# Chapter 19. Strong Connectivity # Chapter 19. Strong Connectivity Connectivity in undirected graphs asks whether every vertex can be reached from every other vertex. In directed graphs, direction changes the problem fundamentally. A vertex may reach another vertex without being reachable in return. For this reason, directed graphs require several notions of connectivity. The most important is strong connectivity. A directed graph is strongly connected if every vertex can reach every other vertex by directed paths. This means that movement through the graph is possible in both directions, even if the actual paths differ. Strong connectivity is one of the central structural ideas in directed graph theory. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Strongly_connected_component?utm_source=chatgpt.com)) ## 19.1 Reachability Revisited Let $$ D = (V,A) $$ be a directed graph. A vertex \(v\) is reachable from a vertex \(u\) if there exists a directed path from \(u\) to \(v\). Reachability is directional. It may happen that \(u\) reaches \(v\), while \(v\) does not reach \(u\). For example, consider the directed graph $$ a \to b \to c. $$ The vertex \(c\) is reachable from \(a\), because there is a directed path $$ a,b,c. $$ However, \(a\) is not reachable from \(c\), because no directed path leaves \(c\). Thus directed reachability differs fundamentally from ordinary graph connectivity. ## 19.2 Strong Connectivity A directed graph \(D\) is strongly connected if for every pair of vertices $$ u,v \in V, $$ there exists a directed path from \(u\) to \(v\) and also a directed path from \(v\) to \(u\). Equivalently, every vertex is reachable from every other vertex. This condition may be written as $$ u \leadsto v \qquad \text{and} \qquad v \leadsto u $$ for all vertices \(u\) and \(v\). Strong connectivity is symmetric at the global level. Although individual arcs are directed, the graph as a whole permits movement between every ordered pair of vertices. For example, the directed cycle $$ a \to b \to c \to a $$ is strongly connected. From any vertex, one can follow the cycle to reach any other vertex. ## 19.3 Examples ### Example 1. A Strongly Connected Graph Consider the graph $$ A = \{(a,b),(b,c),(c,a),(c,d),(d,b)\}. $$ We verify strong connectivity. From \(a\), we can reach $$ b,\quad c,\quad d. $$ From \(d\), we can reach $$ b \to c \to a. $$ Every vertex reaches every other vertex. Therefore the graph is strongly connected. ### Example 2. A Graph That Is Not Strongly Connected Consider the graph $$ a \to b \to c. $$ The vertex \(a\) reaches \(b\) and \(c\). The vertex \(b\) reaches \(c\). But \(c\) reaches no other vertex. Therefore the graph is not strongly connected. ### Example 3. A Single Vertex A graph with one vertex and no arcs is strongly connected under the usual convention that every vertex reaches itself by a path of length zero. ## 19.4 Mutual Reachability Define a relation on the vertex set by declaring that $$ u \sim v $$ if and only if $$ u \leadsto v \qquad \text{and} \qquad v \leadsto u. $$ This relation is called mutual reachability. It is an equivalence relation. ### Reflexivity Every vertex reaches itself by the trivial path of length zero. Thus $$ u \sim u. $$ ### Symmetry If $$ u \sim v, $$ then \(u\) reaches \(v\) and \(v\) reaches \(u\). Reversing the statement gives $$ v \sim u. $$ ### Transitivity Suppose $$ u \sim v \qquad \text{and} \qquad v \sim w. $$ Then $$ u \leadsto v, \qquad v \leadsto w. $$ Concatenating paths gives $$ u \leadsto w. $$ Similarly, $$ w \leadsto v, \qquad v \leadsto u, $$ so $$ w \leadsto u. $$ Hence $$ u \sim w. $$ Therefore mutual reachability partitions the vertices into equivalence classes. These equivalence classes are the strongly connected components. ## 19.5 Strongly Connected Components A strongly connected component of a directed graph is a maximal strongly connected subgraph. “Maximal” means that no additional vertex can be added while preserving strong connectivity. The vertices of a directed graph partition uniquely into strongly connected components. This decomposition into maximal mutually reachable sets is standard in graph theory. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Strongly_connected_component?utm_source=chatgpt.com)) For example, consider the graph $$ a \leftrightarrow b, \qquad b \to c, \qquad c \leftrightarrow d. $$ More explicitly, $$ A = \{(a,b),(b,a),(b,c),(c,d),(d,c)\}. $$ The vertices \(a\) and \(b\) form one strongly connected component, because each reaches the other. The vertices \(c\) and \(d\) form another strongly connected component. There is an arc from the first component to the second, but no path returns from the second to the first. Thus the strongly connected components are $$ \{a,b\} \qquad \text{and} \qquad \{c,d\}. $$ ## 19.6 Component Graph Given a directed graph \(D\), collapse each strongly connected component into a single vertex. The resulting graph is called the component graph or condensation graph. An arc exists between two components if an arc in the original graph goes from a vertex in one component to a vertex in the other. A fundamental fact is that the component graph is always a directed acyclic graph. If the component graph contained a directed cycle, then all components on that cycle would mutually reach one another. They would therefore belong to the same strongly connected component, contradicting maximality. Thus strongly connected components reduce arbitrary directed graphs into DAG structure. ## 19.7 Strong Connectivity and Cycles Directed cycles are closely related to strong connectivity. Every directed cycle is strongly connected. If $$ v_0 \to v_1 \to \cdots \to v_{k-1} \to v_0, $$ then every vertex can reach every other vertex by moving around the cycle. However, a strongly connected graph need not be a single cycle. It may contain many overlapping cycles. For example, $$ a \to b,\qquad b \to c,\qquad c \to a,\qquad a \to d,\qquad d \to b $$ is strongly connected but contains more structure than one simple cycle. Cycles generate strong connectivity locally. Strong connectivity combines such cycles into a global reachability condition. ## 19.8 Weak Connectivity A directed graph is weakly connected if its underlying undirected graph is connected. This ignores the directions of arcs. For example, $$ a \to b \to c $$ is weakly connected because the underlying undirected graph $$ a - b - c $$ is connected. But it is not strongly connected, because \(c\) cannot reach \(a\). Thus strong connectivity is stricter than weak connectivity: | Property | Direction respected? | |---|---| | Weak connectivity | No | | Strong connectivity | Yes | Every strongly connected graph is weakly connected. The converse is false. ## 19.9 Unilateral Connectivity Some authors also define unilateral connectivity. A directed graph is unilaterally connected if for every pair of vertices \(u,v\), at least one of the following holds: $$ u \leadsto v \qquad \text{or} \qquad v \leadsto u. $$ This condition is weaker than strong connectivity but stronger than weak connectivity. The directed path $$ a \to b \to c $$ is unilaterally connected, because every pair of vertices is connected in at least one direction. But it is not strongly connected. ## 19.10 Strongly Connected Subgraphs A subgraph \(H\) of a directed graph \(D\) is strongly connected if every pair of vertices in \(H\) mutually reaches each other within \(H\). Strongly connected subgraphs are important because large directed graphs often contain local regions of high internal connectivity. For example: | System | Strongly connected region | |---|---| | Web graph | tightly interlinked websites | | Social network | mutually connected communities | | Dependency graph | recursive dependency groups | | Program control graph | loops and recursive structures | | Transportation network | mutually reachable route clusters | Strongly connected components isolate these internally reachable regions. ## 19.11 Characterization Using Paths A directed graph is strongly connected if and only if every pair of vertices lies on a common directed cycle or can mutually reach each other through chains of directed cycles. More concretely: $$ D \text{ is strongly connected} $$ if and only if for every pair \(u,v\), $$ u \leadsto v \qquad \text{and} \qquad v \leadsto u. $$ This statement is often used as the practical definition. In finite directed graphs, reachability may be checked using graph search algorithms. ## 19.12 Strong Connectivity and Adjacency Matrices Let \(M\) be the adjacency matrix of a directed graph \(D\). Recall that $$ (M^k)_{ij} $$ counts directed walks of length \(k\) from vertex \(v_i\) to vertex \(v_j\). Thus \(v_j\) is reachable from \(v_i\) if and only if there exists some integer \(k \geq 0\) such that $$ (M^k)_{ij} > 0. $$ The graph is strongly connected if every ordered pair of vertices satisfies this condition for some \(k\). Equivalently, for every \(i,j\), there exists a directed walk from \(v_i\) to \(v_j\). This matrix perspective connects strong connectivity with linear algebra and spectral graph theory. ## 19.13 Detecting Strong Connectivity Strong connectivity can be tested algorithmically. A simple method is: 1. Choose a vertex \(v\). 2. Perform a graph search from \(v\). 3. Check whether all vertices are reachable from \(v\). 4. Reverse all arcs. 5. Perform another graph search from \(v\). 6. Check whether all vertices are reachable again. If both searches reach all vertices, then the graph is strongly connected. The reason is simple. The first search verifies that every vertex is reachable from \(v\). The reversed search verifies that every vertex reaches \(v\) in the original graph. More advanced algorithms compute all strongly connected components efficiently. Standard methods include Kosaraju’s algorithm, Tarjan’s algorithm, and Gabow’s algorithm. These algorithms are fundamental in graph processing and compiler theory. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Strongly_connected_component?utm_source=chatgpt.com)) ## 19.14 Strong Connectivity in Applications Strong connectivity appears naturally in many systems. ### Communication Networks A strongly connected communication network allows messages to travel between every pair of locations. ### Transportation Systems In a road network with one-way streets, strong connectivity means every location is reachable from every other location while respecting street directions. ### Web Graphs Groups of mutually linked web pages often form strongly connected components. ### Software Systems Recursive module dependencies form strongly connected regions in dependency graphs. ### State Machines In automata and Markov chains, strong connectivity corresponds to recurrent or communicating states. ## 19.15 Strong Orientation An orientation of an undirected graph assigns a direction to each edge. An orientation is strongly connected if the resulting directed graph is strongly connected. Not every connected graph admits a strong orientation. A connected undirected graph has a strong orientation if and only if it has no bridge. This classical result is known as Robbins’ theorem. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Robbins%27_theorem?utm_source=chatgpt.com)) A bridge prevents strong connectivity because crossing it in one direction disconnects the reverse reachability. ## 19.16 Common Mistakes A common mistake is to confuse weak connectivity with strong connectivity. A graph may be connected when directions are ignored but disconnected when directions are respected. Another mistake is to assume that having a directed cycle implies strong connectivity. A graph may contain cycles while still having unreachable regions. A third mistake is to test reachability only one way. Strong connectivity requires mutual reachability. A fourth mistake is to confuse strongly connected components with arbitrary connected regions. Strongly connected components are maximal with respect to mutual reachability. ## 19.17 Summary A directed graph is strongly connected if every vertex can reach every other vertex through directed paths. Mutual reachability defines an equivalence relation on the vertex set. Its equivalence classes are the strongly connected components. Strongly connected components partition every directed graph. Collapsing them produces a directed acyclic component graph. Strong connectivity is stricter than weak connectivity because it respects arc direction. It is fundamental in network structure, dependency analysis, compiler theory, transportation systems, and graph algorithms. Subsequent chapters build on this idea through directed acyclic graphs, topological ordering, network flow, and advanced directed graph algorithms.