하켄이 들려주는 4색 정리 이야기 이우혁

하켄? 볼프강 하켄 Wolfgang Haken (1928~현재) 위상수학을 전공. 세 가지의 큰 미해결 문제 중 하나인 4색 문제를 케네스 아펠Kenneth Appel과 함께 컴퓨터를 이용해 풀어 냄으로서 4색 정리를 만듦

4색 문제의 시작 드 모르간 augustus de Morgan 1806~1871 의 수업을 듣던 한 학생의 동생이 형에게 질문 한 문제에서 출발했다. 이때는 영국의 행정구역을 4가지 색으로 칠한 데에서 호기심이 유발되었다.

영국학생의 질문

4색 정리의 조건 지도 : 평면에 그려진 지도. 지도 속에는 나라들과 나라들을 서로 구분짓는 국경선이 있다. 지도 속 나라는 국경선으로 완전히 둘러싸여 있으며, 두 조각 이상 나눠지지 않고 온전한 한 덩어리여야 함. 두 나라가 인접해 있다. : 두 나라가 공유하는 국경선이 존재한다. 두 나라가 만나긴 하는데 한 점에서 만나는 경우 인접해 있지 않다고 한다.

4색 정리의 조건 지도를 색칠한다. : 지도에 그려진 나라들을 하나의 색으로 색칠하되, 서로 인접한 나라 끼리 다른 색으로 칠한다. 어떤 지도가 4색으로 색칠 가능하다. : 지도를 색칠할 수 있는 최소의 색의 수가 4색이다.

드 모르간의 추측 다섯 나라가 있는데, 다섯 나라 모두 다른 네 나라와 인접해 있다면 그 지도를 칠하는데 필히 5색이 필요할 것이다. 그런 지도가 평면에 그려질 수 없다는 것만 증명하면, 평면지도는 모두 4색으로 색칠 가능할 것이다. 과연 참인 명제가 될 수 있을까?

위상수학 어떤 사물이나 도형이 가지고 있는 특성을 연구하고, 공통된 특성을 갖는 것끼리 분류하는 작업을 수행하는 수학 분야를 ‘위상수학 Topology’라고 한다. 그래프 : 점과 선으로 이루어진 그림. 이때 그래프에서 사용된 점들을 ‘꼭짓점’, 그리고 꼭짓점 사이에 이어진 선을 ‘변’ 이라 부른다.

위상수학(2) 나라를 꼭짓점으로, 두 나라가 연결되어 있으면 두 나라를 표현한 꼭짓점을 이어 변을 그려 넣는 과정을 통하여 지도를 그래프로 변환할 수 있다. 같은 그래프 : 꼭짓점의 위치를 바꾸거나 변을 구부리거나 늘이거나 줄여서 두 그래프가 같은 그림으로 그려질 수 있는 그래프.

그래프 둘 다 그래프!

나라를 점으로 생각 연결된 상태를 선으로 생각 그래프로 변환 인접한 두 나라 모식적인 그림 점과 선으로 표현 최종적인 모습

같은 그래프

드 모르간의 추측 증명 일반적으로 그래프를 지도로 바꾸는 작업은 지도를 그래프로 바꾸는 작업의 역순이지만 모든 그래프가 지도로 변환되지는 않는다. 평면 그래프 : 평면 지도로 변환할 수 있는 그래프 또는 어떤 두 변도 꼭짓점이 아닌 곳에서는 서로 만나지 않도록 바꿀 수 있는 그래프

드 모르간의 추측 증명(2) 완전 그래프 : 그래프에 있는 어떤 두 꼭짓점을 선택하더라도 두 꼭짓점을 연결하는 변이 있는 그래프를 말합니다. 꼭짓점의 개수가 5개인 완전 그래프 K5는 평면 그래프가 아니다. 때문에 드 모르간의 추측은 참이다.

완전 그래프

꼭짓점의 개수가 5개인 그래프 평면 그래프가 아님!

그래프가 갖는 법칙 단순 연결 그래프 : 그래프가 하나로 뭉쳐 있고, 변의 양끝에서 만나는 꼭짓점은 반드시 다르고, 두 꼭짓점이 변으로 연결되어 있다면 그러한 변이 반드시 1개뿐인 그래프. 면 : 평면 그래프에서 꼭짓점과 변의 배치로 인해 평면을 어떤 구역으로 나누었을 때, 평면을 나눈 구역. 평면 그래프는 꼭짓점, 변, 면으로 구성됨.

단순 연결 그래프

그래프가 갖는 법칙(2) 오일러 공식 - (꼭짓점의 개수)-(변의 개수)+(면의 개수)=2 즉, v-e+f=2 꼭짓점 : vertex, 변 : edge, 면 : face 평면그 래프 - e≤3∙v-6 이 성립한다.

오일러의 공식 v-e+f=2

평면 그래프 공식 평면그래프에서 성립, 그러나 평면그래프가 아니어도 성립가능 e≤3∙v-6

착색수 그래프를 색칠할 때 K개의 색으로는 칠할 수 있지만 (k-1)개의 색만으로는 색칠하 수 없을 때, k를 이 그래프의 착색수, 혹은 채색수 Chromatic Number라고 한다. 착색수는 물론 자연수이고 평면 그래프뿐 아니라 모든 그래프에 있다.

NP 문제 간단히 말해서 컴퓨터가 버벅거리는 문제 컴퓨터가 일회 계산에 걸리는 시간을 0.0001초라고 한다.

NP 문제 – 착색수 계산시 꼭짓점의 개수 3 4 5 6 7 ∙∙∙ 10 계산 횟수 8 16 32 64 128 1024 소요 시간 - 0.1초 꼭짓점의 개수 20 21 22 25 30 40 50 계산 횟수 100만 200만 400만 3300만 10억 1조 1000조 소요 시간 105초 210초 419초 56분 30시간 3년 3,570년

다섯 이웃 정리 모든 평면 지도에는 인접한 나라가 다섯 개 이하인 나라가 반드시 한 개 이상 존재한다. 마찬가지로 모든 평면 그래프에는 뻗어나가는 변의 개수가 5개 이하인 꼭짓점이 반드시 한 개 이상 존재한다.

최소 범인 지도minimal criminal 4색만으로 색칠할 수 없는 지도 최소 범인 지도보다 나라의 개수가 적은 모든 평면 지도는 4색 만으로 충분히 색칠이 가능한 지도이다.

축소 가능한 배열reducible configuration 나라의 개수를 축소시켜 최소 범인 지도가 될 수 없게 하는 배열. 이 배열을 지도의 일부분으로 사용한 모든 지도는 4색 이하의 착색수를 갖는다.

불가피한 배열의 집합 unavoidable set of reducible configurations 모든 지도에서 등장할 수밖에 없는 배열들을 원소로 갖는 집합

4색 정리의 증명은 불가피한 배열의 집합에 속하는 모든 원소가 축소 가능한 배열임을 보이는 것이다. 4색정리는 앞으로 컴퓨터 기술을 사용한 증명을 인정할 때가 올것을 알려준다.

실생활의 적용 구면 위에 그린 모든 지도는 평면과 마찬가지로 4색만 있으면 충분히 색칠 가능함 완전 그래프 K5는 평면 그래프는 아니지만 튜브 그래프이다. 튜브 위에 그린 모든 지도는 7색만 있으면 충분히 색칠 가능함