“Bridge (graph theory)”的意思、由来-开放百科全书

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.^[1] Equivalently, an edge is a bridge if and only if it is not contained in any cycle. 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 of H in G is a maximal subgraph of G that is not contained in H and is not separated by H.

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.

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 set of simple cycles which contains each edge exactly twice.^[4]

Tarjan's bridge-finding algorithm

The first linear time algorithm 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

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 C_i. C=C₁,C₂,... 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).

See also

Notes

1. ^{{citation | last = Bollobás | first = Béla | author-link = Béla Bollobás | doi = 10.1007/978-1-4612-0619-4 | isbn = 0-387-98488-7 | location = New York | mr = 1633290 | page = 6 | publisher = Springer-Verlag | series = Graduate Texts in Mathematics | title = Modern Graph Theory | url = https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA6 | volume = 184 | year = 1998}}.
2. ^{{citation | last1 = Westbrook | first1 = Jeffery | author1-link = Jeff Westbrook | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan | doi = 10.1007/BF01758773 | issue = 5-6 | journal = Algorithmica | mr = 1154584 | pages = 433–464 | title = Maintaining bridge-connected and biconnected components on-line | volume = 7 | year = 1992}}.
3. ^¹{{citation | last = Robbins | first = H. E. | authorlink = Herbert Robbins | journal = The American Mathematical Monthly | pages = 281–283 | title = A theorem on graphs, with an application to a problem of traffic control | volume = 46 | year = 1939 | doi=10.2307/2303897}}.
4. ^{{citation | last = Jaeger | first = F. | contribution = A survey of the cycle double cover conjecture | doi = 10.1016/S0304-0208(08)72993-1 | pages = 1–12 | series = North-Holland Mathematics Studies | title = Annals of Discrete Mathematics 27 – Cycles in Graphs | volume = 27 | year = 1985}}.
5. ^{{citation | last = Tarjan | first = R. Endre | author-link = Robert Tarjan | doi = 10.1016/0020-0190(74)90003-9 | year = 1974 | issue = 6 | journal = Information Processing Letters | mr = 0349483 | pages = 160–161 | title = A note on finding the bridges of a graph | volume = 2}}.
6. ^¹{{citation | last = Schmidt | first = Jens M. | author-link = Jens M. Schmidt | doi = 10.1016/j.ipl.2013.01.016 | issue = 7 | journal = Information Processing Letters | pages = 241–244 | year = 2013 | title = A Simple Test on 2-Vertex- and 2-Edge-Connectivity | volume = 113| arxiv = 1209.0700}}.