[그래프] 오일러/해밀토니안

모든 edge 한 번씩 지남 - Euler circuit / trail (= 한붓그리기)
모든 node 한 번씩 지남 - Hamiltonian cycle / path

 

Euler - P문제 (DFS를 통한 O(VE) 알고리즘 존재 - 종만북 p.839)

Hamiltonian - NP-Hard (Optimization) / NP-Complete (Decision) 문제

(N! 가지 경우의 수를 모두 해보는 완전 탐색 풀이)

 

(TSP의 NP-Complete 증명에 Hamiltonian을 활용하는, 참고할만한 아주 좋은 블로그)

 

 

* 현대 그래프 이론에서 path란 한 점을 한 번만 지나는 단순 경로.

Cycle은 시작점에서 끝나는 단순경로를 의미 (종만북 p.814)

 

오일러 서킷 / 트레일은 edge만 한 번씩 지나면 되므로, 한 점은 두 번 이상 지나기 가능.

그래서 cycle / path라고 하지 않고 circuit / trail이라고 한다.