Hamiltonian  Cycle  Problem

William Rowan Hamilton 경은 1800 년 중반 12 면체의 모양에서 수수께끼 하나를 제시했다 (그림 1). 각 꼭지점에 도시 이름을 주고, 문제는 어떤 도시에서 출발하여, 간선들을 따라서 한 도시를 한번만 방문하여, 최초의 출발 도시로 돌아오는 것이다. 12 면체의 간선의 그래프는 그림 2 에 주어져 있다. 해밀턴의 수수께끼를 그림 2 의 그래프에서 사이클을 찾을 수 있다면 문제는 해결된다. 다만 각 정점은 한 번만 포함되어야 한다 (출발점과 끝나는 점은 두 번 나타나는 것을 제외하고). 그림 3 은 그 해이다.

그림 1  해밀턴 퍼즐

그림 2  해밀턴 퍼즐의 그래프

그림 3  그림 2 의 그래프에서 각 정점이 한번만 방문한다.

해밀턴의 업적을 기리어, 주어진 그래프에서 출발점과 종료점만 두 번 나타나는 것을 제외하고는 정점이 한 번씩만 나타나는 사이클을 해밀턴 사이클 (Hamiltonian cycle) 이라 한다. ............ (해밀턴 사이클과 판매원 방문 문제 (Hamiltonian Cycles and the Travelling Salesperson Problem) : Richard Johnsonbaugh)

해밀턴 (1805~1865) 은 아일랜드의 대학자였다. 그는 듀브린 대학의 천문학 교수였고, 물리학과 수학 분야에서 많은 논문들을 집필했다. 수학 분야에서, 해밀턴은 사원법 (quaternions) 의 발명, 실수 체계의 일반화로 매우 유명하다. 그의 사원법은 현대 추상 대수의 발전에 영감을 주었다. 해밀턴은 벡터 용어를 도입했다

term :

그래프이론 (Graph Theory)   순회판매원 문제 (Traveling Salesman Problem)   William Rowan Hamilton

site :

The Hamiltonian Page  : Hamiltonian cycle and path problems 에 관한 많은 자료

Hamiltonian Cycle Problem  : Hamiltonian cycle problem을 풀기위한 source code hamilton.c