新頁面 1

[Basic Concepts]

Articulation point: An Articulation point in a connected graph is a vertex that, if delete, would break the graph into two or more pieces (connected component).
Biconnected graph: A graph with no articulation point called biconnected. In other words, a graph is biconnected if and only if any vertex is deleted, the graph remains connected.
Biconnected component: A biconnected component of a graph is a maximal biconnected subgraph- a biconnected subgraph that is not properly contained in a larger biconnected subgraph.
A graph that is not biconnected can divide into biconnected components, sets of nodes mutually accessible via two distinct paths.

The graphs we discuss below are all about loop-free undirected ones.

image1.jpg (29545 bytes)

Figure 1. The graph G that is not biconnected

How to find articulation points?
Figure 2. Depth-first panning tree of the graph G	[Step 1.]	Find the depth-first spanning tree T for G
	[Step 2.]	Add back edges in T
	[Step 3.]	Determine DNF(i) and L(i) DNF(i): the visiting sequence of vertices i by depth first search L(i): the least DFN reachable frome i through a path consisting of zero or more tree edges followed by zero or one back edge
	[Step 4.]	Vertex i is an articulation point of G if and only if eather: i is the root of T and has at least two children i is not the root and has a child j for which L(j)>=DFN(i)

[Example] The DFN(i) and L(i) of Graph G in Figure 1 are:

Vertex G is an articulation point because G is not the root and in depth-first spanning tree in Figure 2, L(L)>=DFN(G), that L is one of its children

Vertex A is an articulation point because A is the root and in depth-first spanning tree in Figure 2, it has more than one child, B and F

Vertex E is not an articulation point because E is not the root and in depth-first spanning tree in Figure 2, L(G)<DFN(E) and L(D)<DFN(E), that G and D are its children