사색정리
위키백과 ― 우리 모두의 백과사전.
사색정리(四色定理)는 지도와 같이 평면을 여러 부분으로 나눈 다음 각 부분에 여러가지 색을 칠하는 문제에 대한 정리로, 서로 맞닿아 있는 두 부분을 서로 다른 색으로 칠해야 할 때 네 가지 색으로 이것이 가능하다는 정리이다.
세 가지 색으로는 평면을 칠할 수 없다는 것은 반례를 찾는 것으로 증명할 수 있다. 또한 다섯 가지 색으로 칠하는 것이 가능하다는 것도 증명되어 있다. 하지만 네 가지 색으로 가능한지에 대한 문제는 오랫동안 미해결 상태였다.
무한 개의 가짓수에서 유한 개로 가짓수를 줄인 증명이 발표되었고, 유한 개의 가짓수를 모두 컴퓨터를 이용해 검사하였다. 즉, 이 문제는 컴퓨터를 사용해 증명된 문제이다. 따라서 일부 사람들은 이러한 증명은 진정한 의미의 수학적인 증명이 아니라고 생각하고, 더욱 간단한 방법의 증명을 찾는 사람들도 있다.
목차 |
[편집] 역사
사색문제를 처음으로 연구한 사람은 프랜시스 구트리에이다. 1852년에 영국의 지도를 색으로 칠해 구분하다가, 네 가지 색만 사용하면 각 주(州)를 구분할 수 있다는 것을 발견했다. 구트리에는 자신의 스승인 Augustus De Morgan에게 이것을 수학적으로 증명할 수 있는지 문의했다. 구트리에는 유니버시티 칼리지에서 드 모르간의 학생이었으며 1850년에 졸업했다. 사색문제가 처음으로 학문적으로 논의된 것은 1879년 아데 케일리의 논문이었다. (On the colourings of maps., Proc. Royal Geography Society 1, 259-261, 1879.)
사색정리를 증명하기 위한 시도는 여러번 있었다. 1879년에 알프레드 켐페(Alfred Kempe)가 사색정리 증명을 발표했고, 많은 사람들이 증명 과정이 옳다고 생각했다. 이듬해에는 피터 테이트(Peter Tait)가 다른 방법으로 사색정리를 증명했다. 1890년이 되어서야 퍼시 히우드(Percy Heawood)에 의해서 켐페의 증명에서 오류가 있다는 것이 밝혀졌고, 1891년에는 줄리어스 페터슨(Julius Petersen)에 의해서 테이트의 증명도 잘못되었다는 것이 밝혀졌다. 증명이 잘못되었다는 것이 모두 11년이 지나서야 밝혀진 셈이었다. 히우드는 켐페의 증명이 잘못되었다는 것뿐 아니라, 모든 평면 그래프는 다섯가지 색을 사용하면 구분 가능하다는 것을 증명했다. 이것을 사색정리와 구분하여 오색정리라고 한다. 독일의 수학자 하인리히 히쉬(Heinrich Heesch)는 컴퓨터로 수학적 증명을 해결하는 방법을 제안했다. 드디어 1976년에 일리노이 대학교이 케네스 아펠과 볼프강 하켄이 히쉬의 기본 아이디어에 J. 코흐 (Koch)의 알고리즘을 더하여 사색정리를 증명하는데 성공했다. 만약 사색정리가 거짓이면, 다섯가지 색이 필요한 구획들로 구성된 지도가 적어도 하나 존재할 것이다. 아펠과 하켄은 그런 반례가 존재하지 않는다는 것을 다음과 같은 두 가지 개념을 이용하여 보였다.
- 지도에서 나라들이 배열되는 경우의 수는 무한히 많지만, 그 형태를 단순화시키면 유한개의 기본 그래프가 조합된 형태가 된다.
- 기본 그래프가 사색문제의 반례가 되지 않고, 나머지 부분을 네가지 색으로 칠 할 수 있으면 전체 그래프는 네 가지 색으로 칠할 수 있다.
아펠과 하켄은 method of discharging, rings, Kempe chains등의 복잡한 과정으로 무한히 다양한 그래프들은 유한개의 기본 그래프로 단순화시킬 수 있음을 보였고, 결국 사색문제의 반례가 존재하지 않음을 증명할 수 있었다. 지도에서 나라가 배열되는 경우는 무한히 많지만, 결국 1936개의 단순한 형태로 줄일 수 있음을 보였다. 그리고 제대로 단순화 되었는지 컴퓨터로 검사하는 방법을 썼다. (나중에 연구한 결과 1476개만으로 충분함을 보였다.) 무한히 많은 그래프들을 단순화 시키는 과정은 두 대의 컴퓨터에서 별도로 시행하여 다시 한 번 확인했다. 한편 기본 그래프를 네 가지 색으로 칠할 수 있음을 보이는 과정은 손으로 일일이 색을 칠하여 각각의 그래프가 사색정리의 반례가 될 수 없음을 보이는 방법을 썼다. 이 부분만 500페이지가 넘는 분량이었으며, 많은 부분은 당시 10대 소년인 하켄의 아들 리폴드(Lippold)가 검사했다. 컴퓨터 프로그램을 실행하는데는 수백시간이 걸렸다.
어떤 지도를 한가지 혹은 두가지 색으로 칠할 수 있는지 여부를 판별하는 효율적인 알고리즘은 존재하지만, 세 가지 색으로 칠할 수 있는지 여부는 NP-완전 문제이기 떄문에 빠른 해결방법이 없을 것으로 추측된다. 어떤 그래프가 평면그래프이던 아니던 네 가지 색으로 칠할 수 있는지 여부를 판별하는 문제도 마찬가지로 NP-완전이다.
[편집] 지도와 사색정리의 관계
프랜시스 구트리에가 지도를 보면서 사색문제를 처음으로 연구했지만, 사실 지도와 사색정리는 큰 연관이 없다. 케네스 메이(Kenneth May)에 따르면, 학자들이 미국 의회도서관의 지도를 분석한 결과 지도 제작에서 색을 최소한으로 사용하려는 노력은 별로 보이지 않는다고 한다. 구획을 구분하는 것 이외에도 색으로 구분하는 경우가 종종 있고, 대부분의 지도는 다섯가지 이상의 색으로 구획을 구분한다. 실제로 네 가지 색을 사용한 경우는 네 가지 보다 덜 쓰는 것도 가능한 경우가 많다고 한다. 또한 실제 지도에서는 연못도 그려야 하는데, 일반적으로 연못들은 모두 같은 색으로 칠해야 하기 때문에 사색문제의 기본 조건에 어긋난다.
지도제작과 관련된 책에서는 사색정리를 별도로 언급하지 않는다. 지도를 실제로 제작할 때는 색을 칠하는 것이 중요한 문제이기는 하지만, 색을 최소한으로 사용하는 것보다는 한 색이 너무 많이 쓰이지 않도록 적절히 배분하는데 더 관심을 가질 뿐, 색을 네 가지 사용하는지 다섯 가지 사용하는지는 별로 주의를 기울이지 않는다고 한다.
[편집] 엄밀한 그래프 이론적 표현
사색문제는 그래프 이론으로 조금 더 엄밀하게 정의할 수 있다. '모든 평면 그래프의 꼭지점을 많아봐야 네가지 색만 사용하여 인접한 꼭지점들이 같은 색을 가지지 않도록 칠할 수 있는가'하는 것이 사색문제이다. 간단히 '모든 평면 그래프는 네가지 색으로 칠할 수 있는가'라고 하기도 한다. 여기서 지도의 모든 구획은 그래프에서 꼭지점으로 대치되며, 지도의 구획이 경계선을 두고 맞닿아 있으면 해당하는 그래프를 선으로 연결한다.
[편집] 잘못된 증명
[편집] 사색정리의 일반화
[편집] 실제 지도와 차이점
[편집] 같이 보기
[편집] 참고문헌
- 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.
