어느 지도에서나 경계가 맞닿아 있는 지역에는 서로 다른 색을 칠하여 경계를 분명이 구별하면 보기 좋다. 예를 들면 한국 지도에서 서울·경기도·강원도 등의 지역을 서로 다른 색으로 칠하는 것이다.
1850년경 영국 거스리(Guthrie)라는 수학도는 영국 지도상의 지역들을 구분하기 위해 4가지 색만 있으면 충분하다는 사실을 발견하였다. 이것을 ‘4색 문제(four-coloring problem)’라고 이름 붙여 정식 문제로 제안한 사람은 행렬이론으로 유명한 영국 수학자 케일리(A. Cayley)였다.
그후 켐프와 히우드를 거쳐 1920년경 프랭클린이 국가 수가 25개 이하라는 4색으로만 구분이 가능하다는 것을 증명하였다. 그 후 68년 오어와 스템플이 40개 이하의 국가 수 역시 4색으로 가능하다는 걸 증명해 보였지만 일반적인 해법은 발견할 수 없었다.
76년 미국 일리노이대학의 아펠(Appel)과 하켄(Haken) 교수는 컴퓨터 프로그램을 통해 이 4색 문제를 입증하였다. 이들은 지도를 특징별로 1879개의 경우로 분류하고 1200여 시간에 이르는 컴퓨터 계산과 수백 페이지에 이르는 증명을 하였다. 하지만 아직까지 제대로 인정받지 못하고 있다. 컴퓨터 프로그램으로 입증된 사실을 인정하면서도 엄밀한 수학적 증명 과정의 일부를 컴퓨터가 담당하였다는 점 때문에 수학계가 공식적으로는 인정하지 않는 것이다. 그래서 많은 수학자들은 지금도 4색 문제를 수학적으로 증명하는 연구를 하고 있다. 언젠가는 인간에 의해 공식적으로 증명되는 날이 올 것으로 기대된다.
그래프 색칠하기의 응용 분야는 지도에서의 색깔 구분 외에도 매우 다양하지만 여기서는 3가지의 예만 들어본다. 화학 물질을 창고에 저장할 때 만일의 사고를 방지하기 위해 서로 반응하는 물질들을 다른 장소에 배치하는 문제, 방송국 주파수가 겹쳐 난시청 지역이 발생하지 않도록 하는 문제, 애완동물을 판매할 때 사이가 좋지 않은 동물들을 다른 전시관에 배치하는 문제 등이다.
[문제 1]에서는 황새(2), 토끼(4), 말(4), 오리(2), 강아지(4), 소(4), 참새(2), 코끼리(4) 다리의 수를 모두 합하면 된다.
[문제 2]에서는 주어진 자음과 모음을 이용하여 각 예의 글자를 만들 수 있는 지를 조합해본다.
[문제 3]에서는 1층과 2층의 둘레 면과 위에서 본 면을 합하는 것도 하나의 방법이다.
김대수 서울대 사대 수학과·동 대학원 수료, 미국 사우스캐롤라이나대 컴퓨터 공학 석·박사, 인공지능과 신경망 등을 연구해 온 컴퓨터공학자이자 두뇌 과학자다. 『창의 수학 콘서트』와 컴퓨터공학 관련 10여 권의 저서를 출간했다.
