Bridge (graph theory)

Bridge (graph theory)
A graph with 6 bridges (highlighted in red)
An undirected connected graph with no cut edges

In graph theory, a bridge (also known as a cut-edge or cut arc or an isthmus) is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle.

A graph is said to be bridgeless if it contains no bridges. It is easy to see that this is equivalent to 2-edge-connectivity of each nontrivial component.

A graph with n nodes can contain at most n − 1 bridges, since adding additional edges must create a cycle.

Contents

Cycle double cover conjecture

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 cycles which contains each edge exactly twice.[1]

Bridge-Finding Algorithm

An O( | V | + | E | ) algorithm for finding bridges in a connected graph was found by Tarjan in 1974.[2] A distributed version of the algorithm also exists.[3]

Algorithm:

  1. Find a spanning tree of G
  2. Create a rooted tree T from the spanning tree
  3. Traverse the tree T in preorder and number the nodes. Parent nodes in the tree now have lower numbers than child nodes.
  4. For each node from v1 (the leaf nodes of the tree) to 1 (the root node of the tree) do:
    1. Compute the number of descendants ND(v) for this node.
    2. Compute L(v) and H(v)
    3. For each w such that v \to w: if L(w) = w and H(w) < w + ND(w) then (v,w) is a bridge.

Definitions: A non-tree (undirected) edge between v and w is denoted by v − − w. An in-tree edge with v as the parent is denoted by v\to w.

ND(v) = 1 + \sum_{v \to w} ND(w) where v is the parent node of w.

ND(v) is the number of descendants of v (including itself) in the rooted spanning tree.

L(v) = \min(\{v\} \cup \{L(w) \mid v \to w\} \cup \{w \mid v--w\})

H(v) = \max(\{v\} \cup \{H(w) \mid v \to w\} \cup \{w \mid v--w\})

L(v) and H(v) are the labels of the nodes with lowest and highest preorder label respectively reachable from v by travelling in the subtree rooted at v, along with at most one non-tree edge.

This algorithm works because ND(v), H(v) and L(v) can all be computed for a node v provided we know their values on all in-tree descendants of v. Also, if and only if the edge v \to w is a bridge, then it is clear that in the subtree rooted at w, it must be impossible to reach any node that is not a descendant of w. This is easy to check because the subtree rooted at w (that is, all descendants of w) consists of the nodes \{w, w+1, \ldots, w+ND(w)-1\} so we can simply check if L(w),H(w) are in this set or not to check whether an edge is a bridge.

Cut arc in trees

An edge or arc e = uv of a tree G is a cut arc of G if and only if the degree of the vertices u and v are greater than 1. Cut arcs are also defined for directed graphs [4]

See also

Notes

  1. ^ http://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm
  2. ^ "A note on finding the bridges of a graph", Robert Endre Tarjan, Information Processing Letters, April 1974 pp160-161.
  3. ^ http://sma.epfl.ch/~pritchar/math/2006/podc-bicon-a0-poster.pdf
  4. ^ Rao, S.B.; Ramachandra Rao, A. The number of cut vertices and cut arcs in a strong directed graph. (English) Acta Math. Acad. Sci. Hung. 22, 411-421 (1972).

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… …   Universalium

  • graph theory — A branch of mathematics used to represent relations and networks. A graph consists of a set of points (nodes or vertices) and the pairwise links between them (arcs or lines). In sociological applications, the nodes are typically individuals,… …   Dictionary of sociology

  • Connectivity (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 (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… …   Wikipedia

  • Dominator (graph theory) — For Dominating set problem, see Dominating set. In computer science, in control flow graphs, a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n (or sometimes d n). By… …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Bridge (disambiguation) — A bridge is a structure built so that a transportation route can cross above an obstacle.Bridge can also refer to:In entertainment*Bridge (card game disambiguation), multiple card games *Bridge (instrument), the device that anchors the strings to …   Wikipedia

  • Königsberg bridge problem — a mathematical problem in graph theory, solved by Leonhard Euler, to show that it is impossible to cross all seven bridges of the Prussian city of Königsberg in a continuous path without recrossing any bridge. * * * ▪ mathematics  a recreational… …   Universalium

  • Feynman graph — A Feynman graph is a graph suitable to be a Feynman diagram in a particular application of quantum field theory. (The most common use is when each field has quanta (particles) associated with it as the quantum of the electromagnetic field is a… …   Wikipedia

  • Skew-symmetric graph — 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. The isomorphism is required to be an involution without any fixed… …   Wikipedia

  • Königsberg bridge problem — a mathematical problem in graph theory, solved by Leonhard Euler, to show that it is impossible to cross all seven bridges of the Prussian city of Königsberg in a continuous path without recrossing any bridge …   Useful english dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”