정점을 빠짐없이 지난다
A—B—C—D라는 경로 그래프에서 A,B,C,D 순서는 해밀턴 경로다. 네 정점을 한 번씩 방문한다. 큰 그래프에 추가 간선이 있어도 그 간선을 모두 사용할 필요는 없다.
일부 경로와 구별한다
그래프 안에 단순 경로가 있다는 것만으로 해밀턴 경로가 있는 것은 아니다. 그 경로가 그래프 전체의 정점을 포함해야 한다. 도중에 방문하지 않은 정점이 남으면 조건을 충족하지 못한다.
오일러 경로와 다르다
오일러 경로는 모든 간선을 한 번씩 사용하며 정점을 다시 지날 수 있다. 해밀턴 경로는 정점 재방문을 허용하지 않는 대신 간선 전체를 덮을 필요가 없다. 두 조건은 어느 하나가 다른 하나를 그대로 대신하지 않는다.
출발점으로 돌아가면
모든 정점을 한 번씩 지난 뒤 마지막 정점에서 시작점으로 돌아오는 간선이 있으면 해밀턴 순환을 만들 수 있다. 경로가 있다는 것만으로 마지막 연결 간선까지 보장되는 것은 아니다.
관련 문서
해밀턴 순환 / 오일러 경로 / 오일러 회로 / 경로 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론) / 단순 그래프