Problem:
On adding one extra edge to a directed graph G, the number of strongly connected components...?
Solution:
Anything could happen!
Suppose the graph is a direct chain, adding an edge to make it a cycle can make it reduce a lot of strongly connected components.
1 -> 2 -> 3 -> 4 (4 strongly connected components)
Adding 4 -> 1 will result in just 1 strongly connected components.
On the other hand adding one more edge, say 1 -> 3, does not decrease it any more.
So the answer is this choice:
...might or might not remain the same (depending on the graph).
On adding one extra edge to a directed graph G, the number of strongly connected components...?
Solution:
Anything could happen!
Suppose the graph is a direct chain, adding an edge to make it a cycle can make it reduce a lot of strongly connected components.
1 -> 2 -> 3 -> 4 (4 strongly connected components)
Adding 4 -> 1 will result in just 1 strongly connected components.
On the other hand adding one more edge, say 1 -> 3, does not decrease it any more.
So the answer is this choice:
...might or might not remain the same (depending on the graph).
No comments:
Post a Comment