Prove that the existence of a back-edge, in the DFS output of a directed graph, is sufficient for detecting the presence of cycles.
What will be an ideal response?
Assume a cyclic Graph G on which you execute DFS algorithm as shown in Figure 2.16 (a).
Assume p is the vertex on the cycle with lowest DFS number.
Since p is on a cycle, there must exist another vertex
q with a directed edge q ? p. Further, q is a descendant of p due to
p 0 s low DFS number (as can be seen from Figure 2.16(b). The edge q ?
p cannot be a tree arc because DFS number of p is lower than DFS number of
q. Further the edge q ? p cannot be a forward arc as the edge q ? p is not a tree arc.
Since vertices q and p are on the
same tree, it cannot be a cross arc either. The only possibility is that q ? p is a back arc.
Therefore, presence of a back arc indicates presence of a cycle in the graph.
You might also like to view...
Does a VM require fewer resources than a physical machine?
What will be an ideal response?
How does the Play Across Slides from the Audio Options group differ from the Loop Until Stopped check box?
A) Play Across Slides lets you set the number of slides you wish the audio to play, the Loop Until Stopped option does not B) Play Across Slides allows you to choose two or more sounds to play simultaneously; the Loop Until Stopped option only allows you to play one over and over again C) Play Across Slides lets you choose up to 10 slide for the audio to play across; the Loop Until Stopped option allows an unlimited number of slides D) Play Across Slides doesn't let you choose the number of slides to play the audio; the Loop Until Stopped option does
What is the significance of understanding the figure/ground relationship?
What will be an ideal response?
Which of the following syslog severity codes indicates an emergency and that the system is unusable?
A. 0 B. 1 C. 6 D. 7