도넛 위의 지도는 일곱 색
도넛 위에 지도를 칠해 보세요
평평한 종이 위에 어떤 복잡한 지도를 그려도 이웃한 나라끼리 색이 겹치지 않게 칠하는 데는 색 네 개면 충분합니다.
하지만 둥근 튜브나 도넛(토러스) 표면에 지도를 그리면 네 색으로는 어림도 없고 일곱 가지 색이 전부 필요해집니다. 땅의 모양은 그대로인데 구멍 하나 뚫렸다고 왜 필요한 색이 4개에서 7개로 껑충 뛸까요?
이야기
1879년 앨프리드 케임프가 「네 색이면 된다」는 증명을 발표합니다. 사람들은 문제가 끝난 줄 알았습니다.
그런데 11년 뒤인 1890년, 퍼시 히우드가 그 증명이 틀렸다는 것을 밝혀냈습니다. 십일 년 동안 아무도 못 본 구멍이었습니다.
히우드는 거기서 멈추지 않았습니다. 무너진 증명에서 「다섯 색이면 된다」는 건져 냈고, 도넛 위에서는 일곱 색이라는 것까지 증명했습니다. 그래서 이상한 일이 벌어졌습니다. 어려워 보이는 도넛이 쉬워 보이는 평면보다 86년이나 먼저 풀린 것입니다. 평면의 네 색이 증명된 것은 1976년입니다.
도넛이 더 많은 색을 쓰는 까닭은 구멍에 있습니다. 도넛에서는 나라가 구멍을 감아 돌 수 있어서, 평면에서는 만들 수 없는 이웃 관계를 만들 수 있습니다.
구멍이 여러 개인 면에 대해서도 히우드의 식이 있습니다. 구멍 수를 넣으면 필요한 색 수가 나옵니다. 구멍이 하나도 없는 평면과 공만 예외인데, 하필 그 가장 쉬운 경우가 가장 늦게 풀렸습니다.
구멍의 개수가 성질을 정합니다. 이 생각이 위상 데이터 분석으로 자랐습니다.
암세포와 정상세포의 모양을 「구멍의 수」로 가르고, 뇌 신경망의 구조를 분석하고, 자료 뭉치의 숨은 모양을 찾는 데 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
도넛 모양에 색칠해 보기
도넛 모양 튜브에 사인펜으로 나라들을 나누어 그립니다. 평면에서는 나라들이 서로 가로막혀 네 나라가 동시에 서로 국경을 맞댈 수 없습니다.
하지만 도넛 표면에서는 구멍 안쪽을 통과해 반대편으로 돌아 나오는 길이 생깁니다. 일곱 나라가 서로서로 빠짐없이 국경을 맞대도록 지도를 그릴 수 있어서 7가지 색이 모두 필요해집니다.
도넛 위의 지도
이상하게도 도넛이 1890년에 먼저 풀렸습니다.
구멍이 늘면 색도 는다
평면 지도는 오일러 표수가 이지만, 도넛은 구멍이 하나 있어서 이 됩니다.
구멍을 통해 국경선(변)을 훨씬 많이 얽어맬 수 있습니다. 평면에서는 5개의 완전 그래프 를 선이 겹치지 않게 그릴 수 없지만, 도넛 위에서는 7개의 나라가 모두 서로 이웃하는 을 완벽하게 그릴 수 있습니다.
헤이우드 공식
g = 0(평면)에서만 이 공식이 틀립니다 — 5 가 아니라 4 입니다.
오일러 표수와 색수
1890년 퍼시 헤이우드는 종수(구멍 수)가 인 곡면 위의 지도 색칠 수에 대한 헤이우드 공식(Heawood conjecture) 을 제시했습니다.
도넛은 이므로 색이 됩니다. 링겔과 영스는 1968년 클라인 병( 비가향, 6색)을 제외한 모든 곡면에서 이 공식이 정확함을 증명했습니다.
뫼비우스 띠에서는
방향을 매길 수 없는 면은 따로 세어야 합니다.
헤이우드 공식
평면의 4색 정리는 컴퓨터로 수천 개 배위(Configuration)를 전수 조사하여 겨우 증명되었으나, 놀랍게도 도넛 위의 7색 정리는 오일러-푸앵카레 표수와 그래프 이론의 삼각분할 대수학만으로 인간의 손으로 깔끔하게 증명되었습니다.
이는 곡면의 위상수학적 불변량(Topology)이 조합론적 채색수(Chromatic Number)의 상한을 직접 결정함을 보여주는 위상 그래프 이론의 백미입니다.
실제 지도는 왜 4 색인가
다만 비지(飛地)가 있으면(칼리닌그라드 같은) 더 필요할 수 있습니다.
풀어 보기
곡면의 지도 색칠과 헤이우드 공식. 구멍이 개인 곡면 위의 지도를 칠하는 데 필요한 최대 색의 수는 헤이우드 공식 로 주어진다.
(1) 평면 및 구면()에서의 최소 채색수(사색정리)를 쓰시오.
(2) 도넛 표면(토러스, )에서의 최대 채색수 을 헤이우드 공식으로 구하시오.
(3) 구멍이 2개인 쌍도넛() 표면 지도를 칠하는 데 필요한 최대 색의 수를 구하시오. ()
(2) 색, (3) 색입니다.
답과 풀이 보기
(1) 4 색입니다 — 사색정리.
헤이우드 공식에 을 넣어도 로 맞아떨어집니다.
⛔ 다만 g=0 만은 이 공식으로 증명된 것이 아닙니다. 1976 년 아펠과 하켄이 컴퓨터로 1,936 가지 경우를 따져 따로 증명했습니다.
(2) 색입니다.
(3) 색입니다.
⭐ 거꾸로입니다. 평평한 지구본은 4 색이면 되는데, 구멍이 뚫린 도넛에서는 7 색이 필요합니다.
구멍이 생기면 돌아가는 길이 늘어나 서로 이웃한 나라를 더 많이 만들 수 있기 때문입니다.
더 이상한 것은 — 도넛 쪽이 먼저 증명되었다는 점입니다. 1890 년에 이미 7 색이 밝혀졌는데, 가장 쉬워 보이는 평면이 86 년을 더 버텼습니다.
더 멀리
구멍의 개수가 성질을 정합니다.
- 오일러 표수 — 구는 2, 도넛은 0입니다. 이 값이 색 수를 정합니다
- 위상수학 — 늘이고 구부려도 변하지 않는 성질을 다룹니다
- 직접 해 보기 — 튜브 모양 종이에 지도를 그려 색칠해 보세요
이어지는 장
평면이나 둥근 지구본 위의 지도는 네 가지 색이면 충분하지만, 가운데 구멍이 뚫린 도넛 곡면에서는 완전히 맞닿는 일곱 나라가 만들어집니다 — 제42장 의 평면 사색정리와 비교하며 공간의 위상적 차이를 체험해 보세요.
영감을 받은 곳
퍼시 히우드(Percy Heawood)가 1890년 《순수 및 응용수학 계간지》(Quarterly Journal of Pure and Applied Mathematics)에 발표한 논문 「Map-Colour Theorem」에서 토러스(도넛) 위의 지도 채색에 7색이 필요함을 증명했습니다.