Question

Run the strongly connected components algorithm on the following directed graphs G. When doing DFS on GR: whenever there is a choice of vertices to explore, always pick the one that is alphabetically first.

In each case answer the following questions.

(a) In what order are the strongly connected components (SCCs) found?

(b) Which are source SCCs and which are sink SCCs?

(c) Draw the “metagraph” (each meta-node is an SCC of G).

(d) What is the minimum number of edges you must add to this graph to make it strongly connected

Short answer

(a) The order of the strongly connected components are:

$\left\{\mathrm{E},\mathrm{B},\mathrm{A},\mathrm{HGI},\mathrm{CDFJ}\right\}$

The order of the strongly connected components in the second graph are:

$\left\{\mathrm{DGHIF},\mathrm{C},\mathrm{AEB}\right\}$

(b) The source of the first graph is $\mathrm{E}\mathrm{and}\mathrm{B}$.

The sink of the first graph is $\mathrm{CDFJ}$.

The source of the second graph is $\mathrm{C}\mathrm{and}\mathrm{A}$.

The sink of the second graph is$\mathrm{DGHIF}$.

(c) The “metagraph” of both graphs is possible.

(d) The minimum number of edges in the graph $\left(\mathrm{a}\right)$to make it strongly connected is two. And the minimum number of edges in the graph $\left(\mathrm{b}\right)$to make it strongly connected is also two.

Step-by-step solution

Explain Strongly Connected Components

Strongly connected components in a directed graph show that every vertex is reachable from every other vertex. The graph is strongly connected only when the graph is a directed graph.

Depth First Search (DFS) is an application of graph traversal. It traverses downwards and uses the stack as a data structure. Through this, it traverses all vertices in the downward direction one by one.

Some properties ofdepth-first search are as follows:

Using DFT, it is verified whether the graph is connected or not. It means it detects the cycle present in the graph or not.

The number of connected components is found using a depth-first search. Here stack is used as a data structure.

Determine the order of the strongly connected components.

Perform Depth First Search on the given graph and compute pre and post-interval for all vertices as starts from A and ends on C. Here the pre-order of vertex A is 1 and post order is 16.

After applying depth-first search traversal on this graph, the pre-order and post order of all the vertices are as follows:

$\mathrm{A}\left(1,6\right),\mathrm{B}\left(2,3\right),\mathrm{C}\left(7,20\right),\mathrm{D}\left(10,11\right),\mathrm{E}\left(4,5\right),\mathrm{F}\left(9,18\right),\mathrm{G}\left(14,15\right),\mathrm{H}\left(12,17\right),\mathrm{I}\left(13,16\right),\mathrm{J}\left(8,19\right)$

Fig: pre and post-interval of the graph by depth-first search.

In the next step, compute the reverse graph of the given graph by changing the direction of the edges from vertices. The reversal of the graph is represented as ${\mathrm{G}}^{\mathrm{R}}$.

Fig: Reversal of the graph. (${\mathrm{G}}^{\mathrm{R}}$)

After this step, run depth-first search on the graph, and during the depth-first search, process the vertices in decreasing order of their post numbers from step1.

To find the strongly connected components in this graph, determine the vertices which are forming a graph which is directly connected to its all vertices. In this order, there are four strongly connected components formed first, called $\mathrm{CDFJ}$. Here $\mathrm{C}$is the source vertex, which easily is reached with all the other vertices in its own connected component. In order to find other strongly connected components are $\left\{\mathrm{E},\mathrm{B},\mathrm{A},\mathrm{HGI}\right\}$.

So, in this graph, there are five strongly connected components, and they are$\left\{\mathrm{E},\mathrm{B},\mathrm{A},\mathrm{HJI},\mathrm{CDFG}\right\}$

Determine the order of the strongly connected components for graph 2 .

