@14:00 he says a cross edge cant go from lower vertex to higher vertex but in the diagram he has drawn the edge from 4 to 8 . Can any one explain how ?
I think what he means is that cross edge can't go from a lower to higher vertex based upon their starting and finishing time , like we can't have cross edge from vertex 2 to 4 because if we would have such an edge then we would discover 4 using 2 rather than going back to 1 and then going to 4.
ruclips.net/video/RDA1nGsEVLY/видео.html -> here is the updated video by the same professor.... he explained ur confussion clearly in the updated video. He was basically saying - A edge from node 'u' to node 'v' can be marked as a cross edge if both the vertices dont share a ancestor descendant relationship and also node 'v' 's starting time should be more than node 'u' 's finishing time.
He says higher number, not vertex. By number, he means DFS number. Since DFS number are chronological, thus if Y has higher DFS number than X, Y was encountered later than X. Thus, only a cross edge Y->X can exist. If an edge X->Y exists, Y will be explored while exploring X, and thus would become a child.
Thank you very much for these applications. It helped me solve many questions .
Brilliant Stuff! Thanks a lot for sharing.
Very Informative. Thanks
is minimum no.of edges to be removed to make a graph acyclic is no.of back edges??
@14:00 he says a cross edge cant go from lower vertex to higher vertex but in the diagram he has drawn the edge from 4 to 8 . Can any one explain how ?
I think what he means is that cross edge can't go from a lower to higher vertex based upon their starting and finishing time , like we can't have cross edge from vertex 2 to 4 because if we would have such an edge then we would discover 4 using 2 rather than going back to 1 and then going to 4.
by higher vertex he means ancestor and by lower vertex he means descendant, 8 is not ancestor of 4 ....
Think of a cross edge as an edge connecting siblings in the tree
ruclips.net/video/RDA1nGsEVLY/видео.html -> here is the updated video by the same professor.... he explained ur confussion clearly in the updated video. He was basically saying - A edge from node 'u' to node 'v' can be marked as a cross edge if both the vertices dont share a ancestor descendant relationship and also node 'v' 's starting time should be more than node 'u' 's finishing time.
He says higher number, not vertex. By number, he means DFS number.
Since DFS number are chronological, thus if Y has higher DFS number than X, Y was encountered later than X.
Thus, only a cross edge Y->X can exist. If an edge X->Y exists, Y will be explored while exploring X, and thus would become a child.