fc2ブログ



Ariticulation Points 関節点 切断点

2006.04.26 22:50  グラフ 探索

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


articulationPoints.gif

連結グラフの 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.GBack 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つ以上の子供をもつとき(必要十分条件)、 rG の 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
artPointG1.gif
artPointT1.gif


(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
artPointG2.gif
artPointT2.gif


#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 );
}

スポンサーサイト



| コメント(2) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

管理人のみ閲覧できます

このコメントは管理人のみ閲覧できます

| | 2009.01.10 14:11

管理人のみ閲覧できます

このコメントは管理人のみ閲覧できます

| | 2009.02.18 21:51

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