C++で完全グラフの辺彩色（エッジカラーリング）を実行するプログラム

完全グラフと辺彩色（エッジカラーリング）とは

完全グラフとは、グラフ内の任意の2つの頂点どうしが必ず1本の辺で結ばれているグラフのことです。頂点数が n の完全グラフにおける辺の総数は、e = n × (n − 1) / 2 となります。

辺彩色（エッジカラーリング）とは、同じ頂点を共有する隣接した辺同士が同じ色にならないように、グラフのすべての辺へ色を割り当てる問題です。本記事では、完全グラフに対して辺彩色を実行するC++プログラムを紹介します。

アルゴリズム

1. 頂点数「n」を入力として受け取ります。
2. e = n × (n − 1) / 2 本の辺を用いて、完全グラフを配列 ed[][] 上に構築します。
3. EdgeColor() 関数によって、グラフの各辺に色を割り当てます。
   A) 現在処理している辺には、まず仮の色として c = 1 を割り当てます。
   B) 隣接する辺のいずれかがすでに同じ色を使用している場合、その色を破棄して flag に戻り、次の色を試します。
   C) 他の隣接辺と衝突しなくなった時点の色を、その辺の色として確定させます。
4. 最後に、各辺に割り当てられた色を出力します。

サンプルコード

#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:
            ed[i][2] = c;
            // 隣接する辺が同じ色を使っている場合は、
            // その色を破棄してflagに戻り、次の色を試す
            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, cnt = 0;
    cout<<"Enter the number of vertexes for the complete graph: ";
    cin>>n;
    e = (n*(n-1))/2;
    int ed[e][3];
    for(i = 1; i <= n; i++) {
        for(j = i+1; j <= n; j++) {
            ed[cnt][0] = i;
            ed[cnt][1] = j;
            ed[cnt][2] = -1;
            cnt++;
        }
    }
    EdgeColor(ed , e);
    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]<<".";
}

出力結果

Enter the number of vertexes for the complete graph: 4
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):1 and n(2):3 is: color2.
The color of the edge between vertex n(1):1 and n(2):4 is: color3.
The color of the edge between vertex n(1):2 and n(2):3 is: color3.
The color of the edge between vertex n(1):2 and n(2):4 is: color2.
The color of the edge between vertex n(1):3 and n(2):4 is: color1.

実行結果の解説

頂点数 4 の完全グラフ（K₄）には合計 6 本の辺がありますが、それぞれに color1〜color3 の 3 色が割り当てられています。例えば、頂点1から伸びる辺（1-2、1-3、1-4）はすべて異なる色になっており、頂点2を共有する辺（1-2、2-3、2-4）についても色の重複がありません。このように、「同じ頂点を共有する辺同士は同じ色にならない」という条件が正しく満たされていることが確認できます。

なお、グラフ理論のVizingの定理によれば、頂点数が偶数の完全グラフ K_n に必要な最小色数（彩色指数）は n − 1 色、奇数の場合は n 色であることが知られています。この例では n = 4（偶数）なので、必要な色はちょうど 3 色（n − 1 色）となり、実際の出力結果とも一致しています。