入力グラフの線グラフに対する辺彩色（エッジカラーリング）を実行するC++プログラム

無向グラフ G の線グラフ（Line Graph） L(G) とは、元のグラフ G における辺同士の隣接関係を表す別のグラフです。線グラフでは、G の各辺が頂点となり、G で共有する端点を持つ（つまり接している）2つの辺は、L(G) 内で互いに隣接する頂点として結ばれます。

本記事では、入力されたグラフから線グラフを生成し、その線グラフに対して辺彩色（Edge Coloring）を行うC++プログラムを紹介します。辺彩色とは、隣接するどの2つの辺も同じ色にならないように、グラフの辺に色を割り当てる問題です。

アルゴリズム

プログラムの処理の流れは以下のとおりです。

Begin
　　1. 頂点数「n」と辺数「e」を入力として受け取る。
　　2. グラフの e 本の辺について、n 個の頂点ペアを ed[][] に入力する。

　　【関数 GenLineGraph()】
　　　・線グラフを LineEd[][] に構築する。
　　　・元のグラフの各辺について、その辺に隣接する
　　　　（端点を共有する）辺どうしを LineEd 内で結ぶ。

　　【関数 EdgeColor()】
　　　・LineEdge[][] のグラフの辺を彩色する。
　　　・現在の辺に最初は色 col = 1 を割り当てる。
　　　・同じ色が隣接する辺に使われていた場合は、その色を破棄し、
　　　　flag に戻って次の色を試す。
　　　・線グラフの各辺に割り当てられた色を出力する。
End.

サンプルコード

以下は、実際に動作するC++による実装例です。辺には自動的に a, b, c… というラベルが付けられます。

#include<iostream>
using namespace std;
int GenLineGraph(int ed[][2], char LineEd[][3], int e) {
    int i, cnt = 0, j, N;
    char c;
    for(i = 0; i < e; i++) {
        for(j = i+1; j < e; j++) {
            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]) {
                LineEd[cnt][0] = 'a'+i;
                LineEd[cnt][1] = 'a'+j;
                LineEd[cnt][2] = 0;
                cnt++;
            }
        }
    }
    N = cnt;
    cout<<"\n\nThe adjacency list representation for the given graph: ";
    for(i = 0; i < e; i++) {
        cnt = 0;
        c = 'a'+i;
        cout<<"\n\t"<<c<<"-> { ";
        for(j = 0; j < N; j++) {
            if(LineEd[j][0] == i+'a') {
                cout<<LineEd[j][1]<<" ";
                cnt++;
            } else if(LineEd[j][1] == i+'a') {
                cout<<LineEd[j][0]<<" ";
                cnt++;
            } else if(j == e-1 && cnt == 0)
                cout<<"Isolated Vertex!";
        }
        cout<<" }";
    }
    return N;
}
void EdgeColor(char ed[][3], int e) {
    int i, col, j;
    for(i = 0; i < e; i++) {
        col = 1;
        flag:
            ed[i][2] = col;
        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]) {
                    col++;
                    goto flag;
                }
            }
        }
    }
}
int main() {
    int i, n, e, j, max = -1;
    char c= 'a';
    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][2];
    char LineEd[e*e][3];
    for(i = 0; i < e; i++) {
        cout<<"\nEnter the vertex pair for edge '"<<c++<<"'";
        cout<<"\nV(1): ";
        cin>>ed[i][0];
        cout<<"V(2): ";
        cin>>ed[i][1];
    }
    e = GenLineGraph(ed, LineEd, e);
    EdgeColor(LineEd , e);
    for(i = 0; i < e; i++)
        cout<<"\nThe color of the edge between vertex n(1):"<<LineEd[i][0]<<" and n(2):"<<LineEd[i][1]<<" is: color"<<0+LineEd[i][2]<<".";
}

実行結果

4つの頂点と3本の辺（a: 1-2、b: 3-2、c: 4-1）からなるグラフを入力した場合の実行例です。辺 a は辺 b・c の両方に接しているため、それぞれ異なる色が割り当てられていることがわかります。

Enter the number of vertices of the graph:4
Enter the number of edges of the graph: 3
Enter the vertex pair for edge 'a'
V(1): 1
V(2): 2
Enter the vertex pair for edge 'b'
V(1): 3
V(2): 2
Enter the vertex pair for edge 'c'
V(1): 4
V(2): 1
The adjacency list representation for the given graph:
a-> { b c }
b-> { a }
c-> { a }
The color of the edge between vertex n(1):a and n(2):b is: color1.
The color of the edge between vertex n(1):a and n(2):c is: color2.

まとめ

このプログラムでは、まず GenLineGraph() 関数が入力グラフの辺同士の隣接関係を調べて線グラフを構築し、続いて EdgeColor() 関数が貪欲法（グリーディ法）によって各辺に最小限の色を順次割り当てています。この手法により、隣接する辺同士が必ず異なる色になるように彩色でき、スケジューリング問題やネットワーク設計など、さまざまな応用分野で役立つグラフ理論の基礎技術を学ぶことができます。