Editing Bridge (graph theory) (section)

==Bridge-finding with chain decompositions==
A very simple bridge-finding algorithm<ref name="Schmidt">{{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}}.</ref> uses [[chain decomposition]]s.
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 [[Biconnected component|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 [[Depth-first search|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<sub>i</sub>''. ''C=C<sub>1</sub>,C<sub>2</sub>,...'' 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''.<ref name="Schmidt"/> 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]].
# ''G'' is 2-vertex-connected if and only if ''G'' has minimum degree 2 and ''C<sub>1</sub>'' 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<sub>1</sub>''.
# If ''G'' is 2-vertex-connected, ''C'' is an [[Ear decomposition|open ear decomposition]].