입력 그래프의 선 그래프(Line Graph)에 에지 컬러링을 수행하는 C++ 프로그램

무방향 그래프 G의 선 그래프(Line Graph) L(G)는 원본 그래프 G의 에지(간선)들 사이의 인접 관계를 표현하는 또 다른 그래프입니다. 즉, 원본 그래프의 각 에지가 선 그래프에서는 하나의 정점이 되며, 두 에지가 원본 그래프에서 정점을 공유할 때 선 그래프에서 서로 연결됩니다.

이 글에서는 입력으로 주어진 그래프의 선 그래프를 생성한 뒤, 해당 선 그래프에 대해 에지 컬러링(Edge Coloring)을 수행하는 C++ 프로그램을 살펴봅니다.

알고리즘

시작
    정점의 개수 'n'과 에지의 개수 'e'를 입력받는다.
    그래프의 'e'개 에지에 대한 'n'개의 정점 쌍을 ed[][] 배열에 입력받는다.
    함수 GenLineGraph():
        LineEd[][] 배열에 선 그래프를 구성한다.
        선 그래프를 만들기 위해, 주어진 그래프의 각 에지에 대해
        해당 에지와 인접한 에지들을 LineEd에 연결한다.
    함수 EdgeColor():
        LineEdge[][] 그래프의 에지에 색상을 지정한다.
        현재 에지에 색상 col(초기값 1)을 할당한다.
        인접한 에지 중 같은 색상이 있다면 해당 색상은 버리고
        flag로 돌아가 다음 색상을 시도한다.
        선 그래프의 각 에지에 대한 색상을 출력한다.
끝.

예제 코드

#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<<"

The adjacency list representation for the given graph: ";
   for(i = 0; i < e; i++) {
      cnt = 0;
      c = 'a'+i;
      cout<<"
	"<<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<<"
Enter the vertex pair for edge '"<<c++<<"'";
      cout<<"
V(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<<"
The 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개로 구성된 그래프를 입력했을 때의 실행 결과는 다음과 같습니다.

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.

동작 방식 요약

위 프로그램은 크게 세 단계로 동작합니다.

1. 선 그래프 생성 (GenLineGraph)

모든 에지 쌍을 비교하여 두 에지가 하나 이상의 정점을 공유하는 경우, 선 그래프에서 이 둘을 연결하는 에지를 추가합니다. 에지에는 a, b, c처럼 알파벳 문자로 이름이 부여되며, 완성된 선 그래프는 인접 리스트 형태로 출력됩니다.

2. 에지 컬러링 (EdgeColor)

각 에지에 색상 1부터 순서대로 할당하되, 이미 색칠된 인접 에지와 색상이 겹치면 다음 색상을 시도합니다(goto 문을 활용한 반복). 이 과정을 통해 인접한 에지끼리는 항상 서로 다른 색상을 갖도록 보장합니다.

3. 결과 출력

선 그래프의 모든 에지에 대해 어떤 색상이 배정되었는지 화면에 출력합니다. 위 예제에서는 에지 a-b에는 color1, 에지 a-c에는 color2가 할당된 것을 확인할 수 있습니다.