시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 98 49 39 52.000%

문제

사색 정리란, 평면그래프의 각 정점을 4개의 색 중 하나로 칠하되 인접한 두 정점의 색이 다르도록 할 수 있다는 정리이다. 이 정리의 증명은 굉장히 길고 복잡하다. 하지만 이보다 약한 정리인 오색 정리에는 간결하고 아름다운 증명이 있어서 "Proofs From The Book (하늘책의 증명)"에도 실려 있을 정도이다. 우리가 할 일은 그래프의 각 정점에 숫자 1, 2, 3, 4, 5 중 하나를 부여하는 프로그램을 작성하는 것이다. 단, 코드가 "Codes From The Book (하늘책의 코드)"에 실릴 수 있을 정도로 간결하고 아름다워야 한다.

다음은 오색 정리의 증명이다. 사실 1879년에 알프레드 켐프가 이런 방식으로 사색 정리의 증명을 썼으나, 11년이 지난 후 존 퍼시 히우드가 그 증명의 치명적인 오류를 발견했다. 우리가 볼 증명은 퍼시 히우드가 그 증명을 수정해서 완성한 오색 정리의 증명이다. 안타깝게도 이 증명은 "하늘책의 증명"에 실려 있는 증명이 아니다. 그럼에도 "하늘책의 증명" 대신 이 증명을 싣게 된 이유는 여러 가지가 있다.

  1. 오색 정리의 증명 중 가장 잘 알려져 있다. 실제로 위키백과의 "Five color theorem" 문서에도 이 증명이 적혀 있다.
  2. "하늘책의 증명"은 list coloring이라는 개념을 사용한다. 따라서 이 증명을 쓰려면 list coloring을 정의해야 하고, 그 외에도 그래프 이론을 아예 모르는 사람에게 소개하기에는 준비 과정이 조금 복잡하다고 판단하였다.
  3. "하늘책의 증명"은 매우 간결하고 아름답지만, 이것을 코딩으로 옮기기는 어렵다. Triangulation을 하는 과정, outer face와 인접한 사이클을 찾는 과정, chord를 찾은 뒤 그래프를 분리하는 과정 등 구현하기 복잡한 과정이 많다. 늘 그렇듯이 수학적으로 아름다운 것과 알고리즘적으로 아름다운 것에는 차이가 있을 수 있는 법이다. 우리가 소개할 증명도 충분히 간결하고 아름다우며, 구현 방법도 직관적으로 떠올릴 수 있다는 장점이 있다.
  4. "하늘책의 증명" 책에 이 증명이 있는 줄 알았는데, 다 쓰고 보니 아니었다.

아래 정리에서 그래프는 모두 단순 그래프라고 가정하겠다. 즉 양 끝점이 같은 간선은 없으며, 같은 쌍의 정점을 연결하는 두 간선도 없다. 우선 평면 그래프에 대한 오일러 공식을 소개한다.

정리 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 이하인 정수이다.

위치가 중복되는 점은 없고, 양 끝점이 같은 간선은 없으며, 같은 쌍의 정점을 연결하는 두 간선도 없다.

출력

총 M개의 숫자를 공백 없이 출력한다. x번째 숫자는 x번째 정점에 부여한 숫자이다. 여러 가지 방법이 있을 경우 그 중 한 방법만 출력하면 된다.

예제 입력 1

3 3
0 0
2 0
1 1
1 2
2 3
3 1

예제 출력 1

123

출처

Contest > 구데기컵 > 진짜 구데기컵 2018 🌈번

채점

  • 소스 코드의 크기는 1000B을 넘을 수 없다.