4색정리
4색정리(四色定理) 또는 4색문제는 평면을 유한 개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분하다는 정리이다. 이 문제는 지도에서 서로 맞닿은 지역에 다른 색을 칠한다는 것에서 착안해 만들어졌다.
세 가지 색으로는 평면을 칠할 수 없다는 것은 반례를 찾는 것으로 증명할 수 있다. 또한 다섯 가지 색으로 칠하는 것이 가능하다는 것도 증명되어 있다. 하지만 네 가지 색으로 가능한지에 대한 문제는 오랫동안 미해결 상태였다.
평면을 여러 개의 부분으로 나누는 가짓수를 무한 개에서 유한 개로 줄인 증명이 발표된 후, 이후 이 유한 개의 경우를 모두 컴퓨터 계산을 통해 검사하였다. 즉, 이 문제는 컴퓨터를 이용한 증명으로, 일부 사람들은 이러한 증명은 진정한 의미의 수학적인 증명이 아니라고 생각하고, 더욱 간단한 방법의 증명을 찾는 사람들도 있다.
목차 |
[편집] 역사
4색문제를 처음으로 연구한 사람은 프랜시스 구드리(Francis Guthrie)이다. 1852년에 영국의 지도를 색으로 칠해 구분하다가, 네 가지 색만 사용하면 각 주(州)를 구분할 수 있다는 것을 발견하였다. 구드리는 자신의 스승인 드모르간에게 이것을 수학적으로 증명할 수 있는지 문의하였다. 구드리는 유니버시티 컬리지에서 드모르간의 학생이었으며 1850년에 졸업하였다. 4색정리가 처음으로 학문적으로 논의된 것은 1879년 아서 케일리의 논문이었다. (On the colourings of maps., Proc. Royal Geography Society 1, 259-261, 1879.)
4색정리를 증명하기 위한 시도는 여러번 있었다. 1879년에 알프레드 켐프(Alfred Kempe)가 4색정리 증명을 발표하였고, 많은 사람들이 증명 과정이 옳다고 생각하였다. 이듬해에는 피터 테이트(Peter Tait)가 다른 방법으로 4색정리를 증명하였다. 1890년이 되어서야 퍼시 히우드(Percy Heawood)에 의해서 켐프의 증명에서 오류가 있다는 것이 밝혀졌고, 1891년에는 율리우스 페터센(Julius Petersen)에 의해서 테이트의 증명도 잘못되었다는 것이 밝혀졌다. 증명이 잘못되었다는 것이 모두 11년이 지나서야 밝혀진 것이다. 히우드는 켐페의 증명이 잘못되었다는 것뿐 아니라, 모든 평면 그래프는 다섯 가지 색을 사용하면 구분 가능하다는 것을 증명하였다. 이것을 4색정리와 구분하여 5색정리라고 한다.
독일의 수학자 하인리히 헤쉬(Heinrich Heesch)는 컴퓨터로 수학적 증명을 해결하는 방법을 제안하였다.
드디어 1976년에 일리노이 대학교 어바나-샴페인의 케네스 아펠과 볼프강 하켄이 히쉬의 기본 아이디어에 J. 코흐 (Koch)의 알고리즘을 더하여 4색정리를 증명하는 데에 성공하였다. 만약 4색정리가 거짓이면, 다섯 가지 색이 필요한 구획들로 구성된 지도가 적어도 하나 존재할 것이다. 아펠과 하켄은 그런 반례가 존재하지 않는다는 것을 다음과 같은 두 가지 개념을 이용하여 보였다.
- 지도에서 나라들이 배열되는 경우의 수는 무한히 많지만, 그 형태를 단순화시키면 유한개의 기본 그래프가 조합된 형태가 된다.
- 기본 그래프가 4색문제의 반례가 되지 않고, 나머지 부분을 네 가지 색으로 칠할 수 있으면 전체 그래프는 네 가지 색으로 칠할 수 있다.
아펠과 하켄은 method of discharging, rings, Kempe chains등의 복잡한 과정으로 무한히 다양한 그래프들은 유한개의 기본 그래프로 단순화시킬 수 있음을 보였고, 결국 4색문제의 반례가 존재하지 않음을 증명할 수 있었다. 지도에서 나라가 배열되는 경우는 무한히 많지만, 결국 1936개의 단순한 형태로 줄일 수 있음을 보이고 제대로 단순화 되었는지 컴퓨터로 검사하는 방법을 썼다. (후속 연구에 따르면 633개만으로 충분하다.) 무한히 많은 그래프들을 단순화시키는 과정은 두 대의 컴퓨터에서 별도로 시행하여 다시 한 번 확인하였다. 한편 기본 그래프를 네 가지 색으로 칠할 수 있음을 보이는 과정은 손으로 일일이 색을 칠하여 각각의 그래프가 4색정리의 반례가 될 수 없음을 보이는 방법을 썼다. 이 부분만 500페이지가 넘는 분량이었으며, 많은 부분은 당시 10대 소년인 하켄의 아들 리폴드(Lippold)가 검사하였다. 컴퓨터 프로그램을 실행하는 데는 수백 시간이 걸렸다.
어떤 지도를 한가지 혹은 두가지 색으로 칠할 수 있는지 여부를 판별하는 효율적인 알고리즘은 존재하지만, 세 가지 색으로 칠할 수 있는지 여부는 NP-완전 문제이기 때문에 빠른 해결방법이 없을 것으로 추측된다. 어떤 그래프가 평면 그래프이든 아니든 네 가지 색으로 칠할 수 있는지 여부를 판별하는 문제도 마찬가지로 NP-완전이다. 한편으로는 지도를 실제로 네 가지 색으로 칠하는 알고리즘은 O(n2) 시간 복잡도로 가능함이 알려져 있다.[1]
[편집] 지도와 4색정리의 관계
프랜시스 구드리가 지도를 보면서 4색문제를 처음으로 연구했지만, 사실 지도와 4색정리는 큰 연관이 없다. 케네스 메이(Kenneth May)에 따르면, 학자들이 미국 의회도서관의 지도를 분석한 결과 지도 제작에서 색을 최소한으로 사용하려는 노력은 별로 보이지 않는다고 한다. 구획을 구분하는 것 이외에도 색으로 구분하는 경우가 종종 있고, 대부분의 지도는 다섯 가지 이상의 색으로 구획을 구분한다. 실제로 네 가지 색을 사용한 경우는 네 가지보다 덜 쓰는 것도 가능한 경우가 많다고 한다. 또한 실제 지도에서는 연못도 그려야 하는데, 일반적으로 연못들은 모두 같은 색으로 칠해야 하기 때문에 사색문제의 기본 조건에 어긋난다.
지도제작과 관련된 책에서는 4색정리를 별도로 언급하지 않는다. 지도를 실제로 제작할 때는 색을 칠하는 것이 중요한 문제이기는 하지만, 색을 최소한으로 사용하는 것보다는 한 색이 너무 많이 쓰이지 않도록 적절히 배분하는 데 더 관심을 가질 뿐, 색을 네 가지 사용하는지 다섯 가지 사용하는지는 별로 주의를 기울이지 않는다고 한다.
[편집] 이론적 표현
4색정리는 그래프 이론으로 조금 더 엄밀하게 정의할 수 있다. '모든 평면 그래프의 꼭지점을 많아봐야 네 가지 색만 사용하여 인접한 꼭지점들이 같은 색을 가지지 않도록 칠할 수 있는가'하는 것이 4색문제이다.
간단히 '모든 평면 그래프는 네 가지 색으로 칠할 수 있는가'라고 하기도 한다. 여기서 지도의 모든 구획은 그래프에서 꼭지점으로 대치되며, 지도의 구획이 경계선을 두고 맞닿아 있으면 해당하는 그래프를 선으로 연결한다.
[편집] 같이 보기
[편집] 참고문헌
- Appel, Kenneth & Haken, Wolfgang & Koch, John, Every Planar map is Four Colorable, Illinois: Journal of Mathematics: vol.21: pp.439-567, December 1977.
- Appel, Kenneth & Haken, Wolfgang, Solution of the Four Color Map Problem, Scientific American, vol.237 no.4: pp.108-121, October 1977.
- Appel, Kenneth & Haken, Wolfgang, Every Planar Map is Four-Colorable. Providence, RI: American Mathematical Society, 1989.
- Gonthier, Georges, A computer-checked proof of the Four Colour Theorem, unpublished.
- O'Connor and Robertson, The Four Colour Theorem, at the MacTutor archive, 1996.
- Robertson, Neil; Sanders, Daniel; Paul, Seymour; and Thomas, Robin, Efficiently four-coloring planar graphs, New York: ACM Press, 1996.
- Saaty and Kainen, The Four Color Problem: Assaults and Conquest (ISBN 0-486-65092-8)
- Thomas, Robin, Four Colors Suffice, London: Penguin Books Ltd, 2002.
- Thomas, Robin, An Update on the Four-Color Theorem (PDF File), Notices of the American Mathematical Society, Volume 45, number 7 (August 1998)
- Thomas, Robin, The Four Color Theorem, http://www.math.gatech.edu/~thomas/FC/fourcolor.html
- Ringel, G. and Youngs, J. W. T. "Solution of the Heawood Map-Coloring Problem." Proc. Nat. Acad. Sci. USA 60, 438-445, 1968.
