Problem:
On adding one extra edge to a directed graph G, the number of strongly connected components...?
Solution:
Adding one edge from the end of a path to the beginning, the number of strongly connected components reduces from $ n $ to $ 1 $.
Therefore we can eliminate these option:
never decreases by more than 1 (no matter what G is)
..will definitely not change (no matter what G is)
...never decreases (no matter what G is)
Therefore the only feasible option is this:
...could remain the same (for some graphs G)
A simple case for that to happen is simply for a four node cycle (which is a strongly connected component itself), adding any diagonal will not change that fact.
On adding one extra edge to a directed graph G, the number of strongly connected components...?
Solution:
Adding one edge from the end of a path to the beginning, the number of strongly connected components reduces from $ n $ to $ 1 $.
Therefore we can eliminate these option:
Therefore the only feasible option is this:
...could remain the same (for some graphs G)
A simple case for that to happen is simply for a four node cycle (which is a strongly connected component itself), adding any diagonal will not change that fact.
No comments:
Post a Comment