완전 그래프 간선 색칠(Edge Coloring)을 수행하는 C++ 프로그램

완전 그래프란?

완전 그래프(Complete Graph)는 그래프 내 임의의 두 정점 사이에 항상 간선이 존재하는 그래프를 말합니다. 정점이 n개인 완전 그래프는 모든 정점 쌍이 서로 연결되어 있으므로, 간선의 총 개수는 n × (n − 1) / 2가 됩니다.

이 글에서는 이러한 완전 그래프에 대해 간선 색칠(Edge Coloring)을 수행하는 C++ 프로그램을 소개합니다. 간선 색칠이란 하나의 정점에 연결된 간선들, 즉 서로 인접한 간선끼리는 서로 다른 색을 갖도록 간선에 색을 배정하는 그래프 이론의 대표적인 문제입니다.

알고리즘

시작
    정점의 개수 'n'을 입력받습니다.
    e = n*(n-1)/2개의 간선을 사용하여 완전 그래프를 ed[][] 배열에 구성합니다.
    EdgeColor() 함수를 호출하여 그래프의 간선에 색을 칠합니다.
    A) 현재 간선에 색 c, 즉 처음에는 1을 할당합니다.
    B) 인접한 간선 중 이미 같은 색이 사용되고 있다면,
       해당 색을 폐기하고 flag 레이블로 되돌아가 다음 색을 시도합니다.
    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:
            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]<<".";
}

코드 동작 원리

main() 함수에서는 먼저 정점의 개수 n을 입력받은 뒤, 이중 반복문을 통해 가능한 모든 정점 쌍 (i, j)에 대해 간선 정보를 ed[][] 배열에 저장합니다. 배열의 세 번째 요소 ed[i][2]는 해당 간선에 배정될 색을 나타내며, 초기값은 -1로 설정됩니다.

EdgeColor() 함수는 각 간선을 순회하면서 색 1부터 차례대로 시도합니다. 만약 두 간선이 하나라도 같은 정점을 공유한다면(인접한다면) 두 간선은 서로 다른 색을 가져야 하므로, 색 충돌이 발생하면 c 값을 1 증가시키고 flag 레이블로 되돌아가 다음 색을 다시 검사합니다. 이 과정을 통해 모든 인접 간선이 서로 다른 색을 갖도록 보장합니다.

실행 결과

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₄)는 3가지 색만으로 모든 간선을 충돌 없이 색칠할 수 있습니다. 일반적으로 정점이 n개인 완전 그래프는 n이 짝수일 때 n개, n이 홀수일 때 n−1개의 색이 필요하다는 사실이 잘 알려져 있으며, 이 프로그램은 그 결과를 자동으로 계산해 줍니다.