Bridge (graph theory)

A graph with 6 bridges (highlighted in red)

An undirected connected graph with no cut edges

In graph theory, a bridge (also known as a cut-edge or cut arc or an isthmus) is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle.

A graph is said to be bridgeless if it contains no bridges. It is easy to see that this is equivalent to 2-edge-connectivity of each nontrivial component.

A graph with n nodes can contain at most n − 1 bridges, since adding additional edges must create a cycle.

Cycle double cover conjecture

An important open problem involving bridges is the cycle double cover conjecture, due to Seymour and Szekeres (1978 and 1979, independently), which states that every bridgeless graph admits a set of cycles which contains each edge exactly twice.^[1]

Bridge-Finding Algorithm

An O( | V | + | E | ) algorithm for finding bridges in a connected graph was found by Tarjan in 1974.^[2] A distributed version of the algorithm also exists.^[3]

Algorithm:

1. Find a spanning tree of G
2. Create a rooted tree T from the spanning tree
3. Traverse the tree T in preorder and number the nodes. Parent nodes in the tree now have lower numbers than child nodes.
4. For each node from v₁ (the leaf nodes of the tree) to 1 (the root node of the tree) do:
   1. Compute the number of descendants ND(v) for this node.
   2. Compute L(v) and H(v)
   3. For each w such that $v \to w$: if L(w) = w and H(w) < w + ND(w) then (v,w) is a bridge.

Definitions: A non-tree (undirected) edge between v and w is denoted by v − − w. An in-tree edge with v as the parent is denoted by $v\to w$.

$ND(v) = 1 + \sum_{v \to w} ND(w)$ where v is the parent node of w.

ND(v) is the number of descendants of v (including itself) in the rooted spanning tree.

$L(v) = \min(\{v\} \cup \{L(w) \mid v \to w\} \cup \{w \mid v--w\})$

$H(v) = \max(\{v\} \cup \{H(w) \mid v \to w\} \cup \{w \mid v--w\})$

L(v) and H(v) are the labels of the nodes with lowest and highest preorder label respectively reachable from v by travelling in the subtree rooted at v, along with at most one non-tree edge.

This algorithm works because ND(v), H(v) and L(v) can all be computed for a node v provided we know their values on all in-tree descendants of v. Also, if and only if the edge $v \to w$ is a bridge, then it is clear that in the subtree rooted at w, it must be impossible to reach any node that is not a descendant of w. This is easy to check because the subtree rooted at w (that is, all descendants of w) consists of the nodes $\{w, w+1, \ldots, w+ND(w)-1\}$ so we can simply check if L(w),H(w) are in this set or not to check whether an edge is a bridge.

Cut arc in trees

An edge or arc e = uv of a tree G is a cut arc of G if and only if the degree of the vertices u and v are greater than 1. Cut arcs are also defined for directed graphs ^[4]

See also

• Cut vertex
• Robbins theorem

Notes

1. ^ http://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm
2. ^ "A note on finding the bridges of a graph", Robert Endre Tarjan, Information Processing Letters, April 1974 pp160-161.
3. ^ http://sma.epfl.ch/~pritchar/math/2006/podc-bicon-a0-poster.pdf
4. ^ Rao, S.B.; Ramachandra Rao, A. The number of cut vertices and cut arcs in a strong directed graph. (English) Acta Math. Acad. Sci. Hung. 22, 411-421 (1972).

References

• Béla Bollobás, Modern graph theory, GTM 184, Springer Verlag, 1998. Page 6.
• Tarjan, Robert Endre. "A note on finding the bridges of a graph". Information Processing Letters 2 (6): 160–161. doi:10.1016/0020-0190(74)90003-9.