Ariticulation Points 関節点 切断点
2006.04.26 22:50 グラフ 探索
連結グラフ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] を計算すます。 | |||||||
|
|||||||
Articulation Points は以下のように決定されます | |||||||
|
具体的な例を考えてみましょう。
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 ); }
| コメント(2) | トラックバック(0) | ↑ページトップ |