4색 문제
4색 문제
  • 김인수
  • 승인 2007.01.11 17:46
  • 댓글 0
이 기사를 공유합니다

 1850년경 영국 런던에 있는 대학원생이었던 구드리라는 학생은 영국의 지도에 있는 지역들을 구별하기 위한 색(colour)은 몇 가지나 될까를 생각하다가 4가지 색이면 충분할 것이라는 사실을 발견하였다.

 그 후, 이 문제는 당시 복잡한 유럽지도에 국경선을 공유하는 나라들을 서로 다른 색으로 표시하는데 있어서도 4가지 색으로만 충분하다는 사실이 알려지게 되었다.

 수학자들이 관심을 갖게 된 것은 ‘구면위(또는 평면위)의 임의의 지도를 색칠하려면 색의 종류가 몇 가지 있어야 필요 충분할까?’ 하는 것이었고 1879년 케일리(A.Cayley)에 의하여 런던 지리학회에서 처음 공식 제기 되었다.

 이 문제를 ‘4색 문제’(four-colour problem)라 하는데 이에 대하여 처음으로 해답을 낸 사람은 켐프라는 수학자였다.

 그는 1879년부터 1880년에 걸쳐 자신의 증명을 여러 학술지에 발표하였고 일단의 논쟁은 막을 내렸다. 그로부터 11년이 지난 1899년 영국의 수학자 히우드(P.J Heawood)는 켐프의 추론과정에 결함이 있음을 발견하고, 이때부터 거의 100여 년간에 걸쳐 이 문제는 수많은 수학자들의 관심의 대상이 되었으나 아무도 증명할 수 없었다.

 그러나 이 문제에 근접하기 위한 노력은 계속되어 히우드는 다섯 가지 색으로는 어떠한 지도라도 구별 가능함을 밝혔고, 1920년경에 프랭크린(P.Franklin)은 국가수가 25개 이하인 경우에는 4색으로 구별 가능함을 증명하였다.

 그후, 1968년에는 오어와 스탬플이 40개 이하의 나라가 있으면 4색으로 구별할 수 있음을 보였지만 일반적인 해법은 발견되지 않았고, 다만 이 문제는 여러 형태의 지도와 다양한 공식들을 양산하여 점점 더 복잡한 형태로 바꾸어 졌다.

 이 복잡한 여러 형태는 컴퓨터를 사용하던 수학자들에 의해 프로그램으로 저장되기 시작됐고, 마침내 이 문제는 1976년 미국의 일리노이 대학에 있는 두 수학자인 아펠과 하켄교수에 의하여 증명되었다.

 그들은 고속의 컴퓨터를 이용하여 1000여 시간 이상 컴퓨터의 계산과 수 백 쪽에 이르는 증명을 하였다. 그럼에도 불구하고, 수학자들은 컴퓨터를 이용한 이 증명법에 별로 흥미를 표시하지 않고 있다.

 이 문제가 단순한 만큼 그 증명 또한 ‘우아하고 단순한 방법’이 존재하리라는 것이 일반적인 수학자들의 생각이다.

 아펠과 하켄교수의 증명은 완벽한 것으로 검증되었지만, 그러나 증명이 지나치게 복잡하고 뿐만 아니라 증명의 대부분은 기계(컴퓨터)의 힘을 빌렸으며, 이 문제의 증명과정이 증명이외에는 쓸모가 전혀 없다는 것으로 밝혀짐으로써 누군가에 의하여 다시 증명되어야 할 문제로 남아 있다고 할 수 있다. 따라서 이 문제는 기계의 힘을 빌리지 않는 해결 방법으로는 아직까지 남아 있다고 할 수 있다.


댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.