이분 그래프와 색칠

어떤 간선도 같은 색의 두 정점을 잇지 않도록 그래프를 두 가지 색으로 칠하는 것을 올바른 채색이라고 합니다. 이렇게 칠할 수 있는 그래프를 이분 그래프라고 합니다.

이러한 색칠이 존재하고 한 정점의 색을 고정한다면, 그 정점에서 도달 가능한 모든 정점의 색은 유일하게 결정된다는 점에 주목합시다. 이 정점의 색이 흰색이라고 하면, 그 이웃은 모두 검은색이 되고, 거리가 2인 정점은 모두 다시 흰색, 거리가 3인 정점은 모두 다시 검은색이 되며, 이런 식으로 계속됩니다.

그래프가 이분 그래프인지 확인하고 색칠 결과를 출력하는 일은 깊이 우선 탐색으로 할 수 있습니다. 이번에는 dfs가 정점을 칠해야 할 색을 매개변수로 받으며, 모든 이웃에 대해 재귀적으로 실행되어 이웃들을 반대 색으로 칠합니다. 알고리즘이 끝나면 그래프가 이분 그래프가 아님을 발견하거나(같은 색을 부여해야 하는 인접한 두 정점을 어느 시점에 보게 된 경우), 그래프의 정점들을 두 부분으로 나눈 분할을 찾게 됩니다.

const int maxn = 1e5;
int color[maxn];

void dfs(int v, int col) {
    color[v] = col;
    for (int u : g[v]) {
        if (!color[u]) {
            dfs(u, -col);
        } else if (color[u] != -col) {
            cout << "Graph is not bipartite" << endl;
            exit(0);
        }
    }
}

그래프가 연결되어 있지 않을 수 있으므로, 서로 다른 정점에서 여러 번 실행해야 할 수도 있습니다:

for (int v = 0; v < n; v++)
    if (!color[v])
        dfs(v, 1);

모든 정점과 모든 간선을 한 번씩만 살펴보므로 시간 복잡도는 $O(n + m)$입니다.

#그래프 색칠에 관한 유용한 명제들

그래프의 채색수는 그래프를 올바르게 칠할 수 있는 최소 색의 개수를 말합니다. 일반적인 경우 채색수를 구하는 문제는 다항 시간에 풀리지 않습니다.

그러나 색칠에 관해서는 몇 가지 유용한 명제를 증명할 수 있습니다. 예를 들면 다음과 같습니다.

• 그래프를 두 가지 색으로 칠할 수 있는 것은(또는 동등하게, 그래프가 이분 그래프인 것은) 그래프의 모든 단순 사이클의 길이가 짝수일 때, 그리고 그때에만 성립합니다.
• 모든 정점의 차수가 $k$ 이하이면 그래프를 $k$가지 색으로 칠할 수 있습니다.
• 모든 평면 그래프는 4가지 색으로 칠할 수 있습니다.

처음 두 명제는 연습 문제로 직접 증명해 보시기를 권합니다. 반면 마지막 명제는 아직까지 컴퓨터로만 증명할 수 있습니다.