해밀턴의 세계 일주 게임

 

19세기 영국의 수학자 해밀턴은 그래프와 관련된 여러 가지 재미있는 문제를 제기하였는데 그 중에는 아직까지 완전히 해결되지 않은 문제도 있다.

'세계 일주 게임'은 그가 1857년에 소개한 것으로, 정십이면체의 20개의 각 꼭짓점에 세계의 유명한 도시의 이름을 붙인 후, 어느 한 도시를 출발하여 모서리를 따라 다른 도시를 모두 방문하고 처음 도시로 돌아오는 게임이다. 이때, 한 번 방문한 도시는 다시 방문하지 않는다.
해밀턴은 정십이면체를 평면그래프로 나타내어 이 문제를 다음 그림과 같이 해결하였다.

 

위의 게임에서와 같이 같은 길을 지나지 않고 주어진 그래프 상의 점을 모두 한 번씩 지나서 출발점으로 돌아올 수 있는 길을 '해밀턴 폐쇄로'라고 한다. 해밀턴 폐쇄로 문제는 '어떤 경우에 해밀턴 폐쇄로가 있는가'를 묻는 문제인제, 아직도 완전히 해결되지 않은 수학의 난제 중 하나로 꼽힌다.

한편 해밀턴 폐쇄로에 통과하는 길의 거리까지 포함시킨 '순회 영업 사원 문제(travelling salesman problem)'라는 것도 있다. 이는 '영업 사원 순회 문제' 또는 '우편집배원 문제'라고도 불리는데, 영업 사원이 한 도시를 출발하여 모든 도시를 통과한 다음 처음 출발했던 도시로 돌아오는 최단 경로를 찾는 문제이다. 최소 경비로 영업 사원이 모든 도시를 방문하거나 최단 거리로 집배원이 모든 편지를 배달하기 위해서는 이동하는 각 선에 교통비나 이동 거리와 같은 가중치를 두어 해밀턴 폐쇄로를 찾아야 한다. 이 문제는 아직도 효율적인 알고리즘을 찾지 못한 난제로 남아 있으며, 그래프에서 가능한 모든 해밀턴 폐쇄로를 찾아 비교해야 하기 때문에 통과하는 지점 수가 늘어나면 컴퓨터로도 처리하는데 많은 시간이 필요하게 된다.

실생활에서 여러 지역에 물건을 효율적으로 배송하는 경로를 찾거나, 적은 경비로 여러 관광지를 여행하는 관광 코스를 찾을 때 등에서 이와 같은 문제 해결 방법은 유용하게 활용되고 있다.