GO Classes Scholarship 2023 | Test | Question: 8

Answer 1

Adding edges is never going to increase the number of strongly connected components. The added edge can be between nodes of an existing SCC, thereby not changing the number of SCCs in the graph OR can connect two SCCs such that they are 'fuzed' into one.  

Consider a directed path graph, so each strongly-connected component is reduced to a single vertex. Then adding an edge to complete a cycle from the last component on the path to the first will make all those components into one strongly-connected component, meaning that an added edge can reduce the number of strongly-connected components by any amount.

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 \rightarrow 2 \rightarrow 3 \rightarrow 4 (4$ strongly connected components)

Adding $4 \rightarrow 1$ will result in just $1$ strongly connected components.

On the other hand adding one more edge, say $1 \rightarrow 3$, does not decrease it any more.

Detailed Video Solution:

https://youtu.be/tqjuxfutFHg?t=4700

Comments

In a ConnectedGraph with n-vertices having maximal set of vertices such that any two vertices in the set are strongly connected(mutually reachable), then we get:

   No. of neighbours for any given vertex=(n-1),  degree=(n-1).

   By adding another edge to this it doesnt change the strength of the graph.

Ans: A,D