해밀턴 경로

그래프의 모든 꼭짓점을 한 번씩만 지나는 경로를 해밀턴 경로, 출발점으로 돌아오면 해밀턴 순환이라 한다. 주어진 그래프에 그런 경로가 있는지 판정하는 문제는 NP-완전이다. 경로를 받으면 확인은 쉽다. 비슷해 보이는 「모든 변을 한 번씩 지나는 길(오일러 경로)이 있는가」는 꼭짓점마다 이어진 변의 수만 세면 되는 쉬운 문제여서, 겉모습이 비슷해도 어려움은 전혀 다를 수 있음을 보여 준다. Clay 수학연구소의 P 대 NP 소개 글도 이 문제를 예로 든다.