Skip to content

22.5 Strongly connected components

22.5-1

How can the number of strongly connected components of a graph change if a new edge is added?

It can either stay the same or decrease. To see that it is possible to stay the same, just suppose you add some edge to a cycle. To see that it is possible to decrease, suppose that your original graph is on three vertices, and is just a path passing through all of them, and the edge added completes this path to a cycle. To see that it cannot increase, notice that adding an edge cannot remove any path that existed before.

So, if $u$ and $v$ are in the same connected component in the original graph, then there are a path from one to the other, in both directions. Adding an edge wont disturb these two paths, so we know that $u$ and $v$ will still be in the same $\text{SCC}$ in the graph after adding the edge. Since no components can be split apart, this means that the number of them cannot increase since they form a partition of the set of vertices.

22.5-2

Show how the procedure $\text{STRONGLY-CONNECTED-COMPONENTS}$ works on the graph of Figure 22.6. Specifically, show the finishing times computed in line 1 and the forest produced in line 3. Assume that the loop of lines 5–7 of $\text{DFS}$ considers vertices in alphabetical order and that the adjacency lists are in alphabetical order.

The finishing times of each vertex were computed in exercise 22.3-2. The forest consists of 5 trees, each of which is a chain. We'll list the vertices of each tree in order from root to leaf: $r$, $u$, $q - y - t$, $x - z$, and $s - w - v$.

22.5-3

Professor Bacon claims that the algorithm for strongly connected components would be simpler if it used the original (instead of the transpose) graph in the second depth-first search and scanned the vertices in order of increasing finishing times. Does this simpler algorithm always produce correct results?

Professor Bacon's suggestion doesn't work out. As an example, suppose that our graph is on the three vertices $\{1, 2, 3\}$ and consists of the edges $(2, 1), (2, 3), (3, 2)$. Then, we should end up with $\{2, 3\}$ and $\{1\}$ as our $\text{SCC}$'s. However, a possible $\text{DFS}$ starting at $2$ could explore $3$ before $1$, this would mean that the finish time of $3$ is lower than of $1$ and $2$. This means that when we first perform the $\text{DFS}$ starting at $3$. However, a $\text{DFS}$ starting at $3$ will be able to reach all other vertices. This means that the algorithm would return that the entire graph is a single $\text{SCC}$, even though this is clearly not the case since there is neither a path from $1$ to $2$ of from $1$ to $3$.

22.5-4

Prove that for any directed graph $G$, we have $((G^\text T)^{\text{SCC}})^\text T = G^{\text{SCC}}$. That is, the transpose of the component graph of $G^\text T$ is the same as the component graph of $G$.

First observe that $C$ is a strongly connected component of $G$ if and only if it is a strongly connected component of $G^\text T$. Thus the vertex sets of $G^{\text{SCC}}$ and $(G^\text T)^{\text{SCC}}$ are the same, which implies the vertex sets of $((G^\text T)^\text{SCC})^\text T$ and $G^{\text{SCC}}$ are the same. It suffices to show that their edge sets are the same. Suppose $(v_i, v_j)$ is an edge in $((G^\text T)^{\text{SCC}})^\text T$. Then $(v_j, v_i)$ is an edge in $(G^\text T)^{\text{SCC}}$. Thus there exist $x \in C_j$ and $y \in C_i$ such that $(x, y)$ is an edge of $G^\text T$, which implies $(y, x)$ is an edge of $G$. Since components are preserved, this means that $(v_i, v_j)$ is an edge in $G^{\text{SCC}}$. For the opposite implication we simply note that for any graph $G$ we have $(G^\text T)^{\text T} = G$.

22.5-5

Give an $O(V + E)$-time algorithm to compute the component graph of a directed graph $G = (V, E)$. Make sure that there is at most one edge between two vertices in the component graph your algorithm produces.

(Removed)

22.5-6

Given a directed graph $G = (V, E)$, explain how to create another graph $G' = (V, E')$ such that (a) $G'$ has the same strongly connected components as $G$, (b) $G'$ has the same component graph as $G$, and (c) $E'$ is as small as possible. Describe a fast algorithm to compute $G'$.

(Removed)

22.5-7

A directed graph $G = (V, E)$ is semiconnected if, for all pairs of vertices $u, v \in V$, we have $u \leadsto v$ or $v \leadsto u$. Give an efficient algorithm to determine whether or not $G$ is semiconnected. Prove that your algorithm is correct, and analyze its running time.

Algorithm:

  1. Run $\text{STRONG-CONNECTED-COMPONENTS}(G)}$.
  2. Take each strong connected component as a virtual vertex and create a new virtual graph $G'$.
  3. Run $\text{TOPOLOGICAL-SORT}(G')$.
  4. Check if for all consecutive vertices $(v_i, v_{i + 1})$ in a topological sort of $G'$, there is an edge $(v_i, v_{i + 1})$ in graph $G'$. if so, the original graph is semiconnected. Otherwise, it isn't.

Proof:

It is easy to show that $G'$ is a DAG. Consider consecutive vertices $v_i$ and $v_{i + 1}$ in $G'$. If there is no edge from $v_i$ to $v_{i + 1}$, we also conclude that there is no path from $v_{i + 1}$ to $v_i$ since $v_i$ finished after $v_{i + 1}$. From the definition of $G'$, we conclude that, there is no path from any vertices in $G$ who is represented as $v_i$ in $G'$ to those represented as $v_{i + 1}$. Thus, $G$ is not semi-connected. If there is an edge between all consecutive vertices, we claim that there is an edge between any two vertices. Therefore, $G$ is semi-connected.

Running-time: $O(V + E)$.