4색 정리 해설

1852년, 잉글랜드의 주 지도를 칠하던 한 젊은 수학자는 이웃한 주들을 구별하는 데 네 가지 색이면 충분한 것 같다는 사실을 알아챘습니다. 이것은 가능한 모든 지도에 대해 참일까요? 이 질문은 수학에서 가장 유명한 문제 중 하나가 되었고, 11년 동안 인정받은 유명한 잘못된 증명을 낳았으며, 마침내 1976년에 해결되었습니다. 그 해결 방식은 수학자들이 무엇을 증명으로 받아들이는지를 바꾸어 놓았습니다.

이웃한 두 나라가 같은 색이 되지 않도록 네 가지 색으로 칠한, 불규칙한 모양의 나라들로 이루어진 지도
이웃한 두 나라가 같은 색이 되지 않도록 네 가지 색으로 칠한, 불규칙한 모양의 나라들로 이루어진 지도

질문

오거스터스 드모르간의 제자였던 프랜시스 거스리는 경계를 공유하는 나라끼리 서로 다른 색이 되도록 어떤 지도든 네 가지 색으로 칠할 수 있는지 물었습니다. 두 가지 규칙이 이 질문을 엄밀하게 만듭니다. 나라는 연결되어 있어야, 즉 각각 한 덩어리여야 하며, 한 점에서만 만나는 나라는 이웃으로 치지 않습니다. 세 가지 색이 항상 충분하지 않다는 것은 분명합니다. 서로 모두 맞닿은 세 나라가 고리처럼 둘러싼 나라에는 네 번째 색이 필요하기 때문입니다. 문제는 다섯 번째 색이 필요한 경우가 있느냐는 것입니다.

그래프로서의 지도

나라마다 점을 하나 찍고, 두 나라가 경계를 공유할 때마다 두 점 사이에 선을 긋습니다. 그 결과가 그래프이며, 지도가 평평한 종이 위에 있으므로 선들을 교차하지 않게 그을 수 있습니다. 즉 이 그래프는 평면 그래프입니다. 지도를 칠하는 것은 모든 변의 양 끝이 서로 다른 색이 되도록 이 그래프의 꼭짓점을 칠하는 것입니다. 이것이 가능한 최소 색 수를 채색수라고 하며, 4색 정리는 채색수가 4를 넘는 평면 그래프는 없다고 말합니다.

실패한 켐프의 증명

1879년 법정 변호사이자 수학자였던 앨프리드 켐프가 증명을 발표했습니다. 오늘날 켐프 체인이라고 불리는 그 기발한 아이디어는, 연결된 나라들의 사슬을 따라 두 색을 맞바꾸어 필요한 곳에 색 하나를 비워 주는 것입니다. 이 증명은 11년 동안 받아들여지다가 1890년 퍼시 히우드가 허점을 발견했습니다. 히우드의 보완으로 증명된 것은 다섯 가지 색이면 항상 충분하다는 더 약한 결과였습니다. 켐프 체인은 살아남아 마침내 완성된 증명의 도구가 되었습니다.

다섯 가지 색이 쉬운 이유

모든 평면 그래프에는 이웃이 다섯 개 이하인 꼭짓점이 있습니다. 이는 오일러 공식에서 나오며, 이 공식에 따르면 꼭짓점이 n개인 평면 그래프의 변은 많아야 3n − 6개입니다. 그런 꼭짓점을 제거하고 같은 논증으로 나머지 지도를 칠한 다음, 꼭짓점을 다시 넣습니다. 그 이웃들이 다섯 가지보다 적은 색을 쓰고 있으면 색 하나가 비어 있습니다. 다섯 가지를 모두 쓰고 있더라도 켐프 체인 맞바꾸기로 항상 하나를 비울 수 있습니다. 네 가지 색에서는 같은 맞바꾸기가 실패할 수 있는데, 이것이 바로 켐프가 놓친 허점입니다.

컴퓨터 증명

1976년 일리노이 대학교의 케네스 아펠과 볼프강 하켄이 이 정리를 증명했습니다. 이들은 모든 지도가 불가피 집합에 속한 1,936개의 배치 중 적어도 하나를 포함하며, 각 배치가 기약 가능하다는 것, 즉 다섯 가지 색이 필요한 가장 작은 지도는 그 배치를 포함할 수 없다는 것을 보였습니다. 기약 가능성을 확인하는 데 컴퓨터로 천 시간이 넘게 걸려, 손으로 검증하기에는 너무 방대했습니다. 많은 수학자가 아무도 전부 읽을 수 없는 증명을 불편하게 여겼고, 컴퓨터 보조 증명에 관한 논쟁이 시작되었습니다.

