C++で学ぶビジングの定理：グラフの辺彩色を実装する方法

ビジングの定理（Vizing's Theorem）とは、グラフ理論における重要な定理の一つです。この定理によると、単純グラフの彩色指数（chromatic index）は「最大次数」または「最大次数＋1」のいずれかに必ずなります。ここで彩色指数とは、グラフの辺彩色（edge coloring）に必要な色数の最小値を指します。

つまり、隣接する辺同士が同じ色にならないように全ての辺を塗り分ける場合、必要な色の数は最大でも「グラフの最大次数＋1」種類で足りるということです。本記事では、このビジングの定理をC++で実装するプログラムを紹介します。

アルゴリズム

プログラムの流れは以下の通りです。

開始
　　1. グラフの頂点数と辺数を入力として受け取る。
　　2. 各辺を構成する頂点のペアを入力する。
　　3. EdgeColor() 関数：グラフの辺を彩色する。
　　　 1) 現在の辺に対して色 c を割り当てる（最初は 1）。
　　　 2) 同じ色が隣接する辺で既に使われている場合、
　　　　 その色を破棄し、次の色で再試行する。
終了

サンプルコード

以下は、ビジングの定理に基づいて辺彩色を行うC++プログラムの完全な実装例です。

#include<iostream>
using namespace std;

void EdgeColor(int ed[][3], int e) {
    int i, c, j;
    for(i = 0; i < e; i++) {
        c = 1; // 現在の辺に最初は色1を割り当てる
        // 同じ色が隣接する辺で使用されている場合は、
        // その色を破棄して flag に戻り、次の色を試す
        flag:
        ed[i][2] = c;
        for(j = 0; j < e; j++) {
            if(j == i)
                continue;
            if(ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] || ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
                if(ed[j][2] == ed[i][2]) {
                    c++;
                    goto flag;
                }
            }
        }
    }
}

int main() {
    int i, n, e, j, max = -1;
    cout<<"Enter the number of vertices of the graph: ";
    cin>>n;
    cout<<"Enter the number of edges of the graph: ";
    cin>>e;
    int ed[e][3], deg[n+1] = {0};
    for(i = 0; i < e; i++) {
        cout<<"\nEnter the vertex pair for edge "<<i+1;
        cout<<"\nN(1): ";
        cin>>ed[i][0];
        cout<<"N(2): ";
        cin>>ed[i][1];
        // 各頂点の次数を計算
        ed[i][2] = -1;
        deg[ed[i][0]]++;
        deg[ed[i][1]]++;
    }
    // 最大次数を求める
    for(i = 1; i <= n; i++) {
        if(max < deg[i])
            max = deg[i];
    }
    EdgeColor(ed , e);
    cout<<"\nAccording to Vizing's theorem this graph can use maximum of "<<max+1<<" colors to generate a valid edge coloring.\n\n";
    for(i = 0; i < e; i++)
        cout<<"\nThe color of the edge between vertex N(1):"<<ed[i][0]<<" and N(2):"<<ed[i][1]<<" is: color"<<ed[i][2]<<".";
}

プログラムのポイント

• 各辺は ed[i][0] と ed[i][1] に両端の頂点番号を、ed[i][2] に割り当てられた色を保持します。
• EdgeColor() 関数では、現在処理中の辺と頂点を共有する隣接辺を調べ、色が重複していれば色番号を増やして再試行します。
• 入力時に各頂点の次数を集計し、その最大値から「最大次数＋1」すなわちビジングの定理が保証する色数の上限を求めています。

出力結果

Enter the number of vertices of the graph: 4
Enter the number of edges of the graph: 3

Enter the vertex pair for edge 1
N(1): 1
N(2): 2

Enter the vertex pair for edge 2
N(1): 3
N(2): 2

Enter the vertex pair for edge 3
N(1): 4
N(2): 1

According to Vizing's theorem this graph can use maximum of 3 colors to generate a valid edge coloring.

The color of the edge between vertex N(1):1 and N(2):2 is: color1.
The color of the edge between vertex N(1):3 and N(2):2 is: color2.
The color of the edge between vertex N(1):4 and N(2):1 is: color2.

この実行例では、頂点4個・辺3本のグラフに対して、最大次数は2であるため、ビジングの定理より使用できる色数の上限は「2＋1＝3色」と表示されています。実際の彩色結果を見ると、すべての辺が隣接する辺と異なる色で塗り分けられていることが確認できます。このように、ビジングの定理はグラフの辺彩色問題において必要な色数の範囲を保証する、非常に有用な理論です。