4색정리

이산수학 Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"	이론
<colbgcolor=#3CC> 기본 대상	수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타	P-NP 문제^미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서	논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학	}}}}}}}}}

1. 개요2. 증명 역사

2.1. 초기2.2. 컴퓨터를 사용해 증명

3. 의의4. 실제 지도에서는?5. 여담

1. 개요

四色定理 / four color theorem

지도 위의 모든 나라를 색칠하는데, 인접한 나라끼리 색이 겹치지 않게끔 칠하려면 4가지 색만으로도 충분한지를 따지는 문제다. 하켄과 아펠에 의해 참[1]으로 증명됐다.

위상수학과 관련된 문제이다. 4색 지도, 4색 증명 등으로도 불린다. 다만 전제 조건이 있는데, 해당 지도가 위상수학적으로 구면과 같아야 한다.[2] 만약 지도가 원환면과 위상동형인 경우는 최소 7색이 필요하다는게 증명되어 있다.

2. 증명 역사

2.1. 초기

앞선 시기에 독일의 수학자 뫼비우스가 4색 문제를 먼저 거론했다는 기록이 있지만, 이 문제를 본격적으로 연구한 사람은 프란시스 구스리라는것이 정설이다.

1852년 영국의 식물학자 프란시스 구스리(Fransis Guthrie)는 영국 지도를 구획 별로 색칠하던 중 4가지 색만 있으면 인접한 지역끼리 서로 겹치지 않게 칠할 수 있다는 것을 깨닫고는, 다른 모든 지도의 경우에도 그러한지 궁금해했다. 프란시스의 동생 프레드릭은 형에게 들은 지도와 4가지 색에 대한 이야기를 저명한 수학자 오거스터스 드 모르간에게 물었는데, 이후 드모르간 본인을 포함하여 수많은 수학자들이 4색 문제에 뛰어들었다. 이 과정에서 드 모르간은 6색 정리를 증명했다.

다른 난제들과 달리 어린아이도 이해할 수 있는 간단한 문제라서, 별 거 아닐거라 얕보고 일반인이고 전문가고 자신만만하게 증명을 시도했다가 낭패를 보는 일이 많았다. 특히 수학자중엔 반평생동안 이 문제에만 줄창 매달렸다가 결국 나가떨어지는 경우도 많았다.

4색 문제를 자신이 해결했다는 사람은 많았으나 대부분은 엉터리였고, 수학자들조차도 한동안 부분적, 간접적 증명에서 더 이상 발을 떼지 못했다.

1879년 알프레드 켐프(Alfred Kempe)가 신박한 증명을 내놓으면서 4색 문제에 종지부를 찍는 듯 보였지만, 11년 뒤에 증명 과정의 오류가 밝혀지며 다시 원점으로 돌아오는 일도 있었다. 이 오류를 밝힌 퍼시 히우드(Percy Heawood)는 켐프의 정리를 손질하여 5색으로는 어떠한 지도라도 색칠이 가능하다는 5색 정리를 증명하는 데 성공한다.

2.2. 컴퓨터를 사용해 증명

1960년대 독일의 헤쉬(Heinrich Heesch)는 '컴퓨터를 이용해 이 문제를 증명한다.'는 당시로서 아주 획기적인 발상을 하였다. 이에 헤쉬는 증명에 필요한 컴퓨터를 구하기 위해 독일과 미국을 동분서주하며 기초이론을 세웠지만, 패전한 서독의 경제사정 탓이었는지 연구 자금이 부족해 결국 연구를 그만두고 만다. 헤쉬는 모든 지도들을 유한 개의 유형으로 분류하는 획기적 성과를 거두었으나, 그럼에도 경우의 수는 거의 9천 개에 가까웠고, 당시 컴퓨터 성능으로는 이 모든 경우를 시뮬레이션하는 데 10년이 넘게 걸릴 거라 예상되면서 포기했다고 한다.

