이분 그래프(bipartite graph)란 그래프의 모든 정점을 서로 독립적인 두 집합으로 나눌 수 있고, 그래프의 모든 간선이 반드시 한 집합의 정점에서 시작해 다른 집합의 정점으로 연결되는 경우를 말합니다. 다시 말해, 같은 집합 내부에는 어떠한 간선도 존재하지 않는 그래프입니다.
정점 색칠(Vertex Coloring)을 통한 이분 그래프 판별
그래프가 이분 그래프인지 확인하는 대표적인 방법은 정점 색칠 기법입니다. 같은 집합에 속한 정점에는 동일한 색을 부여하고, 다른 집합에 속한 정점에는 다른 색을 부여합니다.
너비 우선 탐색(BFS)을 활용하면 인접한 정점마다 색을 번갈아 가며 칠할 수 있습니다. 탐색 과정에서 인접한 두 정점이 같은 색을 가지게 되는 경우가 발생한다면, 해당 그래프는 이분 그래프가 아니라고 판단할 수 있습니다.
입력 및 출력
입력: 인접 행렬(adjacency matrix) 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 출력: The graph is bipartite. (그래프는 이분 그래프입니다.)
알고리즘
isBipartite(source)
입력 − 시작 정점(source vertex)
출력 − 그래프가 이분 그래프이면 true, 아니면 false
Begin
빈 큐 qu와 색상 배열 colorArray를 선언한다
처음에는 모든 노드에 어떤 색도 칠해져 있지 않다
시작 정점을 빨간색(Red)으로 칠한다
시작 정점을 qu에 삽입한다
qu가 비어 있지 않은 동안 반복한다
qu에서 항목을 꺼내 u에 저장한다
자기 루프(self-loop)가 존재하면
false를 반환한다
u와 연결된 모든 정점 v에 대해 반복한다
v에 색이 없다면
colorArray[u] = red이면
colorArray[v] := blue
colorArray[u] = blue이면
colorArray[v] := red
v를 큐에 삽입한다
colorArray[v] = colorArray[u]라면
false를 반환한다
반복 종료
반복 종료
true를 반환한다
End
C++ 구현 예제
#include<iostream>
#include<string>
#include<queue>
#define NODE 6
using namespace std;
/*int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
}; */
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 0}
};
bool isBipartite(int source) {
queue<int> qu;
string colorArray[NODE];
for(int i = 0; i< NODE; i++)
colorArray[i] = "No Color"; // 처음에는 모든 정점에 색이 지정되어 있지 않음
colorArray[source] = "Red"; // 시작 정점에 빨간색 할당
qu.push(source); // 시작 정점을 큐에 삽입
while(!qu.empty()) {
int u = qu.front();
qu.pop();
if(graph[u][u] == 1) // 자기 루프(self-loop)가 존재하는 경우
return false;
for(int v = 0; v < NODE; v++) {
if(graph[u][v] != 0 && colorArray[v] == "No Color") {
if(colorArray[u] == "Red") // 인접 정점에 교대로 색상 할당
colorArray[v] = "Blue";
else if(colorArray[u] == "Blue")
colorArray[v] = "Red";
qu.push(v); // 새로운 인접 노드를 큐에 추가
} else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
return false; // u와 인접 정점의 색이 같은 경우
}
}
}
return true;
}
int main() {
bool check;
check = isBipartite(0);
if(check)
cout << "The graph is bipartite." << endl;
else
cout << "The graph is not bipartite." << endl;
}
실행 결과
The graph is bipartite.
위 예제에서 사용된 그래프는 정점들을 두 개의 독립된 집합으로 나누었을 때 모든 간선이 서로 다른 집합 사이에만 존재하므로, 이분 그래프로 판별됩니다. 만약 그래프에 홀수 길이의 사이클(odd cycle)이 포함되어 있다면, 어떤 방식으로 색칠하더라도 인접한 정점이 같은 색을 가지게 되어 이분 그래프일 수 없다는 점도 함께 기억해 두면 좋습니다.