Английская Википедия:Biconnected component
Шаблон:Short description Шаблон:Confused
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]
Algorithms
Linear time depth-first search
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:
- the depth of each vertex in the depth-first-search tree (once it gets visited), and
- for each vertex Шаблон:Mvar, the lowest depth of neighbors of all descendants of Шаблон:Mvar (including Шаблон:Mvar itself) in the depth-first-search tree, called the Шаблон:Math.
The depth is standard to maintain during a depth-first search. The low point of Шаблон:Mvar can be computed after visiting all descendants of Шаблон:Mvar (i.e., just before Шаблон:Mvar gets popped off the depth-first-search stack) as the minimum of the depth of Шаблон:Mvar, the depth of all neighbors of Шаблон:Mvar (other than the parent of Шаблон:Mvar in the depth-first-search tree) and the lowpoint of all children of Шаблон:Mvar in the depth-first-search tree.
The key fact is that a nonroot vertex Шаблон:Mvar is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child Шаблон:Mvar of Шаблон:Mvar such that Шаблон:Math. This property can be tested once the depth-first search returned from every child of Шаблон:Mvar (i.e., just before Шаблон:Mvar gets popped off the depth-first-search stack), and if true, Шаблон:Mvar separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such Шаблон:Mvar (a component which contains Шаблон:Mvar will contain the subtree of Шаблон:Mvar, plus Шаблон:Mvar), and then erasing the subtree of Шаблон:Mvar 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 := false
for each ni in adj[i] do
if not 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] ≠ null and isArticulation) or (parent[i] = null and 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.
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 Шаблон:Mvar be a chain decomposition of Шаблон:Mvar. Then Шаблон:Mvar is 2-vertex-connected if and only if Шаблон:Mvar has minimum degree 2 and Шаблон:Math is the only cycle in Шаблон:Mvar. This gives immediately a linear-time 2-connectivity test and can be extended to list all cut vertices of Шаблон:Mvar in linear time using the following statement: A vertex Шаблон:Mvar in a connected graph Шаблон:Mvar (with minimum degree 2) is a cut vertex if and only if Шаблон:Mvar is incident to a bridge or Шаблон:Mvar is the first vertex of a cycle in Шаблон:Math. The list of cut vertices can be used to create the block-cut tree of Шаблон:Mvar 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 Шаблон:Mvar vertex additions and Шаблон:Mvar edge additions in Шаблон:Math total time, where Шаблон:Mvar 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 Шаблон:Math time with Шаблон:Math processors.
Related structures
Equivalence relation
One can define a binary relation on the edges of an arbitrary undirected graph, according to which two edges Шаблон:Mvar and Шаблон:Mvar are related if and only if either Шаблон:Math or the graph contains a simple cycle through both Шаблон:Mvar and Шаблон:Mvar. Every edge is related to itself, and an edge Шаблон:Mvar is related to another edge Шаблон:Mvar if and only if Шаблон:Mvar is related in the same way to Шаблон:Mvar. Less obviously, this is a transitive relation: if there exists a simple cycle containing edges Шаблон:Mvar and Шаблон:Mvar, and another simple cycle containing edges Шаблон:Mvar and Шаблон:Mvar, then one can combine these two cycles to find a simple cycle through Шаблон:Mvar and Шаблон:Mvar. 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 Шаблон:Mvar is the intersection graph of its blocks. Thus, it has one vertex for each block of Шаблон:Mvar, and an edge between two vertices whenever the corresponding two blocks share a vertex. A graph Шаблон:Mvar is the block graph of another graph Шаблон:Mvar exactly when all the blocks of Шаблон:Mvar are complete subgraphs. The graphs Шаблон:Mvar with this property are known as the block graphs.[7]
Block-cut tree
A cutpoint, cut vertex, or articulation point of a graph Шаблон:Mvar 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]
Blocks:
Шаблон:Math
Шаблон:Math
Шаблон:Math
Шаблон:Math
Шаблон:Math
Шаблон:Math
Шаблон:Math
Cutpoints:
Шаблон:Math
Шаблон:Math
Шаблон:Math
Шаблон:Math
See also
- Triconnected component
- Bridge (graph theory)
- Single-entry single-exit Counter part of biconnected components in directed graphs
Notes
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Citation.
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Harvtxt credit the definition of this equivalence relation to Шаблон:Harvtxt; however, Harary does not appear to describe it in explicit terms.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Harvtxt, p. 36.
References
External links
