지도를 서로 다른 색으로 칠하려면?

백과사전 상세 본문

지도를 서로 다른 색으로 칠하려면?

다른 표기 언어

툴바 메뉴

폰트확대|
폰트축소|
공유하기|
인쇄 미리보기|
오류 수정 문의

요약 테이블
분야	함수와 규칙성
교과단원	초등 6학년 〈문제해결 방법 찾기〉, 고등 1학년 〈경우의 수〉

4색 문제

1852년 영국의 프랜시스 거스리(Francis Guthrie)는 영국 지도에 있는 지역들을 구분하여 색칠하는 데 몇 가지 색이면 충분한지 연구했습니다. 프랜시스는 4가지 색이면 지도를 색칠할 수 있다는 것을 알았지만 왜 4가지 색이면 가능한지 그 이유는 몰랐어요. 처음 수학자들은 4색 문제^각주1) 를 쉽게 해결할 수 있는 아주 쉬운 증명 문제쯤으로 생각했었다고 하네요. 하지만 이 문제는 그 후 120년 동안 많은 수학자의 노력에도 풀리지 않았어요.

4색 문제는 1976년 미국 일리노이 대학의 케네스 아펠(Kenneth Appel)과 볼프강 하켄(Wolfgang Haken)이 컴퓨터를 이용하여 증명해 냈습니다. 컴퓨터로 4색 문제를 해결하는 데 무려 1200시간이나 걸렸다고 하니 증명치고는 꽤나 복잡한 증명이지요. 그래서 5색이 필요한 지도나 4색 문제에 대한 간단한 증명이 나오길 바라는 수학자들도 있다고 합니다.

4색 문제의 증명을 기념하여 만든 우체국 소인

컴퓨터는 어떻게 증명했을까요?

컴퓨터는 어떤 방법으로 4색 문제를 증명했을까요? 4색 문제를 컴퓨터를 이용하여 증명할 것을 처음으로 생각해 낸 사람은 힐베르트의 제자인 하인리히 헤슈(Heinrich Heesch)라는 수학자입니다. 헤슈는 미국을 방문하여 여러 수학자들과 4색 문제를 증명하기 위한 아이디어를 논의했습니다. 그러나 안타깝게도 독일 정부의 지원을 받지 못하여 결국 포기하고 아펠과 하켄이 증명하게 됩니다.

헤슈는 평면에 그릴 수 있는 모든 지도를 대표할 수 있는 지도를 찾기로 하였습니다.

모든 꼭짓점마다 모서리가 3개인 지도를 4색으로 칠할 수 있다면 임의의 지도를 4색으로 칠할 수 있다고 가정했어요. 그리고 모서리와 면의 개수를 줄이는 방법을 선택하였습니다. 그러나 일일이 따져야 할 경우가 너무 많았고, 확인하는 방법도 쉽지 않았습니다. 결국 487가지의 판별 규칙을 정해 컴퓨터로 직접 확인하는 방법을 택하였습니다. 당시 컴퓨터로 증명하는 데 50일이 걸렸습니다.

지도 색칠하기

서울 지도에서 행정구를 다른 색으로 칠하는 데 4가지 색이면 충분합니다. 직접 증명하는 것은 어렵지만 간단한 방법으로 몇 가지 색이 필요한지는 확인할 수 있습니다. 만약 5가지 색이 반드시 필요한 지도가 있다면 놀라운 발견을 한 것입니다.

4색 문제는 왼쪽부터 차례대로 색칠 대신 번호를 붙여 가며 확인합니다. 이웃한 구끼리는 다른 색이므로 번호를 달리해야 합니다. 1, 2, 3, 4의 숫자로 해결된다면 4가지 색이 필요한 것입니다. 경우에 따라 2가지 또는 3가지 색이 필요한 지도도 있습니다.

지구본에 색칠하기

지도는 직사각형 모양이지만 우리가 살고 있는 지구는 둥근 구면(공)입니다. 평면을 공처럼 둥글게 말면 구면이 됩니다. 평면에서 4가지 색으로 지도를 칠할 수 있으므로 구면에서도 4가지 색이면 충분합니다.

원환면(토러스, torus)에 색칠하기

물놀이 할 때 사용하는 튜브처럼 생긴 모양을 원환면이라고 한다. 이 원환면 위에 복잡한 지도가 그려져 있다고 할 때, 이웃한 지역을 구분하여 칠하려면 몇 가지 색이 필요할까요? 평면 위의 4색 문제보다 복잡해 보이지만 이 문제는 수학자 퍼시 히우드(Percy Heawood)가 완전히 증명하였다. 원환면에 그려진 지도를 구분하여 색칠하는 데에는 7가지 색이 필요하다.