해밀턴 경로(Hamiltonian Path)는 그래프의 모든 정점을 한 번씩 지나는 경로입니다. (정점 중복방문 X)
해밀턴 회로(Hamiltonian Circuit, Cycle)는 해밀턴 경로 중 시작점=마지막점일 때를 말합니다.
위 그림은 정십이면체(dodecahedron)의 해밀턴 회로입니다.
오일러 회로와는 다르게 어떤 그래프가 해밀턴 경로인지, 해밀턴 회로인지 여부를 묻는 문제는 NP-Complete 문제입니다.
오일러 그래프와 해밀턴 그래프 사이에는 관계가 없습니다.
반응형
'알고리즘 > 그래프' 카테고리의 다른 글
| 양방향 탐색(Bidirectional Search) (0) | 2020.05.19 |
|---|---|
| BFS와 BFS 스패닝 트리 구현 (0) | 2020.05.18 |
| 무향 그래프에서 DFS를 이용해 오일러 회로 찾기 (0) | 2020.05.13 |
| 위상 정렬 (Topological Sort) (0) | 2020.05.13 |
| 오일러 회로(Eulerian Circuit), 오일러 트레일(Eulerian Trail) (0) | 2020.04.04 |
