Skip to main content

frequently asked questions about Depth -First Search (DFS)



Recall Depth-first Search (DFS), and Show that edge (u, v) is

a)         a tree edge or forward edge if and only if d[u] < d[v] < f[v] < f[u]





b)         a back edge if and only if d[v] < d[u] < f[u] < f[v] 

c)         a cross edge if and only if d[v] < f[v] < d[u] < f[u]

 

 

Solution:

By theorem, DFS of (undirected/directed) Graph let’s say G, where G= (V, E) and we have two vertices u and v such that they hold





·         Vertex u and vertex v are not successor of each other, and intervals d[u], f[u], d[v] and f[v] are disjoint.
·         Vertex u is descendant of vertex v and the interval d[u], f[u] is confined inside interval d[v] and f[v]
·         Vertex v, descendant of vertex u and the interval of d[v] and f[v] confined inside interval d[u] and f[u]




By corollary, vertex v is a successor of vertex u if and only if d[u], is less than d[v], is less than f[v], and it is less than < f[u].





a)         a tree edge or forward edge if and only if d[u] < d[v] < f[v] < f[u]


Edge (u, v) is a forward edge if and only if vertex v is a successor of vertex u, or in other case it is back edge if and only if vertex u is a successor of vertex v, or in other case it is a cross edge if and only if neither vertex u nor vertex v are successor of each other.
The edge between Vertex u and vertex v is forward edge, if vertex v is a successor of vertex u, and v is successor of vertex u  if and only if we have d[u] < d[v] < f[v] < f[u] , hence it is proved






b)         a back edge if and only if d[v] < d[u] < f[u] < f[v] 

Let’s say edge between vertex u and vertex v is back edge then if this self-loop is a back edge then (d[v] is equal to d[u]), which is less then (f[u] equals to f[v]) holds. U is successor of vertex v and edge between u and v contains no self-loop and by corollary; d[v] < d[u] < f[u] < f[v]. Let’s say d[v] is less than and equals to d[u] and it is less then  f[u] and it is less then and equals to f[v], in such case, vertex u and vertex v are same. d[v] is equals to d[u] < f[u] equals to f[v], and edge between u and v is self-loop. Hence, it is a back edge and in such case of vertex u and vertex v d[v] is less than d[u] < f[u] less than f[v],
Vertex u is a successor of vertex v, interval d[u] and f[u] is confined within d[v] and f[v], so it is back edge. Proved

 

c)         a cross edge if and only if d[v] < f[v] < d[u] < f[u]




Let’s suppose edge between vertex u and vertex v is a cross edge. In this case neither vertex u nor vertex v is predecessor of each other. Different intervals d[u], f[u], d[v] and f[v] are separate. So either d[v] < f[v] < d[u] < f[u] is true or d[u] < f[u] < d[v] < f[v] is true. If cross edge between u and v exists then we cannot have the relationship of d[u] < d[v] as vertex v is a successor of vertex u. If relationship exists such that d[u] is less then d[v], in such case vertex v is remains white in color at d[u] time which opposes cross edge. Hence, d[v] is less then f[v]  and it is less then d[u] , it is less then f[u]. By theorem, neither vertex u nor vertex v is successor of each other
Hence, the edge between vertex u and vertex v, they must have a across edge. Proved





Comments

Post a Comment

Popular posts from this blog

Information Retreival System: Implementation

NCBI provides an information retrieval system, Entrez, designed to provide user friendly access to biomedical data including structural, molecular, sequences and literature.   Entrez provides access and searching facilities to more than 30 databases of genome, health, structural, literature, sequence and chemical. It provides faecet, limited and advance searching option with Boolean operators to customize user’s query. It also facilitates querying with wild card characters, mapping and controlled vocabulary. Web implementation of Entrez has more valuable applications and benefits over Network Entrez as it facilitates searching with a tremendous amount of data in different databases. Entrez provides navigational links between different databases either provided by NCBI or external (journal/databases) for each record by using two types of relationships: neighbors and hard links. Both of these types of relationships have been found on the basis of controlled vocabulary and algor...
Post a Comment
Read more

Comparison between Shared memory architecture and Shared nothing architecture

Shared-Memory Architecture: This architecture connects different processor under one operating system through high speed interconnections (cross-bar switch or high speed bus etc). Query response time is reduced by dividing workload to any connected processor with least or no workload. This architecture provides two main advantages over other architectures as it manages load in a perfect manner and easy to manage. It uses least busy processors and allocates new tasks to it so that query processing is done at a fast speed. But along with two major advantages it has three basic disadvantages too. These are low availability, any fault or problem may affect most of the processors making less availability, high cost to link processors and third, limited extensible. Performance   Shared memory architecture provides a good performance as compared to shared nothing architecture by balancing query load on a processor with less or no work load. So...
Post a Comment
Read more

Centrifugal field flow fractionation:

Centrifugal field flow fractionation: Centrifugal FFF is basically a new name given to Sedimentation FFF after further developments in it. The specialty of this Centrifugal FFF is that it involves the use of centrifugal force as the externally applied force which is the basic element required in the separation of the analyte particles. Channel used in this technique is in the form of a ring which spins at 4900 rpm.  This technique is effective in the separation, characterization and purification of micron-sized particles of any type of analyte. It allows for the separation of particles with only a 5% difference in size. Mode of elution In Centrifugal or sedimentation FFF the elution is carried out by hyperlayer mode. The other two modes of elution fail to explain that for the particles having the size less than 1 µm the retention ratio increases with the increase in velocity of flow. In other words the transport velocity is variable for the particles whose size i...
Post a Comment
Read more