In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components.[1] Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.
This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see bridge in the Glossary of graph theory.
A graph with
n
n-1
n-1
In every undirected graph, there is an equivalence relation on the vertices according to which two vertices are related to each other whenever there are two edge-disjoint paths connecting them. (Every vertex is related to itself via two length-zero paths, which are identical but nevertheless edge-disjoint.) The equivalence classes of this relation are called 2-edge-connected components, and the bridges of the graph are exactly the edges whose endpoints belong to different components. The bridge-block tree of the graph has a vertex for every nontrivial component and an edge for every bridge.[2]
Bridges are closely related to the concept of articulation vertices, vertices that belong to every path between some pair of other vertices. The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints. Analogously to bridgeless graphs being 2-edge-connected, graphs without articulation vertices are 2-vertex-connected.
In a cubic graph, every cut vertex is an endpoint of at least one bridge.
A bridgeless graph is a graph that does not have any bridges. Equivalent conditions are that each connected component of the graph has an open ear decomposition,[3] that each connected component is 2-edge-connected, or (by Robbins' theorem) that every connected component has a strong orientation.[3]
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 multi-set of simple cycles which contains each edge exactly twice.[4]
The first linear time algorithm (linear in the number of edges) for finding the bridges in a graph was described by Robert Tarjan in 1974.[5] It performs the following steps:
G
F
F
v
ND(v)
L(v)
v
v
v
L(w)
v
v
F
H(v)
v
v
H(w)
v
v
F
w
v
L(w)=w
H(w)<w+ND(w)
v
w
A very simple bridge-finding algorithm[6] uses chain decompositions.Chain decompositions do not only allow to compute all bridges of a graph, they also allow to read off every cut vertex of G (and the block-cut tree of G), giving a general framework for testing 2-edge- and 2-vertex-connectivity (which extends to linear-time 3-edge- and 3-vertex-connectivity tests).
Chain decompositions are special ear decompositions depending on a DFS-tree T of G and can be computed very simply: Let every vertex be marked as unvisited. For each vertex v in ascending DFS-numbers 1...n, traverse every backedge (i.e. every edge not in the DFS tree) that is incident to v and follow the path of tree-edges back to the root of T, stopping at the first vertex that is marked as visited. During such a traversal, every traversed vertex is marked as visited. Thus, a traversal stops at the latest at v and forms either a directed path or cycle, beginning with v; we call this pathor cycle a chain. The ith chain found by this procedure is referred to as Ci. C=C1,C2,... is then a chain decomposition of G.
The following characterizations then allow to read off several properties of G from C efficiently, including all bridges of G.[6] Let C be a chain decomposition of a simple connected graph G=(V,E).