In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. 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. Another meaning of "bridge" appears in the term bridge of a subgraph. If H is a subgraph of G, a bridge ofHinG is a maximal subgraph of G that is not contained in H and is not separated by H.
A graph with nodes can contain at most bridges, since adding additional edges must create a cycle. The graphs with exactly bridges are exactly the trees, and the graphs in which every edge is a bridge are exactly the forests. 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. 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.
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.
Traverse the forest in preorder and number the nodes. Parent nodes in the forest now have lower numbers than child nodes.
For each node in preorder, do:
* Compute the number of forest descendants for this node, by adding one to the sum of its children's descendants.
* Compute, the lowest preorder label reachable from by a path for which all but the last edge stays within the subtree rooted at. This is the minimum of the set consisting of the preorder label of, of the values of at child nodes of and of the preorder labels of nodes reachable from by edges that do not belong to.
* Similarly, compute, the highest preorder label reachable by a path for which all but the last edge stays within the subtree rooted at. This is the maximum of the set consisting of the preorder label of, of the values of at child nodes of and of the preorder labels of nodes reachable from by edges that do not belong to.
* For each node with parent node, if and then the edge from to is a bridge.
A very simple bridge-finding algorithm 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, giving a general framework for testing 2-edge- and 2-vertex-connectivity. 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 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 path or 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. Let C be a chain decomposition of a simple connected graph G=.
G is 2-edge-connected if and only if the chains in C partition E.
An edge e in G is a bridge if and only if e is not contained in any chain in C.
G is 2-vertex-connected if and only if G has minimum degree 2 and C1 is the only cycle in C.
A vertex v in a 2-edge-connected graph G is a cut vertex if and only if v is the first vertex of a cycle in C - C1.
If G is 2-vertex-connected, C is an open ear decomposition.
Bridgehead
For a connected graph, a bridge can separate into region and region, i.e. the cut. The vertices and are the two bridgeheads of and. is the near-bridgehead of and far-bridgehead of, and vice versa for.
