In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a bridge, isthmus, cut-edge, or cut arc is an
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed ...
of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
whose deletion increases the graph's 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
Cut may refer to:
Common uses
* The act of cutting, the separation of an object into two through acutely-directed force
** A type of wound
** Cut (archaeology), a hole dug in the past
** Cut (clothing), the style or shape of a garment
** Cut (ea ...
. 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 .
Trees and forests
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
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
, and the graphs in which every edge is a bridge are exactly the
forests
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
.
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.
Relation to vertex connectivity
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
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bi ...
, every cut vertex is an endpoint of at least one bridge.
Bridgeless graphs
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
Open or OPEN may refer to:
Music
* Open (band), Australian pop/rock band
* The Open (band), English indie rock band
* ''Open'' (Blues Image album), 1969
* ''Open'' (Gotthard album), 1999
* ''Open'' (Cowboy Junkies album), 2001
* ''Open'' (YF ...
,
[.] that each connected component is
2-edge-connected, or (by
Robbins' theorem) that every connected component has a
strong orientation In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that makes it into a strongly connected graph.
Strong orientations have been applied to the design of one-way road networks. ...
.
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.
Tarjan's bridge-finding algorithm
The first
linear time algorithm for finding the bridges in a graph was described by
Robert Tarjan
Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's off-line lowest common ancestors algorithm, and co-inventor of both splay trees ...
in 1974.
[.] It performs the following steps:
* Find a
spanning forest
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
of
* Create a rooted forest
from the spanning forest
* 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 (denoting each node using its preorder number), 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.
Bridge-finding with chain decompositions
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'' (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 path
or cycle a ''chain''. The ''i''th chain found by this procedure is referred to as ''C
i''. ''C=C
1,C
2,...'' 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=(V,E)''.
# ''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''.
# If ''G'' is 2-edge-connected, ''C'' is an
ear decomposition
In graph theory, an ear of an undirected graph ''G'' is a path ''P'' where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of ''P'' has degree two in ''G''. A ...
.
# ''G'' is 2-vertex-connected if and only if ''G'' has minimum degree 2 and ''C
1'' 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 - C
1''.
# If ''G'' is 2-vertex-connected, ''C'' is an
open ear decomposition
Open or OPEN may refer to:
Music
* Open (band), Australian pop/rock band
* The Open (band), English indie rock band
* ''Open'' (Blues Image album), 1969
* ''Open'' (Gotthard album), 1999
* ''Open'' (Cowboy Junkies album), 2001
* ''Open'' (YF ...
.
See also
*
Biconnected component
In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...
*
Cut (graph theory)
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connec ...
Notes
{{Authority control
Graph connectivity