7.41

(a) Robbins’ theorem
A connected undirected graph admits a strong orientation ⇔ it has no bridge.

Proof by induction on the number of edges |E|.
• Base (|E| = |V|, a single cycle). Orient the whole cycle clockwise; this clearly lets every vertex reach every other, so the digraph is strongly connected.
• Induction step. Let G be bridgeless with m > |V| edges and choose any edge e = {u,v}. Because e is not a bridge, G′ = G − e is still connected. By the induction hypothesis G′ has a strong orientation. In that orientation there is already a directed path P_u→v; direct e the opposite way (v→u). Now u reaches v by P_u→v and v reaches u by the single edge e, so u and v stay mutually reachable, and all other pairs were unaffected. Hence G is strongly connected.
Conversely, if G has a bridge, whichever way that bridge is directed its two sides cannot reach each other, so a strong orientation is impossible.

(b) Linear-time construction
The proof is constructive; an O(|V| + |E|) implementation uses an ear decomposition.
1. Run a depth-first search; every non-tree edge (u,v) (with depth(u)<depth(v)) together with the tree path v…u forms an ear. The first ear is a cycle; later ears have new internal vertices only.
2. Orient the first cycle arbitrarily (say clockwise).
3. Process the remaining ears in the order found. For an ear whose endpoints a,b already lie in the oriented subgraph:
• if the current digraph already contains a path a ⇝ b orient the entire ear b→…→a; otherwise orient it a→…→b. That choice always creates a new directed cycle through a and b, preserving strong connectivity.
4. When every ear is processed all edges are oriented and the digraph is strongly connected.

Compact pseudocode:
StrongOrient(G):
parent, depth, low ← DFS(G)
ears ← list of non-tree edges in DFS order
orient first ear as a directed cycle
for each (u,v,path) in ears-without-first:
if Reach(u,v): orient path from v to u
else : orient path from u to v
return orientation
Maintaining a directed spanning tree while ears are added lets Reach(u,v) be answered in O(1), so the whole algorithm is Θ(|V|+|E|). Thus any bridgeless city map can have all its streets made one-way while still letting drivers go anywhere and back.

Back to Chapter 7