Consider the following directed graph:
I. The shortest path from A to J has length 5, and this is the longest among all shortest paths in the graph.
II. The number of cycles in the graph is exactly half the number of its strongly connected components.
III. If each strongly connected component is collapsed into a single node, there will be two possible topological orderings of the graph.
IV. If node D and all its incident edges are removed, and a new edge from B to E is added, the resulting graph will form a single strongly connected component.
Which of the statements are correct?
A) I, II, and III
B) Only III
C) III and IV
D) Only IV
E) None of the above
Original idea by: Jhonatan Cléto
No comments:
Post a Comment