1976년 미국 일리노이 대학교의 볼프강 하켄(Wolfgang Haken), 케네스 아펠(Kenneth Appel)이 헤쉬의 아이디어를 바탕으로 컴퓨터 두 대를 50여 일 가량 돌린 끝에 증명에 성공했다.

이들이 채택한 방법은 컴퓨터를 이용해서 가능한 모든 경우의 지도 모델을 뽑고, 거기에 4색 정리가 적용되는지 안 되는지를 가려보자는 것이다. 컴퓨터를 사용한 브루트 포스이다. 모든 계산이 끝난 뒤에 반례가 하나도 나오지 않는다면 4색 정리는 증명되고, 반례가 나오더라도 그 자체로 4색 정리는 거짓이라고 밝혀져서 4색 문제가 해결되는 매우 간단한 방법이었다. 공식이나 법칙을 모를 때 모든 경우에 대해 직접 쓰거나 그려서 문제를 푸는 것과 근본적으로는 동일하다.

앞서 헤쉬가 기초 이론을 세우던 과정에서 검토해야 할 지도의 모델은 9천 개 정도였지만, 하켄과 아펠은 모델을 더욱 단순화시켜 1936개까지 줄였다.[3] 하켄과 아펠은 여기에 487가지 판별 필터를 걸고 컴퓨터 2대를 따로 돌려서 같은 결과가 나옴을 확인한 다음, 컴퓨터로 계산한 자료를 (고등학생, 대학생이던) 자기 아들, 딸에게 직접 축소된 부분을 칠하도록 해 증명했다. 이 때문에 타 논문이었으면 연구비를 지원한 기관에 감사하다는 내용을 썼을 테지만, 이 논문의 첫 시작은 자녀들에게 감사하다는 내용이었다.

이렇다보니 증명 결과만 몇 박스에 달했고, 여러 수학자들 앞에서 멋지게 수식을 휘날리며 결론을 도출한 뒤 과정에 오류가 없음을 확인받는 기존의 증명과 달리 '컴퓨터로 계산해서 빼먹은 것 없는지 확인 다 했고, 그 결과물이 이거다.' 하며 종이 몇 박스를 들이미는 식이라 여러 수학자들에게 아름답지 못한 증명이라고 까였다.[4][5] 거기에 최초로 컴퓨터를 사용한 증명이라는 점 역시 인간이 검증할 수 없다는 이유로 기존 수학자들이 반감을 품었다. 실제로 당시 기록들을 살펴보면, '검토 결과 그들의 증명 과정에서 오류가 없음은 반박할 수 없는 사실이지만, 그래도 컴퓨터를 가지고 이런 무식한 방법으로 증명했다는 점에서 까여야 함.'하며 비판하는 경우가 많았다. 그리고 ' 하늘책의 증명'에도 4색 정리는 빠져 있고, '5색 정리'가 수록되어 있다.

누구나 다 컴퓨터를 가지고 있고 컴퓨터의 속도가 비약적으로 증가해 이 정도 계산은 몇 초도 지나지 않아 끝나는 오늘날에는 '까짓 거 소스 코드 좀 짜고 실행 버튼 누르면 끝이니 수학을 잘 알지 못해도 하겠네.' 생각할 수 있다. 그러나 하켄과 아펠은 수 년에 걸쳐 이론을 가다듬고 계산과정을 최적화하는 데 공을 들였으며, 계산을 수행할 컴퓨터와 연구에 필요한 자금을 얻기 위해 노력했다. 1200여 시간 동안 하드를 불태우며 작업을 수행한 것은 컴퓨터지만, 컴퓨터가 계산을 하도록 모델의 숫자를 줄이고[6] 모든 준비와 검토, 발표를 담당한 하켄과 아펠의 공로를 무시해서는 안 된다.

3. 의의

수많은 수학 난제들이 그러하듯 사실 정리의 증명 자체는 크게 실용성이 없었다.[7] 지도 색칠은 색을 적게 쓰는 것보다는 알아보기 편하도록 적재적소에 알맞은 색을 쓰는 것이 중요하기 때문이다.

