Strong Connectivity

Graph Theory · Axiom Academy

LESSON Strong Connectivity in Directed Graphs Understanding different types of connectivity in digraphs A directed graph is weakly connected if its underlying undirected graph is connected. In other words, if we ignore the direction of all edges and treat them as undirected, we get a connected graph. The animation shows a weakly connected digraph. Notice how paths exist when we ignore edge directions, but directed paths may not exist in both directions. 2. Strongly Connected Digraphs A directed graph is strongly connected if for every pair of vertices u and v, there exists a directed path from u to v AND a directed path from v to u. This is a much stronger condition. The animation demonstrates bidirectional reachability. Click on vertex pairs to see paths in both directions. 3. Strong Connectivity as an Equivalence Relation We can define a relation on vertices: if and only if there exist directed paths from u to v and from v to u. This relation is an equivalence relation! Reflexive: Every vertex u is strongly connected to itself (via the trivial path) Symmetric: If u ~ v, then v ~ u (by definition: paths exist in both directions) Transitive: If u ~ v and v ~ w, then u ~ w (concatenate paths: u→v→w and w→v→u) 4. Examples: Strong vs. Weak Connectivity Let's examine concrete examples to understand the difference between strongly and weakly connected digraphs. Example 1 (left): Strongly connected—every vertex can reach every other vertex via directed paths.

This is the written version of the interactive lesson above. See the full Graph Theory course.