(15pts) we prove that a digraph G=(V, E) has a directed cycle if and only if DFS
ID: 3917898 • Letter: #
Question
(15pts) we prove that a digraph G=(V, E) has a directed cycle if and only if DFS(G) detects a back edge. The proof follows the coloring convention given in class. 1, If-part: Suppose G has back edge e?(1, w). The edge e is colored in--(a) when DFS(G) detects it. We have a cycle created by e and all the (b)edges under_ (c)at the time of detection. This proves the if-part. Only-if-part: Suppose G has a directed cycle C [v, vz, ., v, v1). We can without loss of generality assume that v, is the first node to be colored by DFS(G). At that time, v is colored in (d) all the others are in (e)So there is a time when (vi, V2) is colored in ?(f) , (uz, uj) in--(g) , and all the other edges in--(h)-. Continued, there is a time when the edge-??__ is colored in-?(j)--and all the others in-lk) by DFS(G). The edge--(??is a back edge. Fill in the blanks (A)-(H). The two blanks () are filled with the same expression Answer choices: (1) white, (2) blue, (3) red, (4) v, (5) w, (6) (v, w), (7) (vi, v2), (8) (v2,vz), (9) (v1, v) (10) (vj, v,)., (11) None of the above.Explanation / Answer
Answer:-------------
A. v
B. w
C. (v,w)
D. White
E. Red
F. White
G.Blue
H. White
I. (v1, v2)
J. White
K. Red
I. (v1, v2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.