그러나 그 과정에서 나온 수많은 중간 결과물들이 다른 난제를 푸는 데 도움이 되거나 새로운 난제를 낳았다. 먼저 이 문제를 통해 위상수학과 그래프 이론이 한층 더 발전할 수 있었다. 실제로 위상수학을 통해 5개 이상 영역이 완전그래프를 이루지 않으면 4색 채색이 충분히 가능함을 증명했고, 역으로 완전그래프를 이루는 꼭지점(영역)의 최대 개수만큼 색상 수를 선택해야 모든 영역을 같은 색상이 인접하지 않도록 그릴 수 있음도 증명했다.[8]

또 복잡한 계산이나 모델화, 검증과 같은 증명 과정에 컴퓨터를 사용하는 것이 일반화하여 이제 컴퓨터는 수학과 뗄 수 없는 도구가 되었다.

4. 실제 지도에서는?

당연하지만, 실제 지도 채색에 이 정리를 쓸 일은 없다. 애초에 지도의 목적은 보는 사람이 알아보기가 쉽게 만드는 것이지, 색깔 아끼는 게 아니다. 본래의 목적을 제쳐두고 어떻게든 4색으로만 칠하려고 해도, 실제 지도에는 인접한 나라를 다른 색으로 칠하는 것 말고도 정상적인 지도라면 갖춰야 할 추가 조건이 있기 마련이다.

실제 지도라면 당연히 바다와 호수는 모두 같은 색으로 칠하고, 그 어떤 나라와도 다른 색깔로 칠할 것이다. 상식적으로 육지와 바다는 구별해야 할 것이 아닌가. 여기에서부터 이미 4색문제의 기본 조건과 어긋난다. 위의 세계지도는 바다와 호수에 5번째 색인 흰색을 사용하였다. 이 흰색은 다시 칠하여 없앨 수 있으나, 내륙 국가가 바다와 같은 색이 될 수도 있으며, 일부 호수와 바다의 색깔이 다를 수 있게 된다. 다만 아예 바다·호수가 존재하지 않는 지도라면 이 점은 문제가 되지 않는다.

한편 4색 정리의 기본 조건을 벗어나지 않는 점도 있다. 세계지도와 지구본은 원기둥과 구의 표면에 지도가 그려져 있지만, 동형의 2차원 평면 지도로 변형시킬 수 있다. 나라 하나를 제외하고 끄집어 펼쳐서 2차원 평면 지도로 만든 뒤에, 지도 전체의 외곽을 그 나라로 둘러 버리면 된다. 이런 조건의 지도를 의외로 실제로 자주 보게되는데, 남극대륙을 가장자리에 빙 두른 원판형 지도가 이에 해당한다.

월경지와 섬을 본토와 같은 색으로 그려야 하는 조건은 역시 지도 채색에 있어서 빈번하게 적용되는 제약사항이다. 위의 세계지도에서도 아제르바이잔의 나흐츠반, 러시아의 칼리닌그라드, 프랑스의 프랑스령 기아나와 같이 월경지는 본토와 같은 색으로 칠해져 있고, 프랑스와 네덜란드는 세인트마틴 섬에서 국경을 맞대고 있기 때문에 서로 다른 색으로 칠해져 있는 것을 볼 수 있다.

실제로 월경지로 인해 세계지도는 평면 그래프가 아니게 되는데, 앞서 언급한 아제르바이잔의 나흐츠반이 튀르키예와 인접해 있기 때문이다.

튀르키예는 조지아, 아제르바이잔, 이란과 접해있다.
아르메니아도 조지아, 아제르바이잔, 이란과 접해있다.
러시아도 조지아·아제르바이잔과 접해 있고, 이란과는 직접 접하지는 않지만 카자흐스탄과 투르크메니스탄을 거쳐서 갈 수 있다.

이 나라들이 이루는 그래프는 평면 그래프가 아니다 (K_3,3 완전이분그래프를 마이너로서 포함하는 그래프이기 때문).

