해밀턴 경로와 오일러 경로 차이: 정점·간선·한붓그리기

해밀턴 경로와 오일러 경로의 차이는 무엇을 한 번씩 방문하느냐에 있다. 해밀턴 경로는 모든 정점을 정확히 한 번 방문하고, 오일러 경로는 모든 간선을 정확히 한 번 지난다. 한붓그리기는 도형을 그래프로 올바르게 바꿨을 때 오일러 경로 문제로 볼 수 있다.

가장 먼저 구분할 기준

구분	해밀턴 경로	오일러 경로
한 번씩 방문하는 대상	모든 정점	모든 간선
다시 방문해도 되는 대상	간선은 조건에 따라 다름	정점은 여러 번 방문 가능
시작점과 끝점이 같을 때	해밀턴 사이클	오일러 회로
일반 그래프의 존재 판정	Hamiltonian Path 결정 문제는 NP-complete	무향 그래프는 연결성과 홀수 차수 정점 수로 판정 가능
대표 질문	모든 도시를 한 번씩 방문할 수 있는가	모든 길을 한 번씩 지나갈 수 있는가

NIST의 정의에서 해밀턴 경로는 그래프의 모든 정점을 포함하는 simple path다. 반면 오일러 경로는 모든 간선을 정확히 한 번 사용하는 경로다. 이름은 비슷하지만 제약을 거는 대상이 다르다.

경로와 사이클은 무엇이 다른가

해밀턴 경로가 모든 정점을 한 번 방문한 뒤 다른 정점에서 끝나면 열린 경로다. 마지막 정점에서 처음 정점으로 이어져 닫히면 해밀턴 사이클이다. 단순히 “시작점과 끝점을 연결한다”가 아니라 시작점으로 돌아오는 닫힌 순환이어야 한다.

오일러 경로도 같은 방식으로 구분한다.

• 시작점과 끝점이 다르면 열린 오일러 경로 또는 오일러 trail이다.
• 시작점과 끝점이 같으면 오일러 회로 또는 Euler cycle이다.
• 간선은 한 번씩만 사용하지만, 한 정점을 여러 번 지나는 것은 허용된다.

따라서 정점을 재방문했다는 이유만으로 오일러 경로가 아닌 것은 아니다. 반대로 모든 간선을 지나지 않아도 모든 정점을 정확히 한 번 방문했다면 해밀턴 경로가 될 수 있다.

한붓그리기는 언제 오일러 경로가 되는가

종이 위의 도형을 바로 세지 말고 먼저 그래프로 모델링해야 한다.

1. 선이 끝나는 지점과 실제로 연결되는 교차점을 정점으로 둔다.
2. 두 정점 사이의 선 조각을 간선으로 둔다.
3. 선이 겹쳐 보이더라도 서로 연결되지 않은 교차라면 정점으로 만들지 않는다.
4. 같은 두 정점을 잇는 선이 여러 개면 서로 다른 간선으로 남긴다.

이렇게 만든 그래프에서 모든 간선을 한 번씩 지나는 경로가 있으면 펜을 떼거나 같은 선을 덧그리지 않고 그릴 수 있다. 무향 그래프에서는 간선이 있는 정점들이 하나의 연결 성분에 속해야 하며, 홀수 차수 정점 수가 핵심이다.

• 홀수 차수 정점이 0개면 시작점으로 돌아오는 한붓그리기가 가능하다.
• 홀수 차수 정점이 2개면 한 홀수 정점에서 시작해 다른 홀수 정점에서 끝낼 수 있다.
• 홀수 차수 정점이 그 밖의 개수면 오일러 경로가 없다.

고립 정점은 그릴 간선이 없으므로 이 연결성 검사에서 제외한다. 실제 경로를 만드는 방법은 오일러 경로 판별과 Hierholzer 알고리즘에서 코드로 이어서 볼 수 있다.

난이도 차이는 왜 큰가

오일러 경로는 각 정점의 차수와 연결성을 확인한 뒤 Hierholzer 알고리즘으로 실제 경로까지 만들 수 있다. 인접 리스트를 사용하면 판정과 구성 모두 O(V + E)에 처리할 수 있다.

해밀턴 경로에는 오일러 경로의 홀수 차수 조건처럼 일반 그래프 전체에 적용되는 간단한 필요충분조건이 없다. MIT의 NP-complete 문제 강의 자료는 directed Hamiltonian Path 결정 문제가 NP-complete임을 Hamiltonian Cycle에서의 환원으로 설명한다. 이는 후보 경로를 검증하기 어렵다는 뜻이 아니라, 일반 입력에서 존재 여부를 다항 시간에 판정하는 알고리즘이 알려져 있지 않다는 뜻이다.

그래프의 크기나 구조가 제한되면 backtracking, bitmask dynamic programming, branch and bound 같은 방법을 사용할 수 있다. 다만 이것을 오일러 경로의 차수 판정과 같은 수준의 일반 해법으로 보면 안 된다.

TSP와 해밀턴 경로는 같은 문제인가

완전히 같지는 않다. Traveling Salesperson Problem은 보통 가중치가 있는 도시 간 이동에서 모든 도시를 방문하고 시작점으로 돌아오는 tour의 총비용을 최소화한다. “모든 정점을 한 번 방문하는 순환”이라는 점에서 해밀턴 사이클과 연결되지만, 존재 여부뿐 아니라 비용 최적화까지 포함한다.

정리하면 다음 세 질문을 분리해야 한다.

• 모든 정점을 정확히 한 번 방문할 수 있는가: 해밀턴 경로 결정 문제
• 모든 정점을 방문하고 출발점으로 돌아올 수 있는가: 해밀턴 사이클 결정 문제
• 그중 비용이 가장 작은 순환은 무엇인가: TSP 최적화 문제

그래프 문제의 다른 경로 기준은 다익스트라 최단경로 풀이와 비교하면 더 선명하다. 최단경로는 모든 정점이나 모든 간선을 방문하는 문제가 아니라 두 지점 사이의 비용을 최소화하는 문제다.

문제를 보자마자 확인할 질문

1. 반드시 한 번씩 사용해야 하는 대상이 정점인가, 간선인가?
2. 시작점으로 돌아와야 하는가?
3. 정점이나 간선의 재방문이 허용되는가?
4. 무향 그래프인가, 방향 그래프인가?
5. 존재 여부만 필요한가, 실제 경로나 최소비용까지 필요한가?

이 다섯 가지를 먼저 적으면 해밀턴, 오일러, 최단경로, TSP를 이름만 보고 섞는 실수를 줄일 수 있다.

정리

해밀턴 경로는 정점, 오일러 경로는 간선을 정확히 한 번씩 다룬다. 한붓그리기는 교차와 선분을 올바르게 모델링한 오일러 경로 문제다. 오일러 경로는 연결성과 차수로 빠르게 판정하고 선형 시간에 구성할 수 있지만, 일반 그래프의 Hamiltonian Path 결정 문제는 NP-complete다.

참고 자료

• NIST DADS: Hamiltonian path
• NIST DADS: Hamiltonian cycle
• NIST DADS: Eulerian path
• MIT 6.046J: NP-Complete Problems