![[-]](/~ygleyzer/course.wiki/images/button-minus.gif)
Q4a - it's not clear why the proposition is about acyclic graph, while it seems that it works on any directed graph
by bondarev - Wednesday, 24 June 2009 18:05:22
Can someone give me an example of a graph that contains cycles and the proposition 4a doesn't hold?
I cannot think of reason why there's a requirement that a graph must be acyclic (an underlined one :)).
Please help...
I cannot think of reason why there's a requirement that a graph must be acyclic (an underlined one :)).
Please help...
Re: Q4a - it's not clear why the proposition is about acyclic graph, while it seems that it works on any directed graph
by abuaffas - Wednesday, 24 June 2009 20:37:47
The reason is
1. because, in this part, we are interested in acyclic graphs.
2. if the graph has cycles, the condition does not hold.
3. if the graph has cycles, you cann't solve it in O(V^2) time.
An example:
V={a,b,c,d}
E={(a,b),(b,c),(b,d),(c,a),(d,a)}
running DFS-visit from every vertex will discover neither forward edges nor cross edges.
1. because, in this part, we are interested in acyclic graphs.
V={a,b,c,d}
E={(a,b),(b,c),(b,d),(c,a),(d,a)}
running DFS-visit from every vertex will discover neither forward edges nor cross edges.
Re: Q4a - it's not clear why the proposition is about acyclic graph, while it seems that it works on any directed graph
by sepetnit - Wednesday, 24 June 2009 19:50:57
But we will get a cross edge while running DFS_VISIT(b):
for example (b,c) , (c,a) and (b,d) will be tree edges and therfore (d,a) will be a cross edge!