From Strong Components to a Smaller Digraph
A directed graph can contain groups of vertices that are mutually reachable, with one-way movement between those groups. Replacing each such group by a single vertex produces a smaller digraph that records the connections between groups. This construction, called the condensation, separates the internally cyclic parts of a digraph from the way those parts connect to one another.
Throughout, a digraph is finite and simple: its arcs are ordered pairs of distinct vertices, and there are no multiple copies of an arc. A directed walk follows the direction of every arc in sequence; a walk of length zero from a vertex to itself is allowed. A vertex \(u\) can reach \(v\) if there is a directed walk from \(u\) to \(v\). Two vertices are mutually reachable if each can reach the other.
The definition deliberately excludes arcs from a component to itself. Such arcs may occur in \(G\), but they describe movement within one strong component, not a connection between two components. Likewise, if several arcs of \(G\) go from \(C\) to \(D\), the condensation contains just one arc \(C\to D\).
Why Strong Components Form a Partition
Mutual reachability is an equivalence relation. Every vertex reaches itself by a length-zero walk, so the relation is reflexive. If \(u\) reaches \(v\) and \(v\) reaches \(u\), the definition is symmetric. If \(u\) and \(v\) are mutually reachable, and \(v\) and \(w\) are mutually reachable, concatenating the relevant directed walks shows that \(u\) reaches \(w\) and \(w\) reaches \(u\); this proves transitivity. Therefore its equivalence classes partition the vertices, and these classes are exactly the strong components. In particular, every vertex belongs to exactly one component, including a vertex that has no incident arcs.
This description also explains maximality: a strong component contains all vertices equivalent to any of its members. It is not necessary for every pair of vertices in a component to have a direct arc between them; directed walks through other vertices suffice.
Worked Example: A Chain of Strong Components
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{1\to2,2\to1,2\to3,3\to4,4\to3,4\to5,5\to6,6\to7,7\to6,2\to5\}\).
Vertices \(1\) and \(2\) reach one another using the two arcs between them, so they form a strongly connected set. Vertices \(3\) and \(4\) also reach one another, as do \(6\) and \(7\). Vertex \(5\) is alone in its component. There is no directed route back from the later groups to the earlier ones: arcs between these groups point from \(\{1,2\}\) toward \(\{3,4\}\) or \(\{5\}\), then toward \(\{6,7\}\). Thus the components are \(A=\{1,2\}\), \(B=\{3,4\}\), \(C=\{5\}\), and \(D=\{6,7\}\).
To construct the condensation, inspect the original arcs and retain only those whose endpoints are in different components. The arcs \(2\to3\) and \(2\to5\) give \(A\to B\) and \(A\to C\); \(4\to5\) gives \(B\to C\); and \(5\to6\) gives \(C\to D\). The other arcs stay within their own component. Hence \(\mathcal{C}(G)\) has vertex set \(\{A,B,C,D\}\) and arc set \(\{A\to B,A\to C,B\to C,C\to D\}\).
| Original arcs inspected | Result in the condensation |
|---|---|
| \(1\to2,\,2\to1\) | Discard: both endpoints are in \(A\) |
| \(2\to3\) | Add \(A\to B\) |
| \(2\to5\) | Add \(A\to C\) |
| \(3\to4,\,4\to3\) | Discard: both endpoints are in \(B\) |
| \(4\to5\) | Add \(B\to C\) |
| \(5\to6\) | Add \(C\to D\) |
| \(6\to7,\,7\to6\) | Discard: both endpoints are in \(D\) |
Check: Each of the four listed condensation arcs comes from an arc in \(G\), and every arc of \(G\) either produces one of those arcs or stays within a component. In particular, \(A\to C\) is present even though \(A\to B\to C\) is also possible; the direct original arc \(2\to5\) creates it.
Reachability Between Components
The condensation retains exactly the information about reachability between different strong components. More precisely, if \(u\in C\) and \(v\in D\), then \(u\) reaches \(v\) in \(G\) if and only if \(C\) reaches \(D\) in \(\mathcal{C}(G)\). Here, reachability in the condensation means that there is a directed walk from one component-vertex to the other, with a length-zero walk allowed when \(C=D\).
Proof. Suppose first that a directed walk in \(G\) goes from \(u\) to \(v\). Record, in order, the strong components visited along the walk. Whenever the walk crosses from one component to a different one, the original arc used for that step gives an arc between those components in \(\mathcal{C}(G)\). Removing consecutive repeated component labels therefore gives a directed walk from \(C\) to \(D\) in the condensation.
Conversely, suppose that \(\mathcal{C}(G)\) has a directed walk \(C=C_0\to C_1\to\cdots\to C_k=D\). For each arc \(C_i\to C_{i+1}\), the definition provides an original arc \(x_i\to y_{i+1}\) with \(x_i\in C_i\) and \(y_{i+1}\in C_{i+1}\). Within each strong component, any vertex can reach any other. Thus one can travel inside \(C_0\) from \(u\) to \(x_0\), cross the chosen arc, travel inside \(C_1\) to \(x_1\), and continue until reaching \(v\) inside \(C_k\). Concatenating these walks and arcs gives a directed walk from \(u\) to \(v\) in \(G\). If \(k=0\), then \(C=D\) and the internal strong connectivity of that component gives the same conclusion. \(\square\)
The Condensation Is Acyclic
Proof. Suppose, for contradiction, that the condensation contains a directed cycle \(C_0\to C_1\to\cdots\to C_{k-1}\to C_0\), where the component-vertices on the cycle are distinct. Since condensation arcs join distinct components, \(k\ge2\). For each arc on the cycle, choose an original arc that gives rise to it. Inside each strong component, any vertex can reach the tail or head needed for the next chosen arc. Consequently, following the cycle gives a directed walk in \(G\) from any vertex of \(C_i\) to any vertex of \(C_j\), for each pair of components on the cycle: follow the cycle forward from \(C_i\) to \(C_j\), using internal walks within the components between the selected arcs. Following the cycle from \(C_j\) back to \(C_i\) gives reachability in the reverse direction. Thus vertices in \(C_i\) and \(C_j\) are mutually reachable. They must belong to the same equivalence class of mutual reachability, contradicting that \(C_i\) and \(C_j\) are distinct strong components. Hence the condensation has no directed cycle. \(\square\)
The contradiction depends on the whole directed cycle, not on any one condensation arc. A single arc \(C\to D\) only gives reachability in one direction. A cycle of component-arcs supplies a return route, making the components on that cycle mutually reachable and therefore unable to remain separate components.
Worked Example: Two Components and an Isolated Vertex
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e\}\) and \(E=\{a\to b,b\to a,b\to c,c\to d,d\to c\}\). The vertices \(a,b\) are mutually reachable, and \(c,d\) are mutually reachable. There is an arc from the first pair to the second pair, but no arc or directed walk back. The vertex \(e\) has no incident arcs, so it forms a singleton strong component. The component set is \(A=\{a,b\}\), \(B=\{c,d\}\), and \(E_0=\{e\}\).
Inspecting the arcs gives \(a\to b\) and \(b\to a\) within \(A\), \(c\to d\) and \(d\to c\) within \(B\), and the single cross-component arc \(b\to c\). Therefore the condensation has vertices \(A,B,E_0\) and the one arc \(A\to B\). The isolated component \(E_0\) has no incoming or outgoing arcs.
Check: The condensation has no directed cycle: its only arc ends at \(B\), and no arc leaves \(B\). Also, reachability is preserved: \(a\) reaches \(d\) in \(G\) using \(a\to b\to c\to d\), matching the condensation walk \(A\to B\).
Worked Example: Branching Between Components
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{1\to2,2\to1,2\to3,1\to3,3\to4,4\to5,5\to4,3\to6,6\to5\}\).
The components are \(A=\{1,2\}\), \(B=\{3\}\), \(C=\{4,5\}\), and \(D=\{6\}\). The pair \(1,2\) is mutually reachable, as is \(4,5\); \(3\) and \(6\) are singleton components. The arcs between components are \(A\to B\), \(B\to C\), \(B\to D\), and \(D\to C\). In particular, the two original arcs \(1\to3\) and \(2\to3\) both give the same condensation arc \(A\to B\), so that arc is included only once.
Check: From \(A\), the condensation can reach \(B\), then \(C\) or \(D\), and \(D\) also reaches \(C\). There is no route from \(C\) back to any other component, so none of these routes closes into a directed cycle. The edge \(6\to5\) is the reason for \(D\to C\); it does not create \(C\to D\).
Common Mistake: Adding Internal Arcs
A common error is to put an arc \(C\to C\) in the condensation whenever the original digraph has an arc whose endpoints both lie in \(C\). That does not follow the definition: the condensation records arcs between distinct components. For example, in the branching example, \(1\to2\) and \(2\to1\) lie within \(A=\{1,2\}\). A mistaken construction might include \(A\to A\), then call it a directed cycle of length one. The correction is to discard both original arcs when forming the condensation. They contribute to the strong connectivity inside \(A\), not to an arc between components.
A second useful check is that the condensation should not have two copies of an arc. If several original arcs go from \(C\) to \(D\), the condition “at least one” in the definition adds exactly one arc \(C\to D\). These conventions ensure that the condensation is itself a simple digraph and that its arcs express only connections between distinct strong components.
Why the Construction Matters
Condensation compresses a digraph without losing its reachability pattern between strong components. A large region in which every vertex can reach every other becomes one component-vertex; one-way connections between regions remain as directed arcs. The theorem guarantees that all directed cycles are confined to the original strong components: after those components are contracted, no directed cycle remains. This makes the condensation a useful summary of global structure, while leaving questions about how to order or process acyclic digraphs to the later material on directed acyclic graphs.
Check Your Understanding
For each question, distinguish arcs internal to a component from arcs between components.
- Why do the mutual-reachability classes partition the vertex set?
- If three original arcs go from component \(C\) to component \(D\), how many arcs \(C\to D\) does the condensation contain?
- Can a vertex with no incident arcs form a strong component? Explain.
- In the branching example, why do \(1\to3\) and \(2\to3\) produce only one condensation arc?
- Explain why a directed cycle among distinct component-vertices contradicts their being distinct strong components.