시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 393 | 158 | 139 | 44.409% |
사색 정리란, 평면그래프의 각 정점을 4개의 색 중 하나로 칠하되 인접한 두 정점의 색이 다르도록 할 수 있다는 정리이다. 이 정리의 증명은 굉장히 길고 복잡하다. 하지만 이보다 약한 정리인 오색 정리에는 간결하고 아름다운 증명이 있어서 "Proofs From The Book (하늘책의 증명)"에도 실려 있을 정도이다. 우리가 할 일은 그래프의 각 정점에 숫자 1, 2, 3, 4, 5 중 하나를 부여하는 프로그램을 작성하는 것이다. 단, 코드가 "Codes From The Book (하늘책의 코드)"에 실릴 수 있을 정도로 간결하고 아름다워야 한다.
다음은 오색 정리의 증명이다. 사실 1879년에 알프레드 켐프가 이런 방식으로 사색 정리의 증명을 썼으나, 11년이 지난 후 존 퍼시 히우드가 그 증명의 치명적인 오류를 발견했다. 우리가 볼 증명은 퍼시 히우드가 그 증명을 수정해서 완성한 오색 정리의 증명이다. 안타깝게도 이 증명은 "하늘책의 증명"에 실려 있는 증명이 아니다. 그럼에도 "하늘책의 증명" 대신 이 증명을 싣게 된 이유는 여러 가지가 있다.
아래 정리에서 그래프는 모두 단순 그래프라고 가정하겠다. 즉 양 끝점이 같은 간선은 없으며, 같은 쌍의 정점을 연결하는 두 간선도 없다. 우선 평면 그래프에 대한 오일러 공식을 소개한다.
정리 1. 연결된 평면 그래프의 정점의 개수를 V, 간선의 개수를 E, 면의 개수를 F라고 할 때, V-E+F = 2이다.
단, 아래 그림에서 색칠된 것과 같은 무한히 넓은 면도 포함한다.
증명. [TODO: 추가 필요] ■
이제 몇 개의 보조정리를 보자.
보조정리 2. 정점 v의 차수를 deg(v)라고 할 때, ∑deg(v) = 2E이다.
증명. 정점 v와 v와 연결된 간선 e의 순서쌍 (v, e)의 개수를 N이라고 하자. 각 v는 deg(v)개의 간선과 연결되어 있으므로 N = ∑deg(v)이다. 한편, 각 간선은 두 개의 정점과 연결되어 있으므로 N = 2E이다. 두 식을 합치면 ∑deg(v) = 2E를 얻는다. ■
보조정리 3. V > 2인 평면 그래프에 대해 E ≤ 3V - 6이다.
증명. 그래프가 연결되어 있다고 가정하자. 연결되어 있지 않다면 평면 그래프를 유지한 채로 간선을 더 그어서 연결 그래프를 만들 수 있다. F = 1이라면 정리 1에 의해 E = V-1 ≤ 3V - 6이다.
F > 1이라면, 간선 e와 e에 인접한 면 f의 순서쌍 (e, f)의 개수를 N이라고 하자. 그래프가 단순 그래프이므로 각각의 면은 최소 3개의 간선과 인접해 있다. 따라서 N ≥ 3F이다. 한편, 각각의 간선은 최대 2개의 면과 인접해 있다. 따라서 N ≤ 2E이다. 두 식을 합치면 3F ≤ 2E를 얻는다. 정리 1에 의해 V-E+F = 2이므로 3F = 6-3V+3E ≤ 2E이다. 이항하면 E ≤ 3V - 6을 얻는다. ■
[TODO: F=1이면 위 증명이 성립하지 않음. 다시 쓰기]
보조정리 4. 평면 그래프에는 차수가 5 이하인 정점이 존재한다.
증명. V < 6인 경우에는 자명하다. V > 6이라면, d를 그래프 정점들의 평균 차수 ∑deg(v)/V로 정의하자. 보조정리 2에 의해 d = 2E/V이다. 보조정리 3에 의해 d ≤ (6V-12)/V < 6이다. 평균 차수가 6보다 작으므로 차수가 6보다 작은 정점이 존재한다. ■
이제 우리는 오색 정리를 증명할 수 있다.
정리 5. 평면그래프 G의 각 정점을 5개의 색 중 하나로 색칠하되 어떤 인접한 두 정점도 같은 색으로 색칠되지 않도록 할 수 있다.
증명. V에 대한 귀납법을 사용한다. V < 6인 경우에는 자명하다. 보조정리 4에 의해 차수가 5 이하인 정점이 존재한다. 그 정점을 v라고 하자. G에서 v 및 v와 연결된 간선을 모두 제거한 그래프를 G-v라고 할 때, 귀납적 가정에 의해 G-v의 각 정점을 5개의 색 중 하나로 색칠할 수 있다.
이제 G-v의 정점의 색을 모두 v를 제외한 G의 정점의 색으로 옮기고, v의 색을 결정해야 한다. v에 인접한 정점을 시계 방향으로 u1, u2, ..., uk라고 하자. 이때 k = deg(v)이다. 만약 k < 5이거나, k = 5이지만 색이 같은 ui, uj가 존재할 경우, 인접한 정점들에서 사용하지 않은 색 중 하나로 v를 바로 색칠하면 된다.
문제는 k = 5이면서 모든 ui의 색이 전부 다를 때이다. 이때는 Kempe chain이라는 개념을 사용한다. 일반성을 잃지 않고, 각 i에 대해 ui가 i번째 색으로 색칠되어 있다고 가정하자. Ki,j를 다음을 만족하는 모든 정점 v의 집합으로 정의한다. 물론 ui 자체도 Ki,j에 포함된다.
"ui에서 v로 가는 경로를 만들되, 그 경로에 있는 모든 정점의 색은 i이거나 j여야 한다. (편의상 i번째 색을 그냥 i라고 부르자.) 그런 조건을 만족하는 경로가 존재한다."
만약 K1,3가 u3를 포함하지 않는다면, K1,3에 있는 정점의 색을 모두 뒤집는다. 즉 색이 1이었던 것은 3으로, 3이었던 것은 1로 바꾼다. 이제 u1의 색은 3이므로 v를 1로 색칠할 수 있다.
[TODO: 여기에 그림 삽입. 이걸 어느 세월에 다 그리지...]
만약 K1,3가 u3를 포함한다면, G가 평면 그래프이므로 K2,4는 u4를 포함할 수 없다. 따라서 K2,4에 있는 정점의 색을 모두 뒤집고, v를 2로 색칠할 수 있다. 이것으로 증명이 완료된다. ■
[TODO: 여기에 그림 삽입]
[TODO: 하늘책 증명도 넣을까?]
[TODO: 사실 하늘책 증명만 넣는 것도 구데기컵에 적합하지 않을까]
첫 줄에 그래프의 정점의 개수 N과 간선의 개수 M이 주어진다. 정점에는 1부터 N까지의 정수 번호가 하나씩 붙어 있다. 그 다음 줄부터는 각 정점의 좌표가 한 줄씩 주어진다. N+2번째 줄부터 M개의 줄에, 한 줄에 하나씩 간선의 양 끝점의 번호가 주어진다. N은 3 이상 100 이하, M은 3N-6 이하의 양의 정수이다. 모든 정점의 좌표는 -1,000 이상 1,000 이하인 정수이다.
위치가 중복되는 점은 없고, 양 끝점이 같은 간선은 없으며, 같은 쌍의 정점을 연결하는 두 간선도 없다.
총 N개의 숫자를 공백 없이 출력한다. x번째 숫자는 x번째 정점에 부여한 숫자이다. 여러 가지 방법이 있을 경우 그 중 한 방법만 출력하면 된다.
3 3 0 0 2 0 1 1 1 2 2 3 3 1
123
Contest > BOJ User Contest > 구데기컵 > 진짜 구데기컵 2018 🌈번