How does below property hold for cross edge in a DFS Tree ?

Question

If (u,v) is a cross edge then

start[u] > start[v]

end[u] > end[v]

Comments

@srestha Ma'am,

i've tried before to include figures in my post, but i failed :P

But, i know this.....edge (u,v) is a cross edge iff, v.start<v.finish<u.start<u.finish.

reference: CLRS chapter 22, III Edition, Question. 22.3-5.

---

definition of cross edge

are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

---

and also it is given

to show that such an edge (u,v) is a forward edge if u.d < v.d and a cross edge if u.d > v.d.

Answer 1

As we are specifying that the u,v is cross edge. Isn't it means that u visited before v and if this is the case then definitely start(u) < start(v) and end(u) > end(v).

So the answer would be the end(u)>end(v). Please let me know if there is anything needs to be corrected.

Comments

**i guess the first condition start(u)<start(v), is what you were trying to write.

coming to the question, the condition you have given is for the forward edge or tree edge, not cross edge. i might be wrong, but please verify your answer once.

---

@aambazinga

then start(u)<start(v)

is it true?

---

@aambazinga 
Please clarify, what needs to be the case for the cross edges then. It will be appreciated if you can show it to us.

---

@Sumit Singh Chauhan @Srestha ,

Given option is incomplete.

Until we don't place a contraint between start(u) and end(v), we can't say that the intervals will not overlap. Think over it..

To ensure that intervals will not overlap, we have to merge the two conditions as follows..

End(v)<start(u)(i.e; before we start visiting u, v is already finished).

And as we know that start of any vertex is practically less than its end.. so completing the conditions...

Start(v)<end(v)<start(u)<start(v). Just take a graph and traverse according to the given condition.. you will get to know.

Let me know if I can explain more.