Biconnected component

Last updated
Each color corresponds to a biconnected component. Multi-colored vertices are cut vertices, and thus belong to multiple biconnected components. Graph-Biconnected-Components.svg
Each color corresponds to a biconnected component. Multi-colored vertices are cut vertices, and thus belong to multiple biconnected components.

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 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. [1]

Contents

Algorithms

The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan (1973). [2] It runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions).

The idea is to run a depth-first search while maintaining the following information:

  1. the depth of each vertex in the depth-first-search tree (once it gets visited), and
  2. for each vertex v, the lowest depth of neighbors of all descendants of v (including v itself) in the depth-first-search tree, called the lowpoint.

The depth is standard to maintain during a depth-first search. The lowpoint of v can be computed after visiting all descendants of v (i.e., just before v gets popped off the depth-first-search stack) as the minimum of the depth of v, the depth of all neighbors of v (other than the parent of v in the depth-first-search tree) and the lowpoint of all children of v in the depth-first-search tree.

The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child y of v such that lowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child of v (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such y (a component which contains y will contain the subtree of y, plus v), and then erasing the subtree of y from the tree.

The root vertex must be handled separately: it is a cut vertex if and only if it has at least two children in the DFS tree. Thus, it suffices to simply build one component out of each child subtree of the root (including the root).

Pseudocode

GetArticulationPoints(i, d)     visited[i] := true     depth[i] := d     low[i] := d     childCount := 0     isArticulation := falsefor each ni in adj[i] doifnot visited[ni] then             parent[ni] := i             GetArticulationPoints(ni, d + 1)             childCount := childCount + 1             if low[ni] ≥ depth[i] then                 isArticulation := true             low[i] := Min (low[i], low[ni])         else if ni ≠ parent[i] then             low[i] := Min (low[i], depth[ni])     if (parent[i] ≠ nulland isArticulation) or (parent[i] = nulland childCount > 1) then         Output i as articulation point

Note that the terms child and parent denote the relations in the DFS tree, not the original graph.

A demo of Tarjan's algorithm to find cut vertices. D denotes depth and L denotes lowpoint. TarjanAPDemoDepth.gif
A demo of Tarjan's algorithm to find cut vertices. D denotes depth and L denotes lowpoint.


Other algorithms

A simple alternative to the above algorithm uses chain decompositions, which are special ear decompositions depending on DFS-trees. [3] Chain decompositions can be computed in linear time by this traversing rule. Let C be a chain decomposition of G. Then G is 2-vertex-connected if and only if G has minimum degree 2 and C1 is the only cycle in C. This gives immediately a linear-time 2-connectivity test and can be extended to list all cut vertices of G in linear time using the following statement: A vertex v in a connected graph G (with minimum degree 2) is a cut vertex if and only if v is incident to a bridge or v is the first vertex of a cycle in CC1. The list of cut vertices can be used to create the block-cut tree of G in linear time.

In the online version of the problem, vertices and edges are added (but not removed) dynamically, and a data structure must maintain the biconnected components. Jeffery Westbrook and Robert Tarjan (1992) [4] developed an efficient data structure for this problem based on disjoint-set data structures. Specifically, it processes n vertex additions and m edge additions in O(mα(m, n)) total time, where α is the inverse Ackermann function. This time bound is proved to be optimal.

Uzi Vishkin and Robert Tarjan (1985) [5] designed a parallel algorithm on CRCW PRAM that runs in O(log n) time with n + m processors.

Equivalence relation

One can define a binary relation on the edges of an arbitrary undirected graph, according to which two edges e and f are related if and only if either e = f or the graph contains a simple cycle through both e and f. Every edge is related to itself, and an edge e is related to another edge f if and only if f is related in the same way to e. Less obviously, this is a transitive relation: if there exists a simple cycle containing edges e and f, and another simple cycle containing edges f and g, then one can combine these two cycles to find a simple cycle through e and g. Therefore, this is an equivalence relation, and it can be used to partition the edges into equivalence classes, subsets of edges with the property that two edges are related to each other if and only if they belong to the same equivalence class. The subgraphs formed by the edges in each equivalence class are the biconnected components of the given graph. Thus, the biconnected components partition the edges of the graph; however, they may share vertices with each other. [6]

Block graph

The block graph of a given graph G is the intersection graph of its blocks. Thus, it has one vertex for each block of G, and an edge between two vertices whenever the corresponding two blocks share a vertex. A graph H is the block graph of another graph G exactly when all the blocks of H are complete subgraphs. The graphs H with this property are known as the block graphs. [7]

Block-cut tree

A cutpoint, cut vertex, or articulation point of a graph G is a vertex that is shared by two or more blocks. The structure of the blocks and cutpoints of a connected graph can be described by a tree called the block-cut tree or BC-tree. This tree has a vertex for each block and for each articulation point of the given graph. There is an edge in the block-cut tree for each pair of a block and an articulation point that belongs to that block. [8]

A graph, and its block-cut tree.
Blocks:
b1 = [1,2]
b2 = [2,3,4]
b3 = [2,5,6,7]
b4 = [7,8,9,10,11]
b5 = [8,12,13,14,15]
b6 = [10,16]
b7 = [10,17,18]
Cutpoints:
c1 = 2
c2 = 7
c3 = 8
c4 = 10 Block-cut tree2.svg
A graph, and its block-cut tree.
Blocks:
b1 = [1,2]
b2 = [2,3,4]
b3 = [2,5,6,7]
b4 = [7,8,9,10,11]
b5 = [8,12,13,14,15]
b6 = [10,16]
b7 = [10,17,18]
Cutpoints:
c1 = 2
c2 = 7
c3 = 8
c4 = 10

See also

Notes

  1. AL-TAIE, MOHAMMED ZUHAIR. KADRY, SEIFEDINE (2019). "3. Graph Theory". PYTHON FOR GRAPH AND NETWORK ANALYSIS. SPRINGER. ISBN   978-3-319-85037-5. OCLC   1047552679. A cut-vertex is a vertex that if removed, the number of network components increases.{{cite book}}: CS1 maint: multiple names: authors list (link)
  2. Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: efficient algorithms for graph manipulation". Communications of the ACM. 16 (6): 372–378. doi: 10.1145/362248.362272 .
  3. 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 .
  4. Westbrook, J.; Tarjan, R. E. (1992). "Maintaining bridge-connected and biconnected components on-line". Algorithmica. 7 (1–6): 433–464. doi:10.1007/BF01758773.
  5. Tarjan, R.; Vishkin, U. (1985). "An Efficient Parallel Biconnectivity Algorithm". SIAM J. Comput. 14 (4): 862–874. CiteSeerX   10.1.1.465.8898 . doi:10.1137/0214061.
  6. Tarjan & Vishkin (1985) credit the definition of this equivalence relation to Harary (1969); however, Harary does not appear to describe it in explicit terms.
  7. Harary, Frank (1969), Graph Theory, Addison-Wesley, p. 29.
  8. Harary (1969), p. 36.

Related Research Articles

<span class="mw-page-title-main">Tree (graph theory)</span> Undirected, connected and acyclic graph

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

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 )).

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs: a chordal completion of a graph is typically called a triangulation of that graph.

<span class="mw-page-title-main">Bridge (graph theory)</span> Edge in node-link graph whose removal would disconnect the graph

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. 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.

<span class="mw-page-title-main">Circuit rank</span> Fewest graph edges whose removal breaks all cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula

In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.

<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">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.

In graph theory, the strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep track of the current search path. Versions of this algorithm have been proposed by Purdom (1970), Munro (1971), Dijkstra (1976), Cheriyan & Mehlhorn (1996), and Gabow (2000); of these, Dijkstra's version was the first to achieve linear time.

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.

<span class="mw-page-title-main">Block graph</span> Graph whose biconnected components are all cliques

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.

<span class="mw-page-title-main">Ear decomposition</span> Partition of graph into sequence of paths

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. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other.

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.

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.

In graph theory, the weak components of a directed graph partition the vertices of the graph into subsets that are totally ordered by reachability. They form the finest partition of the set of vertices that is totally ordered in this way.

References