나라 수
경계
사용한 색
충돌

4색 정리에 대해 더보기

4색 정리 지도 칠하기

지도가 아무리 복잡해도, 경계를 공유하는 나라끼리 같은 색이 되지 않게 칠하는 데는 네 가지 색이면 항상 충분합니다. 아이가 크레용으로 확인해 볼 수 있을 만큼 단순한 명제이지만, 이를 증명하는 데는 한 세기가 넘는 시간과 컴퓨터가 필요했습니다. 무작위 지도를 직접 칠하며 어느 경계가 충돌하는지 확인한 다음, 세 가지 방법이 지도를 칠하는 모습을 지켜보세요. 가끔 다섯 번째 색이 필요한 빠른 탐욕 규칙부터 항상 네 가지 색으로 해내는 백트래킹 탐색까지 있습니다. 색을 고르고 나라를 클릭해 칠하세요. 이웃한 두 나라가 같은 색이면 그 경계가 빨갛게 변합니다. 모서리에서만 맞닿은 나라끼리는 같은 색이어도 됩니다. 컴퓨터에 맡길 수도 있습니다. 방법을 고르고 '풀기'를 누르면 전 과정을 지켜볼 수 있고, '한 단계'를 누르면 한 수씩 따라갈 수 있습니다. '최소 색 수'는 이 지도가 세 가지, 혹은 두 가지 색만으로도 충분한지 확인합니다. '새 지도'는 다른 지도를 그리고, '이웃 관계 보기'는 경계를 공유하는 나라들의 네트워크를 그립니다.

작동 원리

  1. 나라 수를 고르고 '새 지도'를 누르거나, 지금 보이는 지도로 시작하세요.
  2. 색을 고르고 나라를 클릭해 칠하면서, 이웃끼리 충돌하는 곳에 나타나는 빨간 경계를 살펴보세요.
  3. 방법을 고르고 '풀기'나 '한 단계'를 눌러 지도가 칠해지는 모습을 지켜보고, '최소 색 수'를 눌러 이 지도에 몇 가지 색이 필요한지 확인하세요.

지도에서 그래프로

나라마다 점을 하나씩 찍고, 두 나라가 경계를 공유하면 두 점을 잇습니다. 그러면 지도는 그래프가 되고, 지도를 칠하는 것은 이어진 점끼리 색이 다르도록 점을 칠하는 것과 같아집니다. 지도는 평평한 종이 위에 그려지므로 이 그래프들은 평면 그래프, 즉 선이 교차하지 않게 그릴 수 있는 그래프입니다. 모서리에서 만나는 정사각형 네 개처럼 한 점에서만 만나는 나라는 이웃이 아닙니다. 4색 정리는 모든 평면 그래프를 네 가지 색으로 칠할 수 있다고 말합니다. '이웃 관계 보기'를 켜면 현재 지도의 그래프를 볼 수 있습니다.

세 가지 색칠 방법

탐욕 색칠은 이웃이 많은 나라부터 하나씩 차례로 골라, 이웃들이 아직 쓰지 않은 첫 번째 색을 줍니다. 빠르지만 근시안적이어서, 어떤 지도에서는 다섯 번째나 여섯 번째 색까지 꺼내 듭니다. 1979년 다니엘 브렐라즈가 고안한 DSATUR는 이웃에 이미 가장 많은 서로 다른 색이 나타난 나라를 항상 다음 차례로 골라, 대개 그런 함정을 피합니다. 백트래킹은 색을 차례로 시도하다가 어떤 나라에 남은 색이 없으면 가장 최근의 선택을 되돌리고 다시 시도합니다. 때로는 여러 번 되돌아간 끝에, 항상 네 가지 색으로 칠하는 방법을 찾아냅니다.

자주 묻는 질문

왜 네 가지 색이면 항상 충분한가요?

짧은 이유를 찾은 사람은 아직 없습니다. 1976년 케네스 아펠과 볼프강 하켄의 증명은 모든 지도가 1,936개의 작은 배치 중 하나를 반드시 포함하며, 각 배치는 제거했다가 나중에 색칠을 복원할 수 있음을 보였습니다. 이들을 모두 검사하는 데 컴퓨터로 천 시간이 넘게 걸렸습니다. 1996년 닐 로버트슨, 대니얼 샌더스, 폴 시모어, 로빈 토머스가 내놓은 더 간단한 컴퓨터 증명은 633개의 배치만 필요하며, 2005년 조르주 곤티어는 증명 보조기 Coq로 증명을 완전히 검증했습니다.

네 가지 색이 모두 필요한 지도도 있나요?

네. 한 나라를 다른 세 나라가 고리처럼 둘러싼 경우처럼, 네 나라가 각각 나머지 세 나라와 모두 맞닿아 있으면 네 가지 색이 필요합니다. 하지만 많은 지도는 세 가지 색으로 충분하며, '최소 색 수'로 화면의 지도가 어떤지 알아볼 수 있습니다. 네 가지 색이면 항상 충분한데도, 일반적으로 어떤 지도를 세 가지 색으로 칠할 수 있는지 판정하는 것은 NP-완전인 어려운 문제입니다.

탐욕법은 왜 가끔 다섯 가지 색을 쓰나요?

탐욕법은 각 나라를 한 번만 칠하고 결코 마음을 바꾸지 않습니다. 앞선 선택 때문에 나중의 나라가 네 가지 색 모두에 둘러싸일 수 있고, 그러면 다섯 번째 색을 쓰는 수밖에 없습니다. 백트래킹이라면 대신 되돌아가서 앞의 선택을 바꿉니다.

다른 곡면에서도 정리가 성립하나요?

구면에서는 성립합니다. 구면은 평면과 같기 때문입니다. 도넛 표면인 원환면(토러스)에서는 일곱 가지 색이 필요한 지도가 있으며, 퍼시 히우드가 보였듯이 일곱 가지 색이면 항상 충분합니다. 식민지를 거느린 국가처럼 한 나라가 떨어진 여러 조각으로 이루어질 수 있다면, 네 가지 색으로는 더 이상 충분하지 않습니다.

서버로 전송되는 것이 있나요?

아니요. 지도, 색칠 방법, 검사는 모두 브라우저 안에서 실행됩니다. 설정은 이 브라우저의 로컬 저장소에 남습니다.

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

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

편집기로 이동