二重連結グラフとは？DFSによる関節点検出での判定アルゴリズムを解説

二重連結グラフとは

無向グラフにおいて、任意の2つの頂点の間に、途中の頂点を共有しない2本の経路が存在するとき、そのグラフは二重連結グラフ（biconnected graph／二頂点連結グラフ）と呼ばれます。言い換えれば、任意の2頂点が必ず何らかの閉路（サイクル）で結ばれている状態です。

別の見方をすると、グラフGが連結であり、かつ関節点（articulation point、切断点）を1つも含まない場合、そのグラフは二重連結であると言えます。関節点とは、その頂点を取り除くとグラフが非連結に分割されてしまうような頂点のことです。

この問題を解くには、深さ優先探索（DFS）を利用します。DFSでグラフを走査しながら関節点が存在するかどうかを調べ、あわせてすべての頂点が訪問されたかどうかも確認します。未訪問の頂点が残っていれば、そのグラフはそもそも連結ではないため、二重連結ではありません。

入力と出力

入力：
グラフの隣接行列
0 1 1 1 0
1 0 1 0 0
1 1 0 0 1
1 0 0 0 1
0 0 1 1 0

出力：
このグラフは二重連結グラフです。

アルゴリズム

判定の中核となるのは、DFSで関節点を検出する isArticulation 関数です。ここでは各頂点に対して、次の2つの値を管理します。

• disc[v]：頂点vがDFSで発見された時刻（発見順序）
• low[v]：頂点vからDFS木や後退辺を通じて到達できる最も早い発見時刻

isArticulation(start, visited, disc, low, parent)

入力：開始頂点start、訪問済みかどうかを記録するvisited配列、発見時刻を保持するdisc配列、部分木の到達情報を保持するlow配列、各頂点の親を保持するparent配列。

出力：関節点が見つかった場合はtrue。

Begin
    time := 0        //timeの値は次回以降の呼び出しでも初期化されない
    dfsChild := 0
    start を訪問済みとしてマーク
    disc[start] := time + 1、low[start] := time + 1 を設定
    time := time + 1

    グラフGのすべての頂点vについて繰り返し
        (start, v) 間に辺が存在する場合
            v が未訪問なら
                dfsChild を1増やす
                parent[v] := start

                isArticulation(v, visited, disc, low, parent) が true なら
                    return true
                low[start] := low[start] と low[v] の小さい方

                // 根が2つ以上のDFS子を持つ場合は関節点
                parent[start] が φ（根）かつ dfsChild > 1 なら
                    return true

                // 根以外で、子孫が start 以上へ戻れない場合は関節点
                parent[start] が φ 以外かつ low[v] >= disc[start] なら
                    return true
            v が start の親でなければ（後退辺）
                low[start] := low[start] と disc[v] の小さい方
    繰り返し終了
    return false
End

isBiconnected(graph)

入力：与えられたグラフ。

出力：グラフが二重連結であればtrue。

Begin
    最初に、すべての頂点を未訪問にし、各頂点の親を φ に設定する
    isArticulation(0, visited, disc, low, parent) が true なら
        return false

    グラフの各ノード i について
        i が未訪問なら
            return false
    繰り返し終了
    return true
End

C++による実装例

#include<iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0},
   {1, 0, 1, 0, 0},
   {1, 1, 0, 0, 0},
   {1, 0, 0, 0, 1},
   {0, 0, 0, 1, 0}
};

int min(int a, int b) {
   return (a<b)?a:b;
}

bool isArticulation(int start, bool visited[], int disc[], int low[], int parent[]) {
   static int time = 0;
   int dfsChild = 0;
   visited[start] = true;          //最初の頂点を訪問済みにする
   disc[start] = low[start] = ++time;   //発見時刻とlow値を初期化

   for(int v = 0; v<NODE; v++) {
      if(graph[start][v]) {        //startに隣接するすべての頂点vについて
         if(!visited[v]) {
            dfsChild++;
            parent[v] = start;     //startを親として記録
            if(isArticulation(v, visited, disc, low, parent))
               return true;
            low[start] = min(low[start], low[v]);  //v側の部分木がstartの祖先につながる場合
            if(parent[start] == -1 && dfsChild > 1) {  //根が2つ以上の子を持つ場合
               return true;
            }

            if(parent[start] != -1 && low[v]>= disc[start])
               return true;
         } else if(v != parent[start])   //後退辺に対してstartのlow値を更新
            low[start] = min(low[start], disc[v]);
      }
   }
   return false;
}

bool isBiConnected() {
   bool *vis = new bool[NODE];
   int *disc = new int[NODE];
   int *low = new int[NODE];
   int *parent = new int[NODE];

   for(int i = 0; i<NODE; i++) {
      vis[i] = false;    //どのノードも未訪問
      parent[i] = -1;    //初期状態では親は存在しない
   }

   if(isArticulation(0, vis, disc, low, parent))  //関節点が見つかった場合
      return false;
   for(int i = 0; i<NODE; i++)
      if(!vis[i])       //未訪問のノードがあればグラフは非連結
         return false;
   return true;
}

int main() {
   if(isBiConnected())
      cout << "The Graph is a biconnected graph.";
   else
      cout << "The Graph is not a biconnected graph.";
}

出力結果

The Graph is a biconnected graph.
（このグラフは二重連結グラフです）

まとめ

このアルゴリズムは、Tarjanの関節点検出手法に基づいています。隣接行列を用いる実装では計算量は O(V²)、隣接リストを用いれば O(V + E) となり、一度のDFSでグラフが二重連結かどうかを効率的に判定できます。ネットワークの耐障害性の評価など、「1つの頂点の故障で全体が分断されないか」を確認したい場面で役立つ重要な概念です。