To find the order of the strongly connected component in the graph, firstly apply the Depth-First Search on the given graph and compute pre and post-interval for all vertices. It starts from A and ends on D . Here the pre-order of vertex A is 1 , and the post-order vertex is6 . For B , the pre and post-order is given as $\left(3,4\right)$.

After applying depth-first search traversal on this graph, the pre-order and post-order of all the vertices are as follows:

$\mathrm{A}\left(1,6\right),\mathrm{B}\left(3,4\right),\mathrm{C}\left(7,8\right),\mathrm{D}\left(9,18\right),\mathrm{E}\left(2,5\right),\mathrm{F}\left(13,14\right),\mathrm{G}\left(10,17\right),\mathrm{H}\left(11,16\right),\mathrm{I}\left(12,15\right)$

Fig: pre and post-interval of the graph by depth-first search.

After that, compute the reverse graph of the given graph by changing the direction of the edges from vertices.

The reversal of the graph is represented as ${\mathrm{G}}^{\mathrm{R}}$.

Fig: Reversal of the graph. (${\mathrm{G}}^{\mathrm{R}}$)

Run the depth-first search on the graph, and during the depth-first search, process the vertices in decreasing order of their post numbers from step1.

To find the strongly connected components in this graph, first, determine the vertices which are forming a graph that directly connected to its all vertices.

In this order, there are four different strongly connected components, and formed first is DGHIF. Here D is the source vertex, which is easily reached with all the other vertices in its own connected component.

There are also three more strongly connected components. They are C,AEB .

Here the final answer for this graph is $\left\{\mathrm{DGHIF},\mathrm{C},\mathrm{AEB}\right\}$

Determine the sources and sinks of the strongly connected components

b).

The source SCCs and the sink SCCs are explained as follows:

The source is a vertex from where the graph starts, and the sink is the vertex where it ends. The source is the starting node, and the sink is the ending node of the graph.

Here the source of the strongly connected components are: $\mathrm{E}\mathrm{and}\mathrm{B}$and the sink of the strongly connected components are: CDFJ

The sources and sinks of the strongly connected components for the second graph.

For determining the starting and the ending vertex as the source and the sink node of the second graph, take the help of the diagram.

Fig: Reversal of the graph. (${\mathrm{G}}^{\mathrm{R}}$)

So, here the source of the strongly connected components are: $\mathrm{C}\mathrm{and}\mathrm{A}$

And the sink of the strongly connected components are: $\mathrm{DGHIF}$

Obtain the metagraph for graph (a).

c).

The “metagraph” is defined as each meta-node in a strongly connected component of the graph. Here from each separate vertex of the strongly connected component, there is a path to the other vertex of the strongly connected component of the graph.

From A,B,E there is a path connected to the other separate path that is HGI and CDFJ. This is clearer by taking the help of the graph given below.

Metagraph of given graph (a)

Obtain the metagraph for graph (b).

In this graph, there are three strongly connected components of the graph, which form a sequence of nodes where every vertex is reachable from every other vertex, and this is also a connected directed graph.

In the given graph, from each separate vertex of the strongly connected component, there is a path to the other vertex of the strongly connected component of the graph. The metagraph of the given graph is shown below:

Metagraph of given graph $\left(\mathrm{b}\right)$

Hence, the metagraph for both the given graphs is obtained.

Find the minimum number of edges added to the graph to make it strongly connected for graph (a).

d).

Two directed edges are required in the graph to make it strongly connected. One directed from C and A, and the other from C to E . And when it is added, it makes the graph with no source or sink node.

Thus, the minimum number of edges added to the graph to make it a strongly connected graph is two.

Step 9: Find the minimum number of edges added to the graph to make it strongly connected for graph (b).

d).

Two directed edges are required in the graph to make it strongly connected. One directed from E to B, and the other from D to E. When added, it makes the graph with no source or sink node. Since the meta graphs reveal a directed acyclic graph and adding any edge from sink to source creates a cycle, the entire graph is strongly connected.

Thus, the minimum number of edges added to the graph to make it strongly connected is two.