그래도 위 그림을 보면 알겠지만 (바다와 호수를 제외하고) 세계지도를 4색으로 칠할 수는 있다. 이걸 4색정리로 설명하는 게 안 될 뿐. 실제로 아슬아슬하게 다섯가지 색을 칠해야 하는 경우를 피해간 경우도 있는데 폴란드와 리투아니아에 접하고 있는 러시아의 월경지인 칼리닌그라드의 존재로 인해 생기는 경우이다. 만약 폴란드와 라트비아가 발트 해를 통해 이어져 있었다면 폴란드·라트비아·리투아니아· 벨라루스·러시아는 서로 국경을 접해 완전그래프를 이루었을 것이다.

분쟁 지역을 중립적으로 그려야 한다는 조건도 드물지만 색칠을 방해하는 제약사항이다. 예를 들어 스프래틀리 군도처럼 여러 국가가 서로 자기네 땅이라 주장하는 영역을 중립적으로 그려야 하는 경우는 새로운 색상을 채택해야 한다. 다만 분쟁 지역을 (소유권을 주장 중인 국가들과 모두 인접한) 하나의 새로운 국가로 생각하면 되기 때문에, 이것만으로 4색칠이 불가능해지지는 않는다.

대한민국의 시군구 지도 역시 4색으로 칠할 수 없다. 달성군의 월경지로 인해 평면 그래프가 성립하지 않기 때문. #

5. 여담

해당 문제를 해결했던 볼프강 하켄과 케네스 아펠은 다음과 같은 말을 남겼다. #

어느 순간부터인가, 컴퓨터가 우리를 놀라게 하기 시작했습니다.
처음에 우리는 계산에 필요한 변수들을 일일이 손으로 입력하면서 작업을 했기 때문에 어떤 상황에서든 컴퓨터의 모든 동작을 미리 예견할 수 있었습니다.
그런데 갑자기 컴퓨터가 체스를 두는 로봇처럼 혼자서 돌아가기 시작한 것입니다. 컴퓨터는 자신이 '학습했던' 모든 방법들을 하나씩 적용해 나가면서 계산을 했고,
어떤 때는 사람보다도 현명한 판단을 내리곤 했습니다. 그 이후로 우리는 계산을 어떻게 진행해야 할지 컴퓨터에게 배우는 신세가 되었습니다.
어떤 면에서 볼 때 컴퓨터는 계산 능력뿐만 아니라 지적인 능력까지도 자신의 창조주인 인간을 능가하고 있었습니다.
- 사이먼 싱, '페르마의 마지막 정리(Fermat's last theorem)', 박병철 역, 영림카디널, p.399

로널드 그레이엄은 다음과 같은 말로 컴퓨터를 이용한 증명을 비판했다.

리만 가설이 맞는 것인지 컴퓨터에게 물어보았다고 합시다. 그런데 컴퓨터가 "네, 맞습니다. 그런데 그 이유를 설명한다 해도 당신은 이해하지 못할 것입니다."라 대답한다면, 이 얼마나 황당하고 기죽는 일이겠습니까? [9]
- 사이먼 싱, '페르마의 마지막 정리(Fermat's last theorem)', 박병철 역, 영림카디널, p.403

알파고(특히 알파고 vs 알파고)를 경험한 현대인의 입장에서 여러가지로 생각할 거리를 던져주는 말이다.

마틴 가드너는 1975년 4월 1일날 자신의 Mathematical Games 칼럼에 다음의 복잡한 지도가 4색 문제의 반례라고 했다. ( 보기) 물론 날짜를 보면 알듯이 만우절 낚시였다.

용의자 X의 헌신에 나오는 이시가미 데츠야가 더 '아름다운' 방법으로 증명하고 싶다는 문제가 이것이다.[10]

이걸 이제 상위 차원의 문제로 생각해볼 수도 있다. 하위 차원들로 분할된 [math(n)]차원 셀들을 인접하는 경우[11] 다른 색으로 최소 [math(f(n))]가지 수로 색칠할 때 이를 [math(n)]에 관한 식으로 표현할 수 있는가? 답은 불가능. 위키백과에 말없는 증명이 있는데, 글로 표현하자면 각 셀을 실처럼 길게 뽑아서 반으로 접으면 셀이 몇 개가 되더라도 각각이 서로 인접하게 만들 수 있으므로 색이 아무리 많아도 부족하다. #

