평면에 나타내는 지도에 각양각색의 형태가 들어갈 수 있다고 하자. 꼭 현실의 나라들 영토가 그대로 들어갈 필요도 없고, 우주 어느 행성의 지도일 수도 있으며 꼭 영토가 아니라 평면에 아무렇게나 영역을 표현하는 임의의 형태여도 상관없다. 그런데 이렇게 자유로운 형태들로 평면을 이루는 지도를 과연 4 개의 색으로만 온전하게 구분지어서 나타낼 수 있을까? 분명하게 답은 ‘그렇다’ 혹은 ‘그럴 수 없다’가 되겠지만 어떻게 증명할 수 있을까? 4색 정리 또는 4색 문제라고 불리어지는 이 문제는 19 세기 중반에 시작되어 ‘드 모르간의 법칙’으로 잘 알려진 영구 수학자 드 모르간을 거쳐서, 100 년이 더 지난 1976년에 아펠과 하켄이 컴퓨터와 하켄의 아들 리폴드의 도움을 받아서 해결했다. 사실 지도 제작 업자들은 구태여 극도로 색의 개수를 줄이기 위하여 노력하지 않으므로 현실적으로 지도 제작에 도움이 되는 것은 아니지만, 컴퓨터를 이용한 최초의 증명으로써 과연 컴퓨터를 활용한 수학적 증명을 받아들여야 하는 것인지에 대하여 수학자 세계에 파문을 일으키기도 했다.
하켄과 아펠이 채택한 방법은 컴퓨터를 이용해서 가능한 모든 경우의 지도 모델을 뽑고, 거기에 4색 정리가 적용되는지 안 되는지를 가려보자는 것이다. 모든 계산이 끝난 뒤에 반례가 하나도 나오지 않는다면 4색 정리는 증명되고, 반례가 나오더라도 그 자체로 4색 정리는 거짓이라고 밝혀져서 4색 문제가 해결되는 매우 간단한 방법이었다. 하켄과 아펠은 모델을 더욱 단순화시켜 1936개까지 줄였다. 하켄과 아펠은 여기에 487가지 판별 필터를 걸고 컴퓨터 2대를 따로 돌려서 같은 결과가 나옴을 확인한 다음, 컴퓨터로 계산한 자료를 (고등학생, 대학생이던) 자기 아들, 딸에게 직접 축소된 부분을 칠하도록 해 증명했다. 이 때문에 타 논문이었으면 연구비를 지원한 기관에 감사하다는 내용을 썼을 테지만, 이 논문의 첫 시작은 자녀들에게 감사하다는 내용이었다.(나무 위키 인용)
지도 제작에 실용적이지 않은, 어떻게 보면 단순한 호기심에서 출발한 문제는 무슨 의미가 있는 것일까? 이 문제를 통해 위상수학과 그래프 이론이 한층 더 발전할 수 있었고, 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻는 P-NP 문제와도 연결된다. P-NP 문제는 클레이 연구소가 2,000 년도를 맞이하면서 가장 중요하다고 제시한 7 가지의 밀레니엄 문제 중 하나일 정도로 중요한 이슈다. 4색 문제와 연관된 그래프 이론과 P-NP문제에 대하여 짧은 글이지만 살짝 살펴보자.
먼저 P-NP 문제의 예를 구체적으로 보자. 쉽게 풀이법이 확인될 수 있는 문제이지만 답을 계산하기는 어려울 수 있는 문제의 한 예인 부분집합 합 문제를 예를 들어보면 다음과 같다. 어떤 정수의 집합이 주어졌을 때 공집합이 아닌 부분집합중 적어도 하나 이상의 부분집합의 합계가 0일 수 있는지, 예를 들면 {−2, −3, 15, 14, 7, −10}의 부분집합 중 어떤 것은 합계가 0일지 생각해보면 답은 ‘그렇다’이다. 왜냐하면 부분집합 {−2, −3, −10, 15}의 합계가 0 이기 때문인데, 이것은 3회의 덧셈으로 빠르게 풀린다. 그런데도 그런 부분집합을 다항시간 안에 찾아내는 알고리즘은 알려져 있지 않다. 컴퓨터 과학에서 이 문제의 중요성을 차치하더라도, 이 문제의 증명은 수학, 암호, 알고리즘 연구, 인공지능, 게임이론, 멀티미디어 프로세싱, 철학, 경제학 등 다양한 분야에 엄청난 영향을 끼칠 것이다.(위키피디아 인용) P-NP 문제는 아직 인류가 해결하지 못한 미해결문제이다.
4색 정리(혹은 4색 문제)는 그래프 이론으로 조금 더 엄밀하게 정의할 수 있다. ‘모든 평면 그래프의 꼭짓점을 많아봐야 네 가지 색만 사용하여 인접한 꼭짓점들이 같은 색을 가지지 않도록 칠할 수 있는가’하는 것이 4색 문제이다. 간단히 ‘모든 평면 그래프는 네 가지 색으로 칠할 수 있는가’라고 하기도 한다. 여기서 지도의 모든 구획은 그래프에서 꼭짓점으로 대치되며, 지도의 구획이 경계선을 두고 맞닿아 있으면 해당하는 그래프를 선으로 연결한다.(위키피디아 인용) 가령 다음과 같은 그림으로 이해할 수 있을 것이며, 이렇게 영역의 문제를 점과 선의 그래프로 치환하여 생각함으로써 문제를 해결하는 첫발을 내딛은 것이고, 이렇게 동치인 다른 형태로 표현하는 것은 수학과 과학 그리고 일상에서도 중요할 것이기 때문에 구태여 그림과 함께 짧은 지면에 소개한다. 잠시 세상사 번뇌를 잊고 여러 형태의 영역들을 그래프로 치환하여 보는 것도, 자유로운 산책의 한 방법이 아닐까?
