グラフが2部グラフかどうかを判定する方法｜頂点彩色とBFSによるアルゴリズムを解説

グラフの頂点集合を、互いに独立した2つの集合に分割でき、グラフ内のすべての辺が「一方の集合から出発して他方の集合で終わる」関係になっている（＝同じ集合の中に辺が存在しない）とき、そのグラフは2部グラフ（バイパータイトグラフ）であるといいます。

2部グラフかどうかの判定は、頂点彩色を用いて行うことができます。同じ集合に属する頂点には同じ色を割り当て、別の集合に属する頂点には別の色を割り当てます。隣接する頂点同士が必ず異なる色になるように塗分けできれば、そのグラフは2部グラフであると判断できます。

入力と出力

入力：
隣接行列
0 1 0 0 0 1
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
1 0 0 0 1 0

出力：
The graph is bipartite.

この例では、6つの頂点が輪のようにつながったグラフ（6サイクル）を使用しています。隣接する頂点を交互に赤・青で塗っていくと矛盾なく塗分けられるため、2部グラフであると判定されます。

アルゴリズム

isBipartite(source)

入力 − 探索を開始する始点の頂点。
出力 − グラフが2部グラフであれば true、そうでなければ false。

Begin
    空のキュー qu と、色を格納するリスト colorArray を用意する
    初期状態では、すべての頂点に色は割り当てられていない
    始点の頂点を「赤」に彩色する
    始点をキュー qu に追加する
    qu が空でない限り、次の処理を繰り返す
        キューから要素を取り出し、u とする
        自己ループが存在する場合は
            false を返す
        u に隣接するすべての頂点 v について、次を行う
            v がまだ彩色されていない場合
                colorArray[u] が「赤」ならば
                    colorArray[v] := 「青」
                colorArray[u] が「青」ならば
                    colorArray[v] := 「赤」
                v をキューに追加する
            colorArray[v] と colorArray[u] が同じ色の場合
                false を返す
        （v についての繰り返し終了）
    （qu についての繰り返し終了）
    true を返す
End

このアルゴリズムは幅優先探索（BFS）をベースにしており、計算量は O(V + E)（V は頂点数、E は辺数）です。

C++による実装例

#include<iostream>
#include<string>
#include<queue>
#define NODE 6
using namespace std;

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

bool isBipartite(int source) {
    queue<int> qu;
    string colorArray[NODE];

    for(int i = 0; i< NODE; i++)
        colorArray[i] = "No Color";    // 初期状態では全頂点に色を設定しない
    colorArray[source] = "Red";        // 始点の頂点に赤を割り当てる
    qu.push(source);                   // 始点をキューに追加する

    while(!qu.empty()) {
        int u = qu.front();
        qu.pop();
        if(graph[u][u] == 1)           // 自己ループが存在する場合
            return false;

        for(int v = 0; v < NODE; v++) {
            if(graph[u][v] != 0 && colorArray[v] == "No Color") {
                if(colorArray[u] == "Red")       // 隣接頂点に交互の色を割り当てる
                    colorArray[v] = "Blue";
                else if(colorArray[u] == "Blue")
                    colorArray[v] = "Red";
                qu.push(v);                      // 新しい隣接ノードをキューへ追加
            } else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
                return false;                    // u と隣接頂点が同色の場合
            }
        }
    }
    return true;
}

int main() {
    bool check;
    check = isBipartite(0);

    if(check)
        cout << "The graph is bipartite." << endl;
    else
        cout << "The graph is not bipartite." << endl;
}

実行結果

The graph is bipartite.

補足：奇閉路との関係

グラフが2部グラフであるための必要十分条件は、「グラフが奇数長の閉路（奇閉路）を含まないこと」です。例えば、3つの頂点からなる三角形のような閉路が1つでも存在すると、そのグラフは2部グラフになりません。本アルゴリズムでは、隣接する頂点に同じ色が割り当てられた時点で false を返すことで、このような奇閉路の存在を検出しています。