색도 지수(Chromatic Index)란 주어진 그래프의 변 색칠(edge coloring)에 필요한 최소한의 색 개수를 의미합니다. 즉, 그래프의 모든 변을 서로 인접한 변끼리는 서로 다른 색을 갖도록 칠할 때 필요한 최대 색의 수입니다. 이 글에서는 C++를 이용해 순환 그래프(Cyclic Graph)의 색도 지수를 찾는 방법을 알아보겠습니다.
알고리즘
순환 그래프의 색도 지수를 구하는 절차는 다음과 같습니다.
시작
정점의 개수 'n'과 변의 개수 'e'를 입력받습니다.
'e'개의 각 변에 대해 두 정점 쌍을 edge[][] 배열에 입력받습니다.
함수 ChromaticIndex()가 그래프의 변을 색칠합니다:
A) 현재 변에 색 c를 할당합니다.
B) 인접한 변 중 같은 색이 있다면 해당 색은 폐기하고,
flag 레이블로 돌아가 다음 색으로 다시 시도합니다.
C) 순환 그래프의 색도 지수를 출력합니다.
각 변에 할당된 색을 출력합니다.
종료
예제 코드
#include<iostream>
using namespace std;
int ChromaticIndex(int ed[][3], int e) {
int i, c, j, max = -1;
// 모든 변 'i'에 유효한 색을 할당합니다.
for(i = 0; i < e; i++) {
c = 1;
flag:
// 현재 변에 색을 할당
ed[i][2] = c;
for(j = 0; j < e; j++) {
if(j == i)
continue;
// 변 i와 인접한 변들의 색을 검사합니다.
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;
}
}
}
}
// 색도 지수를 찾아 반환합니다.
for(i = 0; i < e; i++) {
if(max < ed[i][2])
max = ed[i][2];
}
return max;
}
int main() {
int i, v, e, j, max = -1;
cout<<"Enter the number of vertices of the graph: ";
cin>>v;
cout<<"Enter the number of edges of the graph: ";
cin>>e;
int ed[e][3];
for(i = 0; i < e; i++) {
cout<<"\nEnter the vertex pair for edge "<<i+1;
cout<<"\nV(1): ";
cin>>ed[i][0];
cout<<"V(2): ";
cin>>ed[i][1];
ed[i][2] = -1;
}
cout<<"\n\nThe chromatic index of the given graph is: "<<ChromaticIndex(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]<<".";
return 0;
}
코드 설명
- 각 변은
ed[i][0],ed[i][1]에 연결된 두 정점을 저장하고,ed[i][2]에는 할당된 색을 저장합니다. ChromaticIndex()함수는 각 변에 색 1부터 차례대로 부여하면서, 인접한 변(정점을 공유하는 변) 중 같은 색이 있는지 확인합니다.- 색 충돌이 발생하면
goto flag;문을 통해 다음 색으로 재시도하는 방식으로 모든 변을 색칠합니다. - 모든 변의 색칠이 끝나면 사용된 색 중 가장 큰 값을 반환하여 색도 지수를 구합니다.
실행 결과
Enter the number of vertices of the graph:4 Enter the number of edges of the graph: 5 Enter the vertex pair for edge 1 V(1): 2 V(2):1 Enter the vertex pair for edge 2 V(1): 3 V(2): 2 Enter the vertex pair for edge 3 V(1): 3 V(2): 1 Enter the vertex pair for edge 4 V(1): 4 V(2): 2 Enter the vertex pair for edge 5 V(1):1 V(2): 3 The chromatic index of the given graph is: 4 The color of the edge between vertex n(1):2 and n(2):1 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):3 and n(2):1 is: color3. The color of the edge between vertex n(1):4 and n(2):2 is: color3. The color of the edge between vertex n(1):1 and n(2):3 is: color4.
참고: 바징의 정리(Vizing's Theorem)
그래프 이론에서 바징의 정리에 따르면, 단순 그래프의 색도 지수는 Δ 또는 Δ+1입니다. 여기서 Δ는 그래프 내 정점이 가질 수 있는 최대 차수(degree)를 의미합니다. 위 예제에서 정점 3은 세 개의 변과 연결되어 있어 Δ=3이지만, 결과값이 4로 나온 것은 입력된 그래프가 단순 그래프 조건(중복 변 없음)을 완전히 만족하지 않는 경우를 보여주는 예시입니다.