Algo doubt

Question

Which of the following is false?

1)An edge(u,v) is forward edge if and only if

d[u] < =d[v] <= f[v] <= f[u].

2) an edge (u,v) is a cross edge if and only if

d[u] < f[u] < d[v] < f[v].

3) an edge (u,v) is a back edge if and only if

d[v] < d[u] < f[u] < f[v].

Comments

yes, that means all wrong

rt?

ques is also not welly formed

---

Yes...... thankyou....@srestha

---

wc :)

Answer 1

Tree edge :- is an edge of our DFS tree

Forward edge(u->v) :- An edge which is not part of our DFS tree and here vertex 'v' is descendant of vertex 'u' , both vertices are part of DFS tree. or in simple words , edge that is coming forward in tree but not part of our DFS tree if it's part of our DFS tree then it becomes Tree edge.

in our figure AD is forward edge(here u=A and v=D)during DFS traversal first A is discovered and then D is discovered and then during backtracking first we are done with D and then A

so d[A]<d[D]<f[D]<f[A]

Back edge (u->v) :- An edge which is  not part of our DFS tree and here vertex 'v' is ancestor  to vertex 'u'. Both vertices are part of our DFS tree. or in simple words , edge that is going back to our DFS tree.

here in our figure DA is back edge , suppose there is also an edge from C->A then it's also back edge. so here u=D and v=A. first we will visit A then reach D and then during backtracking will finish D first and then A later. so d[A]<d[D]<f[D]<f[A]

Cross Edge (u->v) :-All other remaining edges are cross edges. those are also not part of our DFS tree. No ancestor relationship b/w 'u' and 'v'. both vertices may belong to our DFS tree or they may belongs to different trees.

in our figure D->C is cross edge , here u=D and v=C , first we visited C and then finish with C and then we reach D and then finish with D also so d[C]<f[C]<d[D]<f[D].

Resources :

https://www.youtube.com/watch?v=Lw5rRctO9js&index=29&list=PLBF3763AF2E1C572F

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm