바이징(Vizing) 정리는 단순 그래프(simple graph)의 색 지수(chromatic index)가 항상 최대 차수(max degree) 또는 최대 차수 + 1 중 하나라는 것을 말합니다. 여기서 색 지수란 그래프의 변(edge)을 색칠할 때 필요한 최대 색의 개수를 의미합니다.
이 글에서는 바이징 정리를 구현하는 C++ 프로그램을 소개하고, 알고리즘과 실행 예제를 함께 살펴봅니다.
알고리즘
시작
그래프의 정점 개수와 변 개수를 입력받는다.
각 변을 이루는 정점 쌍을 입력받는다.
함수 EdgeColor() : 그래프의 변에 색을 칠한다.
1) 현재 변에 색 c(초기값 1)를 할당한다.
2) 인접한 변 중 같은 색이 이미 사용된 경우,
해당 색을 버리고 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로 되돌아가 다음 색으로 재시도
flag:
ed[i][2] = c;
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, max = -1;
cout<<\"그래프의 정점 개수를 입력하세요: \";
cin>>n;
cout<<\"그래프의 변 개수를 입력하세요: \";
cin>>e;
int ed[e][3], deg[n+1] = {0};
for(i = 0; i < e; i++) {
cout<<\"\\n\"<<i+1<<\"번째 변의 정점 쌍을 입력하세요\";
cout<<\"\\nN(1): \";
cin>>ed[i][0];
cout<<\"N(2): \";
cin>>ed[i][1];
// 각 정점의 차수를 계산
ed[i][2] = -1;
deg[ed[i][0]]++;
deg[ed[i][1]]++;
}
// 최대 차수를 구함
for(i = 1; i <= n; i++) {
if(max < deg[i])
max = deg[i];
}
EdgeColor(ed, e);
cout<<\"\\n바이징 정리에 따르면 이 그래프는 유효한 변 색칠을 위해 최대 \"<<max+1<<\"개의 색을 사용할 수 있습니다.\\n\\n\";
for(i = 0; i < e; i++)
cout<<\"\\n정점 N(1):\"<<ed[i][0]<<\"과 N(2):\"<<ed[i][1]<<\" 사이 변의 색은 color\"<<ed[i][2]<<\"입니다.\";
}실행 결과
그래프의 정점 개수를 입력하세요: 4 그래프의 변 개수를 입력하세요: 3 1번째 변의 정점 쌍을 입력하세요 N(1): 1 N(2): 2 2번째 변의 정점 쌍을 입력하세요 N(1): 3 N(2): 2 3번째 변의 정점 쌍을 입력하세요 N(1): 4 N(2): 1 바이징 정리에 따르면 이 그래프는 유효한 변 색칠을 위해 최대 3개의 색을 사용할 수 있습니다. 정점 N(1):1과 N(2):2 사이 변의 색은 color1입니다. 정점 N(1):3과 N(2):2 사이 변의 색은 color2입니다. 정점 N(1):4과 N(2):1 사이 변의 색은 color2입니다.
프로그램 동작 방식
이 프로그램은 탐욕(greedy) 기법으로 변 색칠을 수행합니다. 각 변에 낮은 번호의 색부터 차례로 부여하되, 같은 정점을 공유하는 인접한 변에는 서로 다른 색이 배정되어야 하므로 충돌이 발생하면 다음 색으로 넘어가는 방식입니다.
바이징 정리에 따라 어떤 단순 그래프든 최대 차수 Δ에 대해 Δ 또는 Δ+1개의 색으로 변 색칠이 항상 가능하므로, 이 프로그램은 최대 Δ+1개의 색만 사용해도 반드시 유효한 색칠을 찾을 수 있습니다.
다만 이 구현은 모든 변 쌍을 일일이 비교하는 방식이라 시간 복잡도가 O(E²)이며, 알고리즘 학습과 결과 검증 용도로 적합합니다.