이 정리를 응용한 퍼즐 게임도 몇 개 있다. Simon Tatham's Puzzles에는 'Map'이라는 이름으로 수록되어 있다.

[1] =인접한 나라끼리 색이 겹치지 않게 칠하는 것은, 4가지 색만으로도 충분하다. [2] 이는 국가를 점으로 나타내고 인접한 국가들끼리 변으로 연결했을 때 평면 그래프가 된다는 것과 동치이다. [3] 하켄-아펠 이후 사람들이 더 연구하여 지금은 이 모델을 633개까지 줄일 수 있다고 한다. [4] 간단히 비유하자면 '1부터 100까지 숫자 중 짝수는 몇 개가 있을까?'라는 문제가 있을 때, '어떤 수를 2로 나눈 몫은 그 수보다 작거나 같은 짝수의 갯수다. 따라서 100/2=50개다.'라는 답이 수학자들이 좋아하는 깔끔한 답이다. 하지만 이들이 낸 증명법은 2, 4, 6, 8... 100까지 짝수를 모조리 써갈긴다음 '다 쓰고 세어보니까 50개네요.'라고 하는 셈이었다. 당연히 싫어할만 하다. 실제로 중고등학교 수학시험 중에서는, 주관식 문제의 풀이과정이 무슨 공식을 쓴 게 아니라 이런 노가다식일 경우 감점하는 경우도 있다. 수학자들도 저 풀이법에서 문제점이나 오류를 찾지는 못했지만 '4색정리를 어떤 신박한 방식으로 풀어나갈 것이며, 그 과정에서 어떤 새로운 수학적 도구, 이론이 생겨날 것인가'라고 기대했다가 실망해서 비판한 것이다. 다만 4색정리의 문제점은 현재까지 알려진 바로는 후자의 방식의 풀이밖에 없다는 것... [5] 여기에 수학자들이 이런 풀이를 싫어했을 만한 것이 이런 중요한 문제들은 그 풀이 과정에서 새로운 수학 분야나 이론이 탄생하거나, 보충되거나 하는데, 아펠과 하켄의 증명에는 그럴 건덕지가 없었기 때문이다. [6] 앞서 설명했듯 기존에 9천개라고 알려져 있던 모델을 1936개까지 줄인 건 두 사람의 공로다. [7] 사실 컴퓨터 공학을 포함한 다양한 분야에서 4색정리와 관련된 내용들이 알게모르게 쓰이기는 한다(보통 이러한 문제를 Graph Coloring 문제라고 함). 몇가지 예시를 들자면 컴파일러에서 레지스터를 어떻게 효율적으로 할당할지를 정하는 문제가 이 문제와 관련이 있다. 그 외 실용적인 예시로는 시험 시간 배정, 택시 스케줄 문제 등과 같은 스케줄 배정 문제와 관련이 있다. #1 #2 [8] 꼭지점 5개가 완전그래프를 이루는 경우는 평면 그래프가 아니다. [9] 여담으로 리만 가설도 노가다성 증명 방법의 가능성이 제시된 상태이다. 다만 이 방법 자체가 개미 잡는데 미사일 쓰는 격인 수준이긴 하다. [10] 즉, 이시가미는 컴퓨터로 증명해낸 하켄과 아펠의 방법이 아닌 오로지 인간의 노력으로 증명해낸 답을 찾고 싶었다는 것. 그것이 그가 말하는 '아름다운 방법'이다. [11] 여기서는 '인접한다'의 기준을 두 셀이 [math(n-1)]차원으로 표현할 수 있는 형태로 만나는 것으로 정의한다. 예를 들어 두개의 3차원 셀이 특정 선에서 만나는 경우는 2차원 지도에서 한 점에서 만나는 경우와 같이 인접해있지 않는 경우로 취급한다.