Grinberg-Introduction-Graph-Theory · Problem 4.8
Digraphs and multidigraphs
Mathematics — Graph Theory · strong-weak-components
Problem
Let be a multidigraph. Prove that the strong components of are the weak components of if and only if each arc of is contained in at least one cycle.Intuitive explanation
The key insight is that strong connectivity requires paths in both directions, while weak connectivity only requires an undirected path. An arc survives in a strong component only if you can return to it—meaning it must be part of a cycle. Conversely, if every arc lies in some cycle, then any weakly connected piece can be traversed in both directions along its arcs, making weak and strong components coincide. Think of it as: weak components are the "connected pieces," but they only become strongly connected when every edge is "reversible" through cycles.
Intuitive explanation
The key insight is that strong connectivity requires paths in both directions, while weak connectivity only requires an undirected path. An arc survives in a strong component only if you can return to it—meaning it must be part of a cycle. Conversely, if every arc lies in some cycle, then any weakly connected piece can be traversed in both directions along its arcs, making weak and strong components coincide. Think of it as: weak components are the "connected pieces," but they only become strongly connected when every edge is "reversible" through cycles.