이 글에서는 그래프의 간선 색칠(Edge Coloring)을 수행하는 C++ 프로그램을 살펴봅니다. 간선 색칠이란 그래프의 모든 간선에 색을 부여하되, 서로 인접한 두 간선, 즉 같은 정점을 공유하는 간선끼리는 절대 같은 색을 쓰지 않도록 배정하는 기법입니다.
간선 색칠의 기본 개념
간선 색칠에서 '인접한 간선'이란 한 정점에서 뻗어 나온 간선들을 의미합니다. 예컨대 정점 A에 연결된 여러 간선은 모두 서로 인접하기 때문에 반드시 서로 다른 색을 가져야 합니다. 그래프 이론의 바이징 정리(Vizing's Theorem)에 따르면, 한 정점에 연결될 수 있는 간선 수의 최댓값(최대 차수)을 Δ라 할 때 필요한 최소 색의 개수는 Δ 또는 Δ+1개로 알려져 있습니다.
알고리즘
- 그래프의 정점 개수 n과 간선 개수 e를 입력받습니다.
- 그래프는 인접 리스트(adjacency list) 형태로 저장합니다.
- 큐(queue)를 이용해 BFS(너비 우선 탐색)로 그래프를 순회하면서, 이미 사용된 색을 피해 각 간선에 겹치지 않는 색을 하나씩 할당합니다.
C++ 코드 예제
#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<pair<int, int> > > g;
vector<int> color;
bool v[111001];
void col(int n) {
queue<int> q;
int c = 0;
set<int> vertex_colored;
if(v[n])
return;
v[n] = 1;
for(i = 0;i<g[n].size();i++) {
if(color[g[n][i].second]!=-1) {
vertex_colored.insert(color[g[n][i].second]);
}
}
for(i = 0;i<g[n].size();i++) {
if(!v[g[n][i].first]) {
q.push(g[n][i].first);
}
if(color[g[n][i].second]==-1) {
while(vertex_colored.find(c)!=vertex_colored.end())
c++;
color[g[n][i].second] = c;
vertex_colored.insert(c);
c++;
}
}
while(!q.empty()) {
int temp = q.front();
q.pop();
col(temp);
}
return;
}
int main() {
int u,w;
set<int> empty;
cout<<"Enter number of vertices and edges respectively:";
cin>>n>>e;
cout<<"\n";
g.resize(n); //number of vertices
color.resize(e,-1); //number of edges
memset(v,0,sizeof(v));
for(i = 0;i<e;i++) {
cout<<"\nEnter edge vertices of edge "<<i+1<<" :"<<"\n";
cin>>u>>w;
u--; w--;
g[u].push_back(make_pair(w,i));
g[w].push_back(make_pair(u,i));
}
col(0);
for(i = 0;i<e;i++) {
cout<<"Edge "<<i+1<<" is coloured with colour "<<color[i]+1
<< "\n";
}
}실행 결과
Enter number of vertices and edges respectively:4 5 Enter edge vertices of edge 1 :1 2 Enter edge vertices of edge 2 :2 3 Enter edge vertices of edge 3 :1 1 Enter edge vertices of edge 4 :3 4 Enter edge vertices of edge 5 :1 4 Edge 1 is coloured with colour 1 Edge 2 is coloured with colour 2 Edge 3 is coloured with colour 2 Edge 4 is coloured with colour 1 Edge 5 is coloured with colour 3
코드 동작 원리
col() 함수가 핵심 로직을 담당합니다. 먼저 현재 정점 n에 연결된 간선들 중 이미 색이 칠해진 것들의 색 번호를 vertex_colored 집합에 모읍니다. 그다음 아직 색이 없는 간선(color 값이 -1)을 만나면, 집합에 없는 가장 작은 색 번호 c를 찾아 해당 간선에 배정하고 집합에 추가합니다. 이후 큐에 담긴 인접 정점들을 하나씩 꺼내 같은 과정을 재귀적으로 반복함으로써 BFS 순회가 완성됩니다.
main() 함수에서는 간선의 양 끝 정점 u, w를 입력받아 인접 리스트 g에 양방향으로 저장하고, 간선마다 고유 번호 i를 함께 기록합니다. 색칠이 모두 끝나면 각 간선에 배정된 색 번호를 출력하는데, 내부적으로 색이 0부터 시작하므로 출력 시 1을 더해 표시합니다.