連結グラフGにおいて、ノード u と、 u から出ている全てのエッジを削除して得られる部分グラフが、もはや連結でなくなってしまうとき、ノード u をグラフ G の Articulation Point (関節点または切断点)といいます。例えば、以下に示すグラフで、赤いノードが Articulation Points です。

連結グラフの Articulation Points を検出することは、実際の問題で非常に重要になります。たとえば、コンピュータの通信網をグラフとしてモデル化した場合、この通信網の Articulation Points になっているコンピュータが故障してしまえば、その通信網は機能しなくなってしまいます。一方、Articulation Points が存在しない連結グラフになれば、たとえ1つのコンピュータが故障しても、他の全てのコンピュータは通信ができることが保障されます。
以下に示す Depth First Search (DFS) の応用によって、連結グラフ G の全ての Articulation Points を検出することができます。
|
G の任意のノードをスタート点として、DFS を行う。グラフ G の各ノード u に対して、DFS における訪問の順番 prenum[u] を記録します。 |
|
DFS によって生成される木(DFS Tree)における u の親 parent[u] を記録します。ここで、この DFS Tree を T とします。 |
|
各ノード u に対して、以下のうちの最小値として lowest[u] を計算すます。 |
|
i. | prenum[u] |
ii. | G の Back edge (u, v) が存在するとき、ノード v における prenum[v]. Back edge (u, v) とは、ノード u から T に属するノード v に向かう T に属さない G のエッジです |
iii. | T に属するノード u のすべての子供 x に対する lowest[x] |
|
|
Articulation Points は以下のように決定されます |
|
(1) | T のルート r が2つ以上の子供をもつとき(必要十分条件)、 r は G の Articulation Point です。 |
(2) | 各ノード u において、u の親 parent[u] を p とすると、prenum[p] ≦ lowest[u] ならば(必要十分条件)、p は Articulation Point である(p がルートの場合は (1) を適用します)。 |
|
具体的な例を考えてみましょう。
Example 1
以下の図はグラフ G と、G をノード 0 から DFS を行った DFS Tree T を表しています。T において、Back edges は点線で表されていて、各ノードの左側にそれぞれ prenum[u] と lowest[u] が示されています。
prenum[u] は DFS において各ノード u が訪問される順番(pre-order): 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 という順番で記録されます。
lowest[u] は DFS において各ノード u の訪問が"終了"する順番(post-order): 4 → 7 → 6 → 5 → 3 → 2 → 1 → 0 という順番で"決定"されます。lowest[u] がどのように"更新"されていくかは、後ほど説明します。
Graph : G |
|
DFS Tree : T |

|
→ |

|
(1) より
T のルートであるノード 0 の子供の数は 1 つなので、ノード 0 は Articulation Point ではありません。
(2) より
各ノード u の親を p とすると prenum[p] ≦ lowest[u] を満たすかをチェックします。
case 1. ノード 5 (親がノード 3)に注目します
prenum[3] ≦ lowest[5] を満たす (4 ≦ 6)ので、ノード 3 が Articulation Point になります。つまり、ノード 5 またはノード 5 から Tのノードを任意の数だけ下にたどったノード 5 の子孫から、ノード 3 の祖先へのエッジがないことを示しています。
case 2. ノード 2 (親がノード 1)に注目します
prenum[1] ≦ lowest[2] を満たさないので、ノード 1 は Articulation Point ではありません。つまり、ノード 2 またはノード 2 の子孫から、ノード 1 の祖先へのエッジが存在していることを示しています。
以下の例も考えてみましょう。
Example 2
Graph : G |
|
DFS Tree : T |

|
→ |

|
#define SIZE 1000
Graph graph = Graph( SIZE ); // graph structure
bool visited[SIZE];
int prenum[SIZE]; int parent[SIZE]; int lowest[SIZE]; int timer;
void dfs( int current, int prev ){
// ノード current を訪問した直後の処理
prenum[current] = timer; lowest[current] = timer;
timer++;
visited[current] = true;
int next;
while ( (next = graph.next( current )) != graph.END ){
if ( !visited[next] ){
// ノード current からノード next へ訪問する直前の処理
parent[next] = current;
dfs( next, current );
// ノード next の探索が終了した直後の処理
lowest[current] = min( lowest[current], lowest[next] );
} else if ( next != prev ){
// エッジ current --> next が Back-edge の場合の処理
lowest[current] = min( lowest[current], prenum[next] );
}
}
// ノード current の探索が終了した直後の処理
}
void depthFirstSearchScheme(){
for ( int i = 0; i < SIZE; i++ ) visited[ i ] = false;
int root = 0;
timer = 1;
graph.reset();
// lowest の計算
dfs( root, -1 );
}