Bridge (graph theory)

Last updated
A graph with 16 vertices and six bridges (highlighted in red) Graph cut edges.svg
A graph with 16 vertices and six bridges (highlighted in red)
An undirected connected graph with no bridge edges Undirected.svg
An undirected connected graph with no bridge edges

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.

Contents

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.

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, 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. (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]

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, 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, [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]

Tarjan's bridge-finding algorithm

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:

Bridge-finding with chain decompositions

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 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. [6] Let C be a chain decomposition of a simple connected graph G=(V,E).

  1. G is 2-edge-connected if and only if the chains in C partition E.
  2. An edge e in G is a bridge if and only if e is not contained in any chain in C.
  3. If G is 2-edge-connected, C is an ear decomposition.
  4. G is 2-vertex-connected if and only if G has minimum degree 2 and C1 is the only cycle in C.
  5. 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.
  6. If G is 2-vertex-connected, C is an open ear decomposition.

See also

Notes

  1. Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, New York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN   0-387-98488-7, MR   1633290 .
  2. Westbrook, Jeffery; Tarjan, Robert E. (1992), "Maintaining bridge-connected and biconnected components on-line", Algorithmica, 7 (5–6): 433–464, doi:10.1007/BF01758773, MR   1154584 .
  3. 1 2 Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly , 46 (5): 281–283, doi:10.2307/2303897, hdl: 10338.dmlcz/101517 , JSTOR   2303897 .
  4. Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1, ISBN   978-0-444-87803-8 .
  5. Tarjan, R. Endre (1974), "A note on finding the bridges of a graph", Information Processing Letters, 2 (6): 160–161, doi:10.1016/0020-0190(74)90003-9, MR   0349483 .
  6. 1 2 Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, arXiv: 1209.0700 , doi:10.1016/j.ipl.2013.01.016 .

Related Research Articles

<span class="mw-page-title-main">Prim's algorithm</span> Method for finding minimum spanning trees

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

<span class="mw-page-title-main">Depth-first search</span> Search algorithm

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E )).

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications, especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components.

<span class="mw-page-title-main">Connectivity (graph theory)</span> Basic concept of graph theory

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

<span class="mw-page-title-main">Biconnected component</span> Maximal biconnected subgraph

In graph theory, a biconnected 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 are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components.

<i>k</i>-vertex-connected graph Graph which remains connected when k or fewer nodes removed

In graph theory, a connected graph G is said to be k-vertex-connected if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

<span class="mw-page-title-main">Tarjan's strongly connected components algorithm</span> Graph algorithm

Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. The algorithm is named for its inventor, Robert Tarjan.

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

<span class="mw-page-title-main">SPQR tree</span> Representation of a graphs triconnected components

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

In graph theory, Robbins' theorem, named after Herbert Robbins, states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.

<span class="mw-page-title-main">Petersen's theorem</span>

In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph.

<span class="mw-page-title-main">Split (graph theory)</span>

In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms.