4색 정리
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
4색 정리는 평면 지도를 칠하는 데 최대 4가지 색상만 필요하다는 정리이다. 1852년 프랜시스 구드리가 처음 발견했으며, 1976년 케네스 아펠과 볼프강 하켄에 의해 컴퓨터를 이용하여 증명되었다. 이 정리는 그래프 이론으로 표현되며, 모든 평면 그래프는 4-채색 가능하다는 것을 의미한다. 증명 과정은 삼각 분할, 켐페 체인, 환원 가능 구성, 불가피 집합, 방전법 등의 개념을 사용한다. 4색 정리는 지도 제작 외의 분야에서는 큰 영향을 미치지 않았으며, 실제 지도 제작에서는 색의 배분에 더 중점을 둔다.
더 읽어볼만한 페이지
- 그래프 색칠 - 채색 다항식
채색 다항식 는 그래프 ''G''를 ''k''개의 색으로 칠하는 방법의 수를 나타내는 다항식으로, 버코프가 4색 정리를 증명하기 위해 평면 그래프에 대해 처음 도입한 후 휘트니에 의해 일반 그래프로 확장되었으며, 그래프의 속성을 나타내고 계산 복잡도 이론에서 #P-난해 문제로 분류된다. - 그래프 색칠 - 비징의 정리
비징의 정리는 단순 무향 그래프의 변 색칠수가 최대 차수와 최대 차수+1 중 하나의 값을 가지며, 이를 기준으로 그래프를 1종과 2종으로 분류하는 그래프 이론의 정리이다. - 그래프 이론 정리 - 램지의 정리
램지의 정리는 주어진 조건을 만족하는 램지 수가 존재한다는 정리로, 그래프 이론으로 해석되며, 특정 크기의 동색 클릭이 존재함을 보장하고, 램지 이론의 시초로 여겨진다. - 그래프 이론 정리 - 최대 유량 최소 컷 정리
최대 유량 최소 컷 정리는 네트워크의 최대 유량과 최소 컷의 용량이 같다는 것을 나타내며, 포드-풀커슨 알고리즘으로 증명되고 다양한 실생활 문제 해결에 기여한다. - 평면 그래프 - 다듬은 정육면체
깎은 정육면체는 정육면체의 꼭짓점을 잘라 만든 다면체로, 6개의 정팔각형과 8개의 정삼각형으로 구성되고, 마름모 입방팔면체 등과 연관되며, 데카르트 좌표계와 트리보나치 수열로 꼭짓점 위치를 나타낼 수 있고, 키랄성 및 팔면체 대칭성을 가지며 여러 분야에 활용됩니다. - 평면 그래프 - 정이십면체
정이십면체는 20개의 정삼각형 면으로 이루어진 볼록 정다면체로, 정반오각기둥 양쪽에 정오각뿔을 붙인 형태이며, 정십이면체와 쌍대 관계를 가지고 다양한 분야에서 활용된다.
4색 정리 | |
---|---|
개요 | |
분야 | 그래프 이론 |
증명 방법 | 컴퓨터 보조 증명 |
관련 개념 | 그래프 채색, 평면 그래프 |
역사 | |
최초 제안 | 1852년, 프랜시스 거스리 |
최초 발표 | 1878년, 아서 케일리 |
오귀스투스 드 모르간의 언급 | 1852년 윌리엄 로원 해밀턴에게 편지 |
잘못된 증명 | 1879년, 알프레드 켐프 |
켐프의 증명 오류 발견 | 1890년, 퍼시 존 히우드 |
5색 정리 증명 | 1890년, 퍼시 존 히우드 |
컴퓨터 보조 증명 | 1976년, 케네스 아펠과 볼프강 하켄 |
증명 간소화 | 1997년, 닐 로버트슨, 대니얼 P. 샌더스, 폴 시모어, 로빈 토머스 |
형식적 증명 | 2005년, 조르주 공티에 |
내용 | |
내용 | 모든 평면 그래프는 4가지 색으로 채색할 수 있다. |
다른 표현 | 어떤 지도에서든, 인접한 영역이 같은 색을 공유하지 않도록 최대 4가지 색을 사용하여 모든 영역을 색칠할 수 있다. |
지도 제작과의 관계 | 지도의 영역을 평면 그래프의 정점으로, 인접한 영역 사이의 경계를 변으로 나타낼 수 있다. |
증명 | |
컴퓨터 보조 증명 | 증명은 컴퓨터를 사용하여 수행되었으며, 수학자와 철학자 모두에게 논란의 여지가 있다. |
간소화된 증명 | 1997년에 더 짧고 단순한 증명이 발견되었지만, 여전히 컴퓨터의 도움이 필요하다. |
형식적 증명 | 2005년에 정리 증명 보조 도구를 사용하여 정리의 형식적 증명이 생성되었다. |
일반화 및 관련 문제 | |
일반화 | 평면을 구, 원환면 및 기타 표면으로 일반화할 수 있다. |
관련 문제 | 헤이우드 수, 해피 엔딩 문제 |
2. 역사
1852년 프랜시스 구드리(Francis Guthrie)가 영국 지도를 색칠하면서 네 가지 색만으로도 충분하다는 것을 발견하고, 그의 스승인 드모르간에게 이 문제를 제기하면서 4색 문제의 역사가 시작되었다.
4색 정리는 1879년 아서 케일리의 논문에서 처음 학문적으로 논의되었다.[6] 이후 여러 수학자들이 증명을 시도했지만, 오랫동안 미해결 문제로 남아 있었다. 4색 정리는 지도 제작자들에게는 오랫동안 알려져 왔지만, 구드리가 처음으로 학문적인 문제로 제기한 것으로 알려져 있다.
2. 1. 초기 증명 시도
1852년 프랜시스 구드리(Francis Guthrie)가 영국의 지도를 색으로 칠해 구분하다가 네 가지 색만으로 각 주(州)를 구분할 수 있다는 것을 발견하고, 그의 스승인 드모르간에게 수학적 증명이 가능한지 문의하면서 4색 문제가 처음 연구되기 시작했다.[3][4] 4색 정리가 처음 학문적으로 논의된 것은 1879년 아서 케일리의 논문이었다.[6]1879년 알프레드 켐프(Alfred Kempe)가 4색 정리 증명을 발표하여 많은 사람들이 옳다고 생각했으나, 1890년 퍼시 히우드(Percy Heawood)에 의해 켐프의 증명에서 오류가 발견되었다.[7] 히우드는 켐프의 증명이 잘못되었음을 지적하고, 5색정리를 증명했다. 1880년 피터 테이트(Peter Tait)가 다른 방법으로 4색 정리를 증명하였으나, 1891년 율리우스 페터센(Julius Petersen)에 의해 테이트의 증명 역시 잘못되었다는 것이 밝혀졌다. 두 증명 모두 11년이 지나서야 오류가 발견되었다.
1976년 케네스 아펠과 볼프강 하켄은 하인리히 헤쉬(Heinrich Heesch)의 아이디어를 바탕으로 4색 정리를 증명하였다.
2. 2. 컴퓨터를 이용한 증명
1976년 일리노이 대학교 어바나-샴페인의 케네스 아펠과 볼프강 하켄은 하인리히 헤쉬의 아이디어를 발전시켜 컴퓨터를 이용해 4색 정리를 증명했다.[8] 아펠과 하켄의 증명은 '불가피 집합'과 '환원 가능 구성'이라는 두 가지 개념을 이용했다.[9]- 불가피 집합: 최소 비-4색칠 가능 삼각형이 되기 위한 몇 가지 필요 조건을 만족하는 모든 지도(예: 최소 차수 5)가 이 집합의 구성 요소를 적어도 하나 가져야 하는 구성 요소의 집합이다.
- 환원 가능 구성: 최소 반례에서 발생할 수 없는 국가들의 배열이다. 지도가 환원 가능한 구성을 포함하는 경우, 지도는 더 작은 지도로 줄일 수 있다. 이 더 작은 지도는 4가지 색으로 칠할 수 있다면 원래 지도에도 적용된다는 조건을 갖는다. 이는 원래 지도를 4가지 색으로 칠할 수 없는 경우 더 작은 지도도 칠할 수 없으며, 따라서 원래 지도가 최소가 아님을 의미한다.
아펠과 하켄은 수학적 규칙과 절차를 사용하여 환원 가능한 구성의 불가피한 집합을 발견하여, 4색 정리에 대한 최소 반례가 존재할 수 없음을 증명했다. 그들의 증명은 가능한 무한한 지도를 1,834개의 환원 가능한 구성(나중에 1,482개로 축소)으로 줄였으며, 이를 컴퓨터로 하나씩 확인해야 했고 1,000시간 이상이 걸렸다. 이 환원 가능성 부분은 다른 프로그램과 컴퓨터를 사용하여 독립적으로 이중 확인되었다. 그러나 증명의 불가피성 부분은 400페이지 이상의 마이크로피시로 확인되었으며, 하켄의 딸 도로테아 블로스타인의 도움을 받아 손으로 확인해야 했다.
아펠과 하켄의 발표는 전 세계 언론에 광범위하게 보도되었으며, 일리노이 대학교 수학과는 "네 가지 색으로 충분하다"라고 명시된 소인(postmark)을 사용했다. 동시에 증명의 특이성—광범위한 컴퓨터 지원으로 증명된 최초의 주요 정리였다는 점—과 인간이 확인할 수 있는 부분의 복잡성은 상당한 논란을 불러일으켰다.
1996년 닐 로버트슨, 다니엘 P. 샌더스, 폴 세이모어, 로빈 토마스는 더 효율적인 알고리즘을 사용한 새로운 증명을 제시했다.[10] 이 증명은 633개의 환원 가능한 구성만 확인하면 되었고, 불가피성 및 환원 가능성 부분 모두 컴퓨터로 실행되어 손으로 확인하는 것은 비실용적이었다.
2005년 벤자민 베르너와 조르주 콩티에는 콕 증명 보조 도구를 사용하여 정리의 증명을 형식화했다. 이것은 특정 경우를 검증하는 데 사용된 다양한 컴퓨터 프로그램을 신뢰할 필요성을 없앴으며, 단지 콕 커널만을 신뢰하면 된다.
3. 이론적 표현
4색 정리는 그래프 이론을 사용하여 "모든 평면 그래프는 4색으로 칠할 수 있다"라는 명제로 표현할 수 있다. 지도의 각 구획은 그래프의 꼭짓점으로, 구획이 맞닿으면 꼭짓점을 선으로 연결하여 표현한다.[2]
좀 더 직관적으로 설명하자면, "평면을 인접한 영역으로 분할했을 때, 인접한 두 영역이 같은 색을 갖지 않도록 최대 4가지 색으로 영역을 칠할 수 있다"는 것이다. 여기서 '인접'은 경계선의 일부를 공유하는 경우를 의미하며, 점만 공유하는 경우는 해당하지 않는다.
그래프 이론적으로는 루프가 없는 평면 그래프 의 채색수 임을 나타낸다. 즉, 모든 평면 그래프는 4-채색 가능하다.
하지만, 월경지와 같이 한 국가의 영토가 여러 곳으로 분리되어 있는 경우에는 4가지 색만으로는 부족할 수 있다. 예를 들어, 아래 지도에서 A로 표시된 두 영역이 같은 국가에 속한다면, 5가지 색이 필요하다.
3. 1. 3색 문제
모든 평면 지도는 네 가지 색으로 칠할 수 있지만, 임의의 평면 지도를 단 세 가지 색으로 칠할 수 있는지 결정하는 것은 NP-완전 문제(NP-complete)이다.[12]
정규 지도는 각 내부 영역이 짝수 개의 인접 영역을 가질 경우에만 세 가지 색으로 칠할 수 있다.[13] 미국 주 지도에서 내륙 주 미주리(MO)는 8개의 이웃을 가지고 있어(짝수) 미주리는 이웃과 모두 다른 색으로 칠해야 하지만, 이웃들은 색상을 교대로 사용할 수 있으므로 이 부분에는 세 가지 색만 필요하다. 그러나 내륙 주 네바다(NV)는 5개의 이웃을 가지고 있어(홀수) 이웃들은 세 가지 색을 필요로 하고, 네바다는 이들과 다른 색으로 칠해야 하므로 네 가지 색이 필요하다.
지도 G가 주어졌을 때, G를 3가지 색으로 칠할 수 있는지 결정하는 문제를 '''3채색 문제'''라고 한다. 사색 문제와 마찬가지로 인접한 지역은 같은 색으로 칠할 수 없다. 3채색 문제는 NP 완전 문제 중 하나로 알려져 있다.
4. 지도와 4색 정리의 관계
프랜시스 구드리가 지도를 보면서 4색 문제에 대한 연구를 시작했지만, 실제 지도와 4색 정리는 큰 연관이 없다. 케네스 메이(Kenneth May)에 따르면, 학자들이 미국 의회도서관의 지도를 분석한 결과 지도 제작에서 색을 최소한으로 사용하려는 노력은 별로 보이지 않는다고 한다.[2] 구획을 구분하는 것 외에도 색으로 구분하는 경우가 종종 있고, 대부분의 지도는 다섯 가지 이상의 색으로 구획을 구분한다. 실제로 네 가지 색을 사용한 경우는 네 가지보다 덜 쓰는 것도 가능한 경우가 많다.[2] 또한 실제 지도에서는 연못이나 호수도 그려야 하는데, 일반적으로 연못은 모두 같은 색으로 칠해야 하기 때문에 사색문제의 기본 조건에 어긋난다. 월경지가 존재하는 경우 역시 해당 월경지를 가지고 있는 국가나 행정 구역과 같은 색으로 칠해야 하기 때문에 사색문제의 기본 조건에 어긋난다.
지도제작과 관련된 책에서는 4색 정리를 별도로 언급하지 않는다. 지도를 실제로 제작할 때는 색을 칠하는 것이 중요한 문제이기는 하지만, 색을 최소한으로 사용하는 것보다는 한 색이 너무 많이 쓰이지 않도록 적절히 배분하는 데 더 관심을 가질 뿐, 색을 네 가지를 사용하는지 다섯 가지를 사용하는지는 별로 주의를 기울이지 않는다.
국가의 정치 지도를 채색하려는 동기가 있었음에도 불구하고, 이 정리는 지도 제작자들에게 특별한 관심사가 아니다. 수학 역사가인 케네스 메이의 기사에 따르면, "네 가지 색만 사용하는 지도는 드물며, 그렇게 사용하는 경우에도 보통 세 가지 색만 필요하다. 지도 제작 및 지도 제작의 역사에 관한 책에서는 사색 정리를 언급하지 않는다."[2] 또한 이 정리는 동일한 국가의 비연속 지역(예: 알래스카와 나머지 미국)이 동일한 색상으로 칠해져야 한다는 일반 지도 제작 요구 사항을 보장하지 않는다.
5. 일반화
4색 정리는 평면뿐만 아니라 구, 원기둥과 같은 표면에서도 성립한다. 그래프 이론적으로 설명하면, 루프가 없는 평면 그래프의 채색수는 4 이하이다. 즉, 평면 그래프는 4개의 색으로 칠할 수 있다는 의미이다.
하지만, 4색 정리의 직관적인 표현인 "평면을 연속된 영역으로 분할했을 때, 인접한 두 영역이 같은 색을 가지지 않도록 최대 4개의 색을 사용하여 칠할 수 있다"는 올바르게 해석해야 한다. 예를 들어, 월경지처럼 특정 지역이 다른 지역에 둘러싸여 있는 경우, 같은 색을 칠하기 위해서는 4개 이상의 색이 필요할 수 있다.
이러한 경우를 그래프 이론으로 표현하면, "평면 그래프는 4채색 가능하다"라는 명제로 나타낼 수 있다. 또한, 경계선이 아닌 점만 공유하는 영역은 인접하지 않은 것으로 간주되어 같은 색으로 칠할 수 있다.
4색 정리는 3차원 이상의 공간에서는 성립하지 않는다. 3차원 이상에서는 영역을 어떻게 구성하느냐에 따라 필요한 색의 수가 무한히 커질 수 있다.
5. 1. 무한 그래프
4색 정리는 유한 평면 그래프뿐만 아니라 평면에서 교차 없이 그릴 수 있는 무한 그래프에도 적용되며, 더 일반적으로는 모든 유한 부분 그래프가 평면 그래프인 무한 그래프(무한 개의 정점을 가질 수 있음)에도 적용된다. 이를 증명하기 위해 유한 평면 그래프에 대한 정리의 증명과, 무한 그래프의 모든 유한 부분 그래프가 ''k''-채색 가능하면 전체 그래프도 ''k''-채색 가능하다는 것을 나타내는 드 브루인-에르되스 정리를 결합할 수 있다. 이는 또한 무한 그래프의 채색 가능성을 일련의 논리적 공식으로 표현함으로써 쿠르트 괴델의 1차 논리에 대한 콤팩트성 정리의 직접적인 결과로도 볼 수 있다.5. 2. 고차원 표면
P. J. Heawood가 1890년에 제안하고, 1968년 Gerhard Ringel과 J. W. T. Youngs가 증명한 바에 따르면, 양의 종수를 갖는 닫힌 (가향 또는 비가향) 곡면에서 필요한 최대 색상 수 ''p''는 곡면의 오일러 지표 χ에 따라 다음과 같이 결정된다.[21]:
여기서 는 바닥 함수를 나타낸다.
가향 곡면의 경우, 위 공식은 곡면의 종수 ''g''를 사용하여 다음과 같이 표현할 수 있다.
:
이 공식의 유일한 예외는 클라인 병인데, 오일러 지표가 0 (따라서 공식은 p = 7을 제공)이지만 1934년 Philip Franklin에 의해 6가지 색상만 필요하다는 것이 밝혀졌다.
예를 들어, 토러스는 오일러 지표 χ = 0 (및 종수 ''g'' = 1)을 가지므로 ''p'' = 7이며, 따라서 토러스에서 어떤 지도에도 7가지 이상의 색상이 필요하지 않다. 이 상한 7은 최대치이다. Szilassi 다면체와 같은 특정 토로이드 다면체는 7가지 색상이 필요하다.
뫼비우스 띠는 6가지 색상이 필요하며, 1-평면 그래프 (각 변마다 교차가 최대 하나 있는 그래프)도 마찬가지이다. 평면 그래프의 정점과 면을 모두 색칠하여 인접한 정점, 면 또는 정점-면 쌍이 같은 색상을 갖지 않도록 하면, 다시 6가지 색상이 필요하다.
6. 증명 아이디어 요약
알프레드 켐페가 1879년에 제시한 4색 정리 증명은 널리 알려졌지만, 1890년에 퍼시 히우드에 의해 오류가 발견되었다. 하지만 켐페의 증명은 이후 증명에 사용된 몇 가지 기본 개념을 제공했다는 점에서 의미가 있다.
켐페의 증명은 다음과 같은 주요 개념들을 사용한다.
- 삼각 분할: 평면 그래프의 모든 영역이 삼각형이 되도록 변을 추가하는 기법.
- 켐페 체인: 그래프에서 두 가지 색으로 번갈아 칠해진 경로.
- 환원 가능 구성: 어떤 부분 그래프를 제거하고 남은 그래프를 4색으로 칠할 수 있다면, 전체 그래프도 4색으로 칠할 수 있는 부분 그래프.
- 불가피 집합: 어떤 평면 그래프를 가져오더라도, 그 집합에 속하는 그래프 중 하나가 부분 그래프로 포함되는 그래프의 집합.
- 방전법: 평면 그래프를 전기 회로망으로 간주하여 전하를 재분배하는 방식으로 불가피 집합을 찾는 방법.
켐페는 먼저 평면 그래프가 삼각 분할되어 있다고 가정한다. 그리고 오일러 공식을 이용하여 차수가 5 이하인 정점이 적어도 하나 존재함을 보인다. 차수가 3 이하인 정점이나 4인 정점은 제거한 후 다시 추가해도 4색 채색이 가능함을 보였다. 하지만 차수가 5인 정점에 대한 증명에는 오류가 있었다.
이후 1976년에 케네스 아펠과 볼프강 하켄은 하인리히 헤쉬가 제안한 방전법을 발전시켜 컴퓨터를 이용해 4색 정리를 증명하였다. 이들은 환원 가능한 구성들의 불가피 집합을 찾아내어, 4색 정리에 대한 반례가 존재할 수 없음을 보였다.
7. 수학 외적 응용
국가의 정치 지도 채색에 대한 동기가 있었음에도 불구하고, 4색 정리는 지도 제작자들에게 특별한 관심사가 아니다. 수학 역사가인 케네스 메이의 기사에 따르면, "네 가지 색만 사용하는 지도는 드물며, 그렇게 사용하는 경우에도 보통 세 가지 색만 필요하다. 지도 제작 및 지도 제작의 역사에 관한 책에서는 4색 정리를 언급하지 않는다." 또한 이 정리는 동일한 국가의 비연속 지역(예: 알래스카와 나머지 미국)이 동일한 색상으로 칠해져야 한다는 일반적인 지도 제작 요구 사항을 보장하지 않는다. 4색 정리는 지도상의 지역이 연속되지 않을 때 적용되지 않기 때문에 세계 지도에도 적용되지 않는다. 세계 지도에서 네덜란드는 생마르탱 섬에서 프랑스와 접하고 있기 때문에 대서양, 벨기에, 독일, 네덜란드, 프랑스는 모두 서로 접경하고 있다.
8. 4색 문제와 농담
1975년, 4색 정리가 해결되기 직전에 한 해프닝이 있었다. 수학 퍼즐로 유명한 마틴 가드너는 『사이언티픽 아메리칸』의 연재 칼럼 "Mathematical Games"에서, 이것이 4색 문제의 반례라고 주장하는(5색이 필요하다고 주장하는) 경계 그림을 실었다[22][23][24]。
「어째서인지 세상의 주목을 받지 못한 6가지 충격적인 발견」이라는 제목의 '''4월호''' 기사는 사실 만우절 농담이었고, 다른 내용 또한 라마누잔 상수(거의 정수#라마누잔의 상수 참조) 등, 보기에는 깜짝 놀랄 수학적 농담이었다. 그리고 "4색 문제의 반례"는, 사실 맥그리거에 의한 수학 퍼즐 문제로, 4색으로 칠하는 것이 언뜻 불가능해 보이지만, 실제로 칠해보면 그렇게 어렵지 않게 풀 수 있다. 어느 정도는 푸는 사람의 시행착오가 요구되며, 운의 요소도 있다. 그래서 칠을 할 수 있었다는 편지가 1,000통 이상이나 왔다고 한다[24][25]。
참조
[1]
인용
[2]
인용
[3]
인용
Graph Theory, 1736–1936
Oxford University Press
[4]
서적
Mechanizing Proof: Computing, Risk, and Trust
MIT Press
[5]
인용
[6]
간행물
The Philosophy of Discovery, Chapters Historical and Critical. By W. Whewell.
1860-04-14
[7]
서적
The Four Color Theorem
Macmillan
[8]
서적
Graphs & Digraphs
CRC Press
[9]
인용
[10]
인용
[11]
인용
[12]
간행물
Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
[13]
간행물
Quo Vadis, Graph Theory?
North-Holland
[14]
간행물
Graph Theory: Favorite Conjectures and Open Problems, II
Springer International Publishing
[15]
인용
[16]
논문
Every planar map is four colorable
1976-09
[17]
논문
Every planar map is four colorable. Part II: Reducibility
[18]
논문
Every Planar Map is Four Colorable
[19]
논문
A new proof of the four-colour theorem
1996-08
[20]
논문
A computer-checked proof of the Four Colour Theorem
http://www2.tcs.ifi.[...]
Microsoft Research Cambridge
[21]
웹사이트
Map Coloring
https://mathworld.wo[...]
[22]
인용
[23]
인용
[24]
인용
[25]
웹사이트
McGregor Map
https://mathworld.wo[...]
[26]
웹인용
math.gatech.edu Four Color
http://www.math.gate[...]
2006-02-02
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com