오일러 경로와 해밀턴 경로 차이는 그래프 입문에서 가장 자주 섞이는 주제 중 하나입니다. 둘 다 경로 문제처럼 보이지만, 오일러는 간선을 한 번씩 지나는지 보고, 해밀턴은 정점을 한 번씩 방문하는지를 봅니다.
이 차이 하나 때문에 판별 난이도도 크게 달라집니다. 오일러는 차수 조건처럼 비교적 깔끔한 규칙이 있지만, 해밀턴은 그런 식의 간단한 지역 규칙으로 끝나지 않는 경우가 많습니다.
오일러 경로와 해밀턴 경로 차이를 가장 짧게 정리하면 이렇습니다. 오일러는 간선을 기준으로, 해밀턴은 정점을 기준으로 문제를 읽습니다. 그래서 같은 그래프 그림을 봐도 체크해야 할 대상이 달라집니다.
- 오일러 경로: 모든 간선을 정확히 한 번씩 지나는 경로
- 오일러 회로: 모든 간선을 정확히 한 번씩 지나며 시작점으로 돌아오는 경로
- 해밀턴 경로: 모든 정점을 정확히 한 번씩 방문하는 경로
- 해밀턴 회로: 모든 정점을 정확히 한 번씩 방문하고 시작점으로 돌아오는 경로
이때 중요한 건 “무엇을 한 번씩 보장하느냐”입니다. 오일러는 간선을 다 써야 하고, 해밀턴은 정점을 다 방문해야 합니다. 같은 경로 문제처럼 보이지만 체크 대상이 다르기 때문에 문제 해석부터 달라집니다.
왜 오일러 경로는 비교적 판별이 쉬울까
오일러 경로는 간선을 한 번씩 써야 하므로, 결국 각 정점에 몇 개의 간선이 들어오고 나가는지가 매우 중요합니다. 무방향 그래프 기준으로는 각 정점의 차수를 보면 꽤 많은 것을 판단할 수 있습니다.
핵심 규칙은 간단합니다. 연결되어 있는 그래프에서 모든 정점 차수가 짝수면 오일러 회로가 있고, 홀수 차수 정점이 정확히 두 개면 오일러 경로가 있습니다. 홀수 차수 정점이 3개 이상이면 오일러 경로는 없습니다.
이 규칙이 직관적인 이유는, 어떤 정점에 들어왔다가 다시 나가려면 간선이 짝을 이뤄야 하기 때문입니다. 시작점과 끝점만 예외가 될 수 있으니 홀수 차수 정점이 0개 또는 2개로 제한됩니다.
반대로 해밀턴 경로는 왜 갑자기 어려워질까
해밀턴 경로는 정점을 정확히 한 번씩 방문해야 합니다. 문제는 어떤 정점 하나의 차수만 보고 전체 가능성을 쉽게 판별하기 어렵다는 점입니다. 한 정점의 연결 수가 많아 보여도, 전체 경로를 한 번씩 이어 붙이는 데 실패할 수 있습니다.
즉 해밀턴 경로는 “이 정점의 지역 조건”보다 “그래프 전체를 한 번에 이어 붙일 수 있는가”가 더 중요합니다. 그래서 오일러처럼 짧은 판별 규칙이 잘 안 통합니다.
같은 그래프도 오일러는 안 되고 해밀턴은 될 수 있을까
그렇습니다. 두 조건은 서로 다른 것을 검사하므로 결과가 다르게 나올 수 있습니다. 예를 들어 어떤 그래프는 모든 정점을 한 번씩 지나는 순서는 만들 수 있지만, 홀수 차수 정점이 너무 많아서 모든 간선을 한 번씩 쓰는 것은 불가능할 수 있습니다.
반대로 모든 간선을 한 번씩 지나는 오일러 회로가 있어도, 정점을 정확히 한 번씩만 방문하는 해밀턴 회로는 없을 수 있습니다. 오일러는 정점 재방문을 허용하지만 간선 재사용을 금지하고, 해밀턴은 그 반대 방향의 제약을 더 강하게 둡니다.
입문자에게 가장 잘 먹히는 예시
쾨니히스베르크의 다리 문제는 오일러 경로 설명의 고전적인 예시입니다. 다리를 모두 한 번씩 건널 수 있는가를 묻는 문제이므로 핵심은 “간선”입니다. 반면 “도시를 모두 한 번씩 방문하는 여행 경로를 만들 수 있는가”는 해밀턴 감각에 더 가깝습니다. 여기서 핵심은 “정점”입니다.
- 다리/도로를 모두 한 번씩 지나야 한다 → 오일러 쪽 감각
- 도시/방/정점을 중복 없이 모두 방문해야 한다 → 해밀턴 쪽 감각
- 간선 재사용 금지가 중요하다 → 오일러
- 정점 재방문 금지가 중요하다 → 해밀턴
오일러 경로와 해밀턴 경로 차이는 코딩테스트에서 어떻게 구분할까
- 문제가 “모든 간선/도로/티켓/연결”을 다 써야 하는지 본다
- 문제가 “모든 정점/도시/방문지”를 다 방문해야 하는지 본다
- 간선 수와 차수 조건으로 빠르게 판별 가능한지 생각한다
- 전체 순열 탐색이나 백트래킹 냄새가 나면 해밀턴 계열 가능성을 의심한다
예를 들어 항공권을 모두 사용해 여행 경로를 만드는 문제는 간선을 다 쓰는 쪽이므로 오일러 계열에 가깝습니다. 반면 각 도시를 한 번씩만 들러야 하는 문제는 해밀턴 계열로 읽는 편이 자연스럽습니다.
그래프 기본 감각이 아직 약하다면 먼저 DFS와 BFS 비교 글로 탐색 관점을 잡고, 이어서 최소 스패닝 트리 글처럼 그래프 성질을 읽는 글과 함께 보면 구분이 더 쉬워집니다.
난이도 차이를 너무 과장 없이 이해하는 법
여기서 중요한 것은 해밀턴이 무조건 구현 불가능한 문제가 아니라, 오일러처럼 짧은 지역 규칙만으로 끝내기 어렵다는 점입니다. 그래서 학습 순서도 다르게 잡는 편이 좋습니다.
오일러는 차수 규칙과 구성 알고리즘 감각을 먼저 익히고, 해밀턴은 전체 경로 조합을 보는 문제라는 관점으로 받아들이면 훨씬 덜 혼동됩니다.
오일러 경로는 조건 판별과 실제 구성 알고리즘이 비교적 잘 정리되어 있습니다. 반면 해밀턴 경로는 일반 그래프에서 존재 여부 판별 자체가 훨씬 까다롭습니다. 그래서 입문자가 둘을 같은 수준의 문제로 보면 학습 순서를 잘못 잡기 쉽습니다.
즉 학습 순서는 보통 오일러 경로를 통해 그래프 성질 문제 감각을 먼저 익히고, 해밀턴 경로는 전체 조합 탐색과 복잡도 차이를 이해하는 재료로 보는 편이 좋습니다.
자주 하는 실수
- 오일러와 해밀턴을 둘 다 “그래프를 한 번씩 돈다”로만 기억한다
- 오일러 경로에서 정점 재방문이 가능하다는 점을 놓친다
- 해밀턴 경로에서 차수만 보고 쉽게 판별하려 한다
- 간선 기준 문제를 정점 기준 문제로 오해한다
특히 두 번째 실수가 많습니다. 오일러 경로는 정점을 다시 지나가도 됩니다. 중요한 것은 간선을 한 번만 쓰는 것입니다. 이 차이를 놓치면 예시 그림을 보고도 정답 판단을 자주 틀립니다.
마무리
오일러 경로와 해밀턴 경로 차이를 한 문장으로 다시 정리하면 이렇습니다. 오일러는 간선을 한 번씩, 해밀턴은 정점을 한 번씩입니다.
이 기준만 분명하면 왜 오일러는 차수 조건이 중요하고, 왜 해밀턴은 갑자기 훨씬 어려워지는지도 자연스럽게 따라옵니다. 그래프 문제를 볼 때 먼저 무엇을 한 번씩 써야 하는지부터 확인해 보세요.
개념 참고는 Eulerian path, Hamiltonian path, 그리고 난이도 감각을 보강하는 longest path problem 정리도 함께 도움이 됩니다.
