Sign in to watch this lesson
Advanced - Graphs Ā· 3:53
Strong Orientation (Robbins' Theorem)
Can every street of a city be made one-way while every intersection still reaches every other? Robbins' theorem says a connected graph has such a strongly connected orientation exactly when it has no bridge, and one depth-first search builds it: tree edges point down, back edges point up. When bridges exist, the fewest strongly connected components over all orientations is the number of connected pieces plus the number of bridges.
You will learn
- State Robbins' theorem and explain in one line why a bridge makes a strongly connected orientation impossible
- Build a strongly connected orientation with one DFS, orienting each edge the first time it is examined
- Argue with low-link values why the DFS orientation of a bridgeless graph is strongly connected
- Compute the minimum number of SCCs over all orientations as (connected pieces) + (bridges), counting isolated vertices