볼프강 하켄. 1976년 케네스 아펠과 함께 일리노이 대학교에서 네 색 정리를 증명했다.
볼프강 하켄. 1976년 케네스 아펠과 함께 일리노이 대학교에서 네 색 정리를 증명했다.

더 간단한 증명과 완전한 검증

1996년 닐 로버트슨, 대니얼 샌더스, 폴 시모어, 로빈 토머스가 633개의 배치로 이루어진 더 체계적인 증명을 발표했습니다. 여전히 컴퓨터로 확인하지만 검증하기는 더 쉽습니다. 2005년 조르주 곤티어와 뱅자맹 베르네는 증명 보조기 Coq로 증명 전체를 형식화하여, 작고 신뢰할 수 있는 프로그램이 모든 논리적 단계를 확인하게 했습니다. 오늘날 4색 정리는 수학에서 가장 철저하게 검증된 결과 중 하나입니다.

색칠 알고리즘

주어진 지도를 네 가지 색으로 칠하는 방법을 찾는 것은 실제로는 빠르지만, 일반적인 그래프에 필요한 최소 색 수를 찾는 것은 어렵습니다. 세 가지 색으로 충분한지 판정하는 문제는 NP-완전입니다. 실용적인 방법으로는 차수가 큰 순서대로 칠하는 탐욕 색칠, 가장 제약이 많은 꼭짓점을 다음에 칠하는 DSATUR, 그리고 선택을 탐색하다가 막히면 되돌리는 백트래킹 탐색이 있습니다. 그래프 색칠은 겹치지 않게 시험 일정을 짜고, 이웃한 송신기끼리 간섭하지 않도록 무선 주파수를 배정하며, 컴파일러에서 레지스터를 할당하는 데 쓰입니다.

직접 살펴보기

4색 정리 지도 칠하기를 열어 나라가 4개에서 120개인 지도를 만들고, 네 가지 색으로 직접 칠하며 충돌이 빨간색으로 나타나는 모습을 지켜보세요. 탐욕 색칠, DSATUR, 백트래킹이 지도를 한 단계씩 풀게 하고, 이웃한 나라들의 그래프를 표시하고, 지도에 실제로 필요한 최소 색 수를 확인해 보세요.

자주 묻는 질문

이 정리가 지도 제작자에게 도움이 되나요?

거의 그렇지 않습니다. 실제 지도는 보통 알아보기 쉽도록 더 많은 색으로 칠하며, 바다와 호수, 여러 조각으로 나뉜 나라도 들어 있는데, 이런 것들은 정리가 다루지 않습니다. 이 정리의 중요성은 수학적인 데 있습니다. 그래프 이론의 발전을 이끌었고, 무엇을 증명으로 볼 것인가라는 질문을 던졌습니다.

켐프 체인이란 무엇인가요?

두 가지 색, 예를 들어 빨강과 파랑을 정하고 빨간색으로 칠한 나라 하나를 고릅니다. 그 나라의 켐프 체인은 빨간색과 파란색 이웃만 거쳐서 그 나라로부터 도달할 수 있는 모든 빨간 나라와 파란 나라의 모임입니다. 체인 전체에서 빨강과 파랑을 맞바꾸어도 색칠은 올바르게 유지되며, 체인 옆에 있는 나라를 위해 색 하나를 비워 줄 수 있습니다.

여러 조각으로 된 나라는 왜 정리를 깨뜨리나요?

한 나라가 모두 같은 색이어야 하는 떨어진 여러 지역으로 이루어질 수 있다면, 이웃 관계 그래프는 더 이상 평면 그래프가 아니며, 더 많은 색이 필요한 지도를 만들 수 있습니다. 나라마다 두 조각일 때는 최대 12가지까지 몇 가지 색이든 필요한 지도를 만들 수 있으며, 히우드가 '제국 문제'에서 이를 연구했습니다.

이 도구는 왜 점으로 지도를 만드나요?

각 나라는 정사각형에서 어떤 무작위 점에 다른 어떤 점보다도 가까운 영역, 즉 보로노이 다이어그램입니다. 이렇게 하면 볼록한 나라들로 이루어진 실감 나는 지도가 만들어지며, 두 나라는 정확히 그 영역들이 경계의 한 구간을 공유할 때 이웃이 되는데, 앱은 이를 정밀하게 계산합니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

4색 정리 지도 칠하기 열기