순회 영업 사원 문제1 해밀턴의 세계 일주 게임 19세기 영국의 수학자 해밀턴은 그래프와 관련된 여러 가지 재미있는 문제를 제기하였는데 그 중에는 아직까지 완전히 해결되지 않은 문제도 있다. '세계 일주 게임'은 그가 1857년에 소개한 것으로, 정십이면체의 20개의 각 꼭짓점에 세계의 유명한 도시의 이름을 붙인 후, 어느 한 도시를 출발하여 모서리를 따라 다른 도시를 모두 방문하고 처음 도시로 돌아오는 게임이다. 이때, 한 번 방문한 도시는 다시 방문하지 않는다. 해밀턴은 정십이면체를 평면그래프로 나타내어 이 문제를 다음 그림과 같이 해결하였다. 위의 게임에서와 같이 같은 길을 지나지 않고 주어진 그래프 상의 점을 모두 한 번씩 지나서 출발점으로 돌아올 수 있는 길을 '해밀턴 폐쇄로'라고 한다. 해밀턴 폐쇄로 문제는 '어떤 경우에 해밀턴 폐쇄로가 있.. 2014. 12. 5. 이전 1 다음
