| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <bgcolor=#46786a> 이론 | |
| <colbgcolor=#46786a> 기본 대상 | 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 그래프 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오(예상과 확인) · 불 논리(격자) · 브라에스 역설 · 차분 · 포함-배제의 원리 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
四色定理 / four color theorem지도 위의 모든 구역을 색칠하는데, 인접한 구역끼리 색이 겹치지 않게끔 칠하려면 최대 4색이면 충분하다는 정리. 볼프강 하켄(Wolfgang Haken), 케네스 아펠(Kenneth Appel)에 의해 증명되었다.
2. 그래프 이론으로 표현
지도의 각 구역을 꼭지점으로 나타내고, 두 구역이 인접해 있었다면 두 꼭지점을 변으로 연결하여 그래프를 그릴 수 있는데, 이 그래프는 반드시 평면 그래프다. 반대로, 임의의 평면 그래프가 주어졌을 때 그것을 지도로 바꿀 수도 있다.즉, 임의의 평면 그래프가 주어졌을 때, 서로 연결된 꼭지점이 다른 색이 되도록 꼭지점을 칠하려면 최대 4색이면 충분하다는 것이다.
어떤 그래프가 평면 그래프인 것과, 그 그래프가 [math({K}_{5})], [math({K}_{3,3})] 및 그 세분(subdivision)[1]을 부분그래프로 가지지 않는다는 것은 동치이다. (Kuratowski's theorem) 따라서 어떤 그래프가 [math({K}_{5})], [math({K}_{3,3})] 및 그 세분 중 어느 하나를 부분그래프로 가지면 평면 그래프가 아니므로 4색정리를 적용할 수 없다. 단, [math({K}_{5})]를 부분그래프로 가지면 무조건 5색 이상이 필요하지만[2], [math({K}_{3,3})]를 부분그래프로 가지거나, [math({K}_{5})], [math({K}_{3,3})]의 (자신이 아닌) 세분을 부분그래프로 가질 경우 5색 이상이 필요할 수도 있고 아닐 수도 있다. 가령 [math({K}_{3,3})]는 2색만으로 칠할 수 있고, [math({K}_{5})]의 세분 중에도 2색만으로 칠할 수 있는 것이 존재한다.
다만 4색정리는 우리가 일상생활에서 접할 수 있는, 위상수학적으로 구면과 같은 지도에만 적용된다. 해당 지도가 위상수학적으로 구면과 같지 않다면 그래프로 변환했을 때 평면 그래프가 나오지 않을 수 있는데, 지도가 원환면과 위상동형일 경우에는 최대 7색이면 충분함이 증명되었다.
3. 증명 역사
3.1. 초기
앞선 시기에 독일의 수학자 뫼비우스가 4색 문제를 먼저 거론했다는 기록이 있지만, 이 문제를 본격적으로 연구한 사람은 프란시스 구스리라는 것이 정설이다.1852년 영국의 식물학자 프란시스 구스리(Fransis Guthrie)는 영국 지도를 구획 별로 색칠하던 중 4가지 색만 있으면 인접한 지역끼리 서로 겹치지 않게 칠할 수 있다는 것을 깨닫고는, 다른 모든 지도의 경우에도 그러한지 궁금해했다. 프란시스의 동생 프레드릭은 형에게 들은 지도와 4가지 색에 대한 이야기를 저명한 수학자 오거스터스 드 모르간에게 물었는데, 이후 드모르간 본인을 포함하여 수많은 수학자들이 4색 문제에 뛰어들었다. 이 과정에서 드 모르간은 6색 정리를 증명했다.
다른 난제들과 달리 어린아이도 이해할 수 있는 간단한 문제라서, 별 거 아닐거라 얕보고 일반인이고 전문가고 자신만만하게 증명을 시도했다가 낭패를 보는 일이 많았다. 특히 수학자중엔 반평생동안 이 문제에만 줄창 매달렸다가 결국 나가떨어지는 경우도 많았다.
4색 문제를 자신이 해결했다는 사람은 많았으나 대부분은 엉터리였고, 수학자들조차도 한동안 부분적, 간접적 증명에서 더 이상 발을 떼지 못했다.
1879년 알프레드 켐프(Alfred Kempe)가 신박한 증명을 내놓으면서 4색 문제에 종지부를 찍는 듯 보였지만, 11년 뒤에 증명 과정의 오류가 밝혀지며 다시 원점으로 돌아오는 일도 있었다. 이 오류를 밝힌 퍼시 히우드(Percy Heawood)는 켐프의 정리를 손질하여 5색으로는 어떠한 지도라도 색칠이 가능하다는 5색 정리를 증명하는 데 성공한다.
3.2. 컴퓨터를 사용한 증명
1960년대 독일의 헤쉬(Heinrich Heesch)는 '컴퓨터를 이용해 이 문제를 증명한다.'는 당시로서 아주 획기적인 발상을 하였다. 헤쉬는 증명에 필요한 컴퓨터를 구하기 위해 독일과 미국을 동분서주하며 기초이론을 세웠지만, 패전한 서독의 경제사정 탓이었는지 연구 자금이 부족해 결국 연구를 그만두고 만다. 헤쉬는 모든 지도들을 유한 개의 유형으로 분류하는 획기적 성과를 거두었으나, 그럼에도 경우의 수는 거의 9천 개에 가까웠고, 당시 컴퓨터 성능으로는 이 모든 경우를 시뮬레이션하는 데 10년이 넘게 걸릴 거라 예상되면서 포기했다고 한다.1976년 미국 일리노이 대학교의 볼프강 하켄(Wolfgang Haken), 케네스 아펠(Kenneth Appel)이 헤쉬의 아이디어를 바탕으로 컴퓨터 두 대를 50여 일 가량 돌린 끝에 증명에 성공했다.
이들이 채택한 방법은 컴퓨터를 이용해서 가능한 모든 경우의 지도 모델을 뽑고, 거기에 4색 정리가 적용되는지 안 되는지를 가려보자는 것이다. 컴퓨터를 사용한 브루트 포스이다. 모든 계산이 끝난 뒤에 반례가 하나도 나오지 않는다면 4색 정리는 증명되고, 반례가 나오더라도 그 자체로 4색 정리는 거짓이라고 밝혀져서 4색 문제가 해결되는 매우 간단한 방법이었다. 공식이나 법칙을 모를 때 모든 경우에 대해 직접 쓰거나 그려서 문제를 푸는 것과 근본적으로는 동일하다.
앞서 헤쉬가 기초 이론을 세우던 과정에서 검토해야 할 지도의 모델은 9천 개 정도였지만, 하켄과 아펠은 모델을 더욱 단순화시켜 1936개까지 줄였다.[3] 하켄과 아펠은 여기에 487가지 판별 필터를 걸고 컴퓨터 2대를 따로 돌려서 같은 결과가 나옴을 확인한 다음, 컴퓨터로 계산한 자료를 (고등학생, 대학생이던) 자기 아들, 딸에게 직접 축소된 부분을 칠하도록 해 증명했다. 이 때문에 타 논문이었으면 연구비를 지원한 기관에 감사하다는 내용을 썼을 테지만, 이 논문의 첫 시작은 자녀들에게 감사하다는 내용이었다.
이렇다보니 증명 결과만 몇 박스에 달했고, 여러 수학자들 앞에서 멋지게 수식을 휘날리며 결론을 도출한 뒤 과정에 오류가 없음을 확인받는 기존의 증명과 달리 '컴퓨터로 계산해서 빼먹은 것 없는지 확인 다 했고, 그 결과물이 이거다.' 하며 종이 몇 박스를 들이미는 식이라 여러 수학자들에게 아름답지 못한 증명이라고 까였다.[4] 거기에 최초로 컴퓨터를 사용한 증명이라는 점 역시 인간이 검증할 수 없다는 이유로 기존 수학자들이 반감을 품었다. 실제로 당시 기록들을 살펴보면, '검토 결과 그들의 증명 과정에서 오류가 없음은 반박할 수 없는 사실이지만, 그래도 컴퓨터를 가지고 이런 무식한 방법으로 증명했다는 점에서 비판받아야 함.'하며 까는 경우가 많았다. 그리고 '하늘책의 증명'에도 4색 정리는 빠져 있고, '5색 정리'가 수록되어 있다.
이렇게만 보면 누구나 다 컴퓨터를 가지고 있고 컴퓨터의 속도가 비약적으로 증가해 이 정도 계산은 몇 초도 지나지 않아 끝나는 오늘날에는 '까짓 거 소스 코드 좀 짜고 실행 버튼 누르면 끝이니 수학을 잘 알지 못해도 하겠네.' 정도로 쉽게 생각할 수 있다. 그러나 아무리 성능이 뛰어난 컴퓨터라도 무한한 경우의 수를 모두 시행착오로 계산하는 것은 절대 불가능하다. 하켄과 아펠은 오랜 시간에 걸쳐 이론을 정교하게 다듬고 계산 과정을 최적화하기 위해 많은 노력을 기울였으며, 컴퓨터 자원과 연구 자금을 확보하기 위해서도 끊임없이 힘썼다. 실제로 약 1200시간에 걸친 계산 작업은 컴퓨터가 수행했지만, 그 방대한 계산을 가능하게 만든 모델을 유한한 형태로 정리하고, 연구 전 과정을 준비하고 점검하며 결과를 발표한 것은 하켄과 아펠의 공이었다. 이들의 기여를 단순히 컴퓨터의 성능으로만 치부해서는 안 된다.
4. 의의
수많은 수학 난제들이 그러하듯 사실 정리의 증명 자체는 크게 실용성이 없었다.[5] 지도 색칠은 색을 적게 쓰는 것보다는 알아보기 편하도록 적재적소에 알맞은 색을 쓰는 것이 중요하기 때문이다. 그러나 그 과정에서 나온 수많은 중간 결과물들이 다른 난제를 푸는 데 도움이 되거나 새로운 난제를 낳았다.또한 주어진 그래프가 평면 그래프인지의 여부에 대해서는 존 홉크로프트(John Hopcroft)와 로버트 타잔(Robert Tarjan)이 내놓은 Hopcroft-Tarjan 알고리즘을 통해서는 [math(O(n))] 시간 내에서 확인할 수 있다.
다만 직관상으로나 그렇지 실제로 증명하는 건 인간의 계산으로는 불가능하다. 그래프를 칠하는 데에 필요한 최소 색상의 수를 찾으려면 모든 그래프를 [math({K}_{n})] 단위로 해체해야 하는데, 이 문제 자체가 NP-완전 문제이기 때문. 게다가 그래프가 복잡할수록 휴먼 에러의 가능성이 높아지는지라, 수많은 수학자들이 좌절을 맛보기도 했다. 또 최소 색상의 수를 구했다 해도 그래프에 직접 그리는 건 또 다른 문제인지라, 실제적 증명을 위해 어쩔 수 없이 컴퓨터가 사용될 수 밖에 없었다. 이 때문에 복잡한 계산이나 모델화, 검증과 같은 증명 과정에 컴퓨터를 사용하는 것이 일반화되었고, 이제 컴퓨터는 수학과 뗄 수 없는 도구가 되었다.
5. 실제 지도에서는?
당연하지만, 실제 지도 채색에 이 정리를 쓸 일은 없다. 애초에 지도의 목적은 보는 사람이 알아보기가 쉽게 만드는 것이지, 색깔 아끼는 게 아니다. 본래의 목적을 제쳐두고 어떻게든 4색으로만 칠하려고 해도, 실제 지도에는 인접한 나라를 다른 색으로 칠하는 것 말고도 정상적인 지도라면 갖춰야 할 추가 조건이 있기 마련이다.
5.1. 육지와 수면의 구분
정상적인 지도라면 당연히 육지와 수면을 구별할 수 있어야 한다. 그러므로 바다와 호수를 하나의 색으로 통일해야 하고 그 색은 육지의 나라를 칠하는데 사용해서는 안 되는데, 여기서 이미 4색정리를 벗어난 문제가 된다. 위의 세계지도는 수면에 일괄적으로 5번째 색인 흰색을 사용했다.수면을 색칠할 필요가 없다고 본다면, 여전히 4색 정리에서 벗어나지 않는다.[6]
5.2. 월경지와 섬
월경지와 섬을 본토와 같은 색으로 그리는 것도 지도 채색 시 필수적인 조건이다. 위의 세계지도에서도 러시아의 칼리닌그라드, 아제르바이잔의 나흐츠반, 프랑스의 프랑스령 기아나와 같이 월경지는 본토와 같은 색으로 칠해져 있고, 프랑스와 네덜란드는 본토가 서로 떨어져 있지만 세인트마틴 섬에서 국경을 맞대고 있기 때문에 서로 다른 색으로 칠해져 있는 것을 볼 수 있다.다행히 수면을 색칠할 필요가 없다고 본다면, 실제 세계지도에서는 이 추가 조건을 고려하면서도 여전히 4색으로 칠할 수 있다. 실제로 아슬아슬하게 [math({K}_{5})]를 피해간 케이스가 존재하는데, 바로 폴란드, 라트비아, 리투아니아, 벨라루스, 러시아의 관계이다. 러시아의 월경지인 칼리닌그라드가 폴란드와 리투아니아에 접하고 있어 생기는 케이스로, 만약 폴란드와 라트비아가 발트해를 통해 이어져 있었다면 이 5개국이 서로 국경을 접하게 되어 [math({K}_{5})]가 생겨났을 것이다.
세계지도는 시간의 흐름에 따라 변하기 때문에 4색으로 칠할 수 있는지의 여부도 바뀌어 왔다. 그리고 정치적 관점에 따라 국경이나 나라를 다르게 구분하는 경우도 많다 보니 딱 잘라 말하기 힘든 부분도 있다. #(영문)
대한민국의 시군구 지도는 달성군의 월경지로 인해 [math({K}_{5})]가 형성되므로, 4개 색상으로 칠하는 것이 불가능하다. #
6. 여담
해당 문제를 해결했던 볼프강 하켄과 케네스 아펠은 다음과 같은 말을 남겼다. #어느 순간부터인가, 컴퓨터가 우리를 놀라게 하기 시작했습니다.
처음에 우리는 계산에 필요한 변수들을 일일이 손으로 입력하면서 작업을 했기 때문에 어떤 상황에서든 컴퓨터의 모든 동작을 미리 예견할 수 있었습니다.
그런데 갑자기 컴퓨터가 체스를 두는 로봇처럼 혼자서 돌아가기 시작한 것입니다. 컴퓨터는 자신이 '학습했던' 모든 방법들을 하나씩 적용해 나가면서 계산을 했고,
어떤 때는 사람보다도 현명한 판단을 내리곤 했습니다. 그 이후로 우리는 계산을 어떻게 진행해야 할지 컴퓨터에게 배우는 신세가 되었습니다.
어떤 면에서 볼 때 컴퓨터는 계산 능력뿐만 아니라 지적인 능력까지도 자신의 창조주인 인간을 능가하고 있었습니다.
- 사이먼 싱, '페르마의 마지막 정리(Fermat's last theorem)', 박병철 역, 영림카디널, p.399
처음에 우리는 계산에 필요한 변수들을 일일이 손으로 입력하면서 작업을 했기 때문에 어떤 상황에서든 컴퓨터의 모든 동작을 미리 예견할 수 있었습니다.
그런데 갑자기 컴퓨터가 체스를 두는 로봇처럼 혼자서 돌아가기 시작한 것입니다. 컴퓨터는 자신이 '학습했던' 모든 방법들을 하나씩 적용해 나가면서 계산을 했고,
어떤 때는 사람보다도 현명한 판단을 내리곤 했습니다. 그 이후로 우리는 계산을 어떻게 진행해야 할지 컴퓨터에게 배우는 신세가 되었습니다.
어떤 면에서 볼 때 컴퓨터는 계산 능력뿐만 아니라 지적인 능력까지도 자신의 창조주인 인간을 능가하고 있었습니다.
- 사이먼 싱, '페르마의 마지막 정리(Fermat's last theorem)', 박병철 역, 영림카디널, p.399
로널드 그레이엄은 다음과 같은 말로 컴퓨터를 이용한 증명을 비판했다.
리만 가설이 맞는 것인지 컴퓨터에게 물어보았다고 합시다. 그런데 컴퓨터가 "네, 맞습니다. 그런데 그 이유를 설명한다 해도 당신은 이해하지 못할 것입니다."라 대답한다면, 이 얼마나 황당하고 기죽는 일이겠습니까? [7]
- 사이먼 싱, '페르마의 마지막 정리(Fermat's last theorem)', 박병철 역, 영림카디널, p.403
알파고(특히 알파고 vs 알파고)를 경험한 현대인의 입장에서 여러 가지로 생각할 거리를 던져주는 말이다.- 사이먼 싱, '페르마의 마지막 정리(Fermat's last theorem)', 박병철 역, 영림카디널, p.403
마틴 가드너는 1975년 4월 1일날 자신의 Mathematical Games 칼럼에 다음의 복잡한 지도가 4색 문제의 반례라고 했다. (보기) 물론 날짜를 보면 알듯이 만우절 낚시였다.
용의자 X의 헌신에 나오는 이시가미 데츠야가 더 '아름다운' 방법으로 증명하고 싶다는 문제가 이것이다.[8]
이걸 이제 상위 차원의 문제로 생각해볼 수도 있다. 하위 차원들로 분할된 [math(n)]차원 셀들이 인접하는 경우[9] 다른 색으로 최소 [math(f(n))]가지 수로 색칠할 때 이를 [math(n)]에 관한 식으로 표현할 수 있는가? 답은 불가능. 위키백과에 말없는 증명이 있는데, 글로 표현하자면 각 셀을 실처럼 길게 뽑아서 반으로 접으면 셀이 몇 개가 되더라도 각각이 서로 인접하게 만들 수 있으므로 색이 아무리 많아도 부족하다. [math(f(1) = 2)]이고 [math(f(2) = 4)]이지만 3차원만 되어도 [math(f(3) = \infty)]라는 뜻. 이는 이미 1880년 영국의 물리학자 프레더릭 거스리(Frederick Guthrie)가 실증한 바 있다. #
이 정리를 응용한 퍼즐 게임도 몇 개 있다. Simon Tatham's Puzzles에는 'Map'이라는 이름으로 수록되어 있다.
[1] 어떤 그래프의 변 위에 꼭지점을 찍어서 만든 그래프를 뜻한다. 자신 또한 포함한다.[2] 이는 비둘기집의 원리를 사용하면 아주 쉽게 증명된다.[3] 하켄-아펠 이후 사람들이 더 연구하여 지금은 이 모델을 633개까지 줄일 수 있다고 한다.[4] 간단히 비유하자면 '1부터 100까지 숫자 중 짝수는 몇 개가 있을까?'라는 문제가 있을 때, '어떤 수를 2로 나눈 몫은 그 수보다 작거나 같은 짝수의 갯수다. 따라서 100/2=50개다.'라는 답이 수학자들이 좋아하는 깔끔한 답이다. 하지만 이들이 낸 증명법은 2, 4, 6, 8... 100까지 짝수를 모조리 써갈긴다음 '다 쓰고 세어보니까 50개네요.'라고 하는 셈이다. 수학자들도 저 풀이법에서 문제점이나 오류를 찾지는 못했지만 '4색정리를 어떤 신박한 방식으로 풀어나갈 것이며, 그 과정에서 어떤 새로운 수학적 도구, 이론이 생겨날 것인가'라고 기대하거나 또는 누구도 생각 못했던 참신한 아이디어를 기대했으나, 4색 정리에 대한 결론을 컴퓨터로 도출하면 결론만 나올뿐 여전히 그 원리를 이해할 수 없으니 실망하게 된 것이다.[5] 사실 컴퓨터 공학을 포함한 다양한 분야에서 4색정리와 관련된 내용들이 알게 모르게 쓰이기는 한다(보통 이러한 문제를 Graph Coloring 문제라고 함). 몇가지 예시를 들자면 컴파일러에서 레지스터를 어떻게 효율적으로 할당할지를 정하는 문제가 이 문제와 관련이 있다. 그 외 실용적인 예시로는 시험 시간 배정, 택시 스케줄 문제 등과 같은 스케줄 배정 문제와 관련이 있다. #1 #2[6] 가령, 바다와 호수의 각 덩어리를 각각 인접한 나라 중 하나에 병합시킨 지도를 만들면 그 지도는 4색정리가 적용되므로 4색으로 칠할 수 있다. 그 다음에 물 부분만 다시 지우면 4색만으로 모든 육지를 칠한 지도가 완성된다.[7] 여담으로 리만 가설도 노가다성 증명 방법의 가능성이 제시된 상태이다. 다만 이 방법 자체가 개미 잡는데 미사일 쓰는 격인 수준이긴 하다.[8] 즉, 이시가미는 컴퓨터로 증명해낸 하켄과 아펠의 방법이 아닌 오로지 인간의 노력으로 증명해낸 답을 찾고 싶었다는 것. 그것이 그가 말하는 '아름다운 방법'이다.[9] 여기서는 '인접한다'의 기준을 두 셀이 [math(n-1)]차원으로 표현할 수 있는 형태로 만나는 것으로 정의한다. 예를 들어 두개의 3차원 셀이 특정 선에서 만나는 경우는 2차원 지도에서 한 점에서 만나는 경우와 같이 인접해있지 않는 경우로 취급한다.