Ariticulation Points 関節点 切断点

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

連結グラフの Articulation Points を検出することは、実際の問題で非常に重要になります。たとえば、コンピュータの通信網をグラフとしてモデル化した場合、この通信網の Articulation Points になっているコンピュータが故障してしまえば、その通信網は機能しなくなってしまいます。一方、Articulation Points が存在しない連結グラフになれば、たとえ１つのコンピュータが故障しても、他の全てのコンピュータは通信ができることが保障されます。

以下に示す 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 );
}