Ingraph theory, abiconnected component orblock (sometimes known as a2-connected component) is a maximalbiconnectedsubgraph. Anyconnected graph decomposes into atree of biconnected components called theblock-cut tree of the graph. The blocks are attached to each other at sharedvertices calledcut vertices orseparating vertices orarticulation points. Specifically, acut vertex is any vertex whose removal increases the number ofconnected components.[1] A block containing at most one cut vertex is called aleaf block, it corresponds to aleaf vertex in the block-cut tree.
The classicsequential algorithm for computing biconnected components in a connectedundirected graph is due toJohn Hopcroft andRobert Tarjan (1973).[2] It runs inlinear time, and is based ondepth-first search. This algorithm is also outlined as Problem 22-2 ofIntroduction to Algorithms (both 2nd and 3rd editions).
The idea is to run a depth-first search while maintaining the following information:
The depth is standard to maintain during a depth-first search. The lowpoint ofv can be computed after visiting all descendants ofv (i.e., just beforev gets popped off the depth-first-searchstack) as the minimum of the depth ofv, the depth of all neighbors ofv (other than the parent ofv in the depth-first-search tree) and the lowpoint of all children ofv in the depth-first-search tree.
The key fact is that a nonroot vertexv is a cut vertex (or articulation point) separating two biconnected components if and only if there is a childy ofv such thatlowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child ofv (i.e., just beforev gets popped off the depth-first-search stack), and iftrue,v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every suchy (a component which containsy will contain the subtree ofy, plusv), and then erasing the subtree ofy 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).
GetArticulationPoints(i, d) visited[i] :=true depth[i] := d low[i] := d childCount := 0 isArticulation :=falsefor each niin adj[i]doifnot visited[ni]then parent[ni] := i GetArticulationPoints(ni, d + 1) childCount := childCount + 1if 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 simple alternative to the above algorithm useschain decompositions, which are special ear decompositions depending onDFS-trees.[3] Chain decompositions can be computed in linear time by thistraversing rule. LetC be a chain decomposition ofG. ThenG is 2-vertex-connected if and only ifG has minimumdegree 2 andC1 is the onlycycle inC. This gives immediately a linear-time 2-connectivity test and can be extended to list all cut vertices ofG in linear time using the following statement: A vertexv in a connected graphG (with minimum degree 2) is a cut vertex if and only ifv is incident to abridge orv is the first vertex of a cycle inC –C1. The list of cut vertices can be used to create theblock-cut tree ofG in linear time.
In theonline version of the problem, vertices and edges are added (but not removed) dynamically, and a data structure must maintain the biconnected components.Jeffery Westbrook andRobert Tarjan (1992)[4] developed an efficient data structure for this problem based ondisjoint-set data structures. Specifically, it processesn vertex additions andm edge additions inO(mα(m,n)) total time, whereα is theinverse Ackermann function. This time bound is proved to be optimal.
Uzi Vishkin andRobert Tarjan (1985)[5] designed aparallel algorithm on CRCWPRAM that runs inO(logn) time withn +m processors.
One can define abinary relation on the edges of an arbitrary undirected graph, according to which two edgese andf are related if and only if eithere =f or the graph contains asimple cycle through bothe andf. Every edge is related to itself, and an edgee is related to another edgef if and only iff is related in the same way toe. Less obviously, this is atransitive relation: if there exists a simple cycle containing edgese andf, and another simple cycle containing edgesf andg, then one can combine these two cycles to find a simple cycle throughe andg. Therefore, this is anequivalence 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]
Theblock graph of a given graphG is theintersection graph of its blocks. Thus, it has one vertex for each block ofG, and an edge between two vertices whenever the corresponding two blocks share a vertex.A graphH is the block graph of another graphG exactly when all the blocks ofH are complete subgraphs. The graphsH with this property are known as theblock graphs.[7]
Acutpoint,cut vertex, orarticulation point of a graphG 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 atree called theblock-cut tree orBC-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 cut-vertex is a vertex that if removed, the number of network components increases.
{{cite book}}: CS1 maint: multiple names: authors list (link)