오일러 경로와 해밀턴 경로 (Euler Path and Hamiltonian Path)

한 줄 정의: 오일러 경로는 그래프의 모든 간선을 정확히 한 번씩 지나는 경로이고, 해밀턴 경로는 모든 정점을 정확히 한 번씩 방문하는 경로입니다.

쉽게 풀면

다리를 하나도 빼놓지 않고 딱 한 번씩만 건너서 산책하는 문제(쾨니히스베르크 다리 문제)에서 나온 오일러 경로는 그래프의 "길(간선)"을 하나도 빠뜨리지 않고, 겹치지도 않게 전부 지나가는 경로를 찾는 문제입니다. 반면 해밀턴 경로는 길이 아니라 "도시(정점)"를 하나씩 딱 한 번만 들르는 여행 코스를 찾는 문제입니다.

두 개념 모두 그래프 위를 한붓그리기처럼 움직이는 경로를 다루지만, 오일러 경로는 간선 기준, 해밀턴 경로는 정점 기준이라는 점이 다릅니다.

흥미롭게도 오일러 경로가 존재하는지는 각 정점에 연결된 간선 수(차수)만 확인하면 간단히 판별되는 반면, 해밀턴 경로가 존재하는지는 일반적으로 판별하기 매우 어려운 문제로 알려져 있습니다.

왜 중요한가

오일러 경로와 해밀턴 경로는 배달·순찰 경로 최적화, 회로 설계, DNA 서열 조립처럼 "모든 자원을 빠짐없이 한 번씩 처리해야 하는" 다양한 실무 문제를 그래프 이론의 언어로 옮겨 다루는 데 사용됩니다. 특히 해밀턴 경로/사이클 문제는 외판원 문제(TSP)와 직결되어 있어, 계산복잡도 이론에서 NP-완전 문제의 대표 사례로도 자주 인용됩니다.

핵심 정리

두 문제는 모두 ‘그래프를 따라 한 번에 걷기’이지만 한 번씩 지나야 하는 대상이 다릅니다.

오일러 경로: 모든 간선을 정확히 한 번씩 지나는 경로. 연결 그래프에서 홀수 차수 정점이 0개 또는 2개이면 존재합니다(Euler, 1736). 0개이면 출발점으로 돌아오는 오일러 회로가 되고, 2개이면 그 두 정점에서 시작하고 끝나는 경로가 됩니다.
해밀턴 경로: 모든 정점을 정확히 한 번씩 지나는 경로. 일반 그래프에서 존재 여부를 판별하는 문제는 NP-완전으로 알려져 있습니다(Karp, 1972; Garey & Johnson, 1979).

오일러 경로는 Hierholzer(1873)의 방법 등으로 간선 수에 비례하는 시간에 구할 수 있는 반면, 해밀턴 경로는 일반적으로 그런 빠른 알고리즘이 알려져 있지 않습니다.

예시로 보기

(쾨니히스베르크 다리 문제를 코드로 계산한 예) 네 개의 땅 A, B, C, D를 일곱 개의 다리가 잇습니다(A–B 2개, A–C 2개, A–D, B–D, C–D 각 1개). 각 땅에 닿는 다리 수, 즉 차수를 세면 A = 5, B = 3, C = 3, D = 3입니다. 홀수 차수 정점이 4개이므로 0개 또는 2개라는 조건을 만족하지 못해 모든 다리를 한 번씩만 건너는 경로는 존재하지 않습니다. 이것이 Euler(1736)가 푼 문제입니다.

응용으로는 짧은 DNA 조각을 이어 전체 서열을 복원하는 문제를 de Bruijn 그래프의 오일러 경로 문제로 바꾼 접근(Pevzner 외, 2001)이 있고, 해밀턴 경로·회로의 변형은 외판원 문제와 이어집니다.

자주 하는 오해

“이름이 비슷하니 난이도도 비슷하다”: 오일러 경로는 차수만 세면 판별되지만 해밀턴 경로는 일반적으로 어렵습니다.
“오일러 경로는 모든 정점을 한 번씩 지난다”: 그렇지 않습니다. 오일러 경로에서는 정점을 여러 번 지날 수 있고, 간선만 한 번씩 지납니다.
차수 조건만 보면 된다는 착각: 홀수 차수 조건은 그래프가 연결되어 있다는 전제에서 성립합니다. 간선이 있는 부분이 떨어져 있으면 조건을 만족해도 경로가 없습니다.
방향 그래프는 조건이 다릅니다: 방향 그래프의 오일러 경로는 홀수 차수 대신 각 정점의 들어오는 간선 수와 나가는 간선 수를 비교해 판별합니다.
그래프 순회(너비·깊이 우선 탐색)는 모든 정점을 방문하는 탐색이며 ‘한 번씩만’이라는 제약이 없습니다.

논문에서는 이렇게 쓰입니다

실제 논문에서

이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.

예시 문장

아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.

"배달 경로 최적화 문제에서 모든 도로 구간을 한 번씩 지나야 하는 제약 조건을 오일러 경로 탐색 문제로 정식화하였다."

이 문장은 배달원이 특정 도로 구간들을 빠짐없이 한 번씩만 지나가는 최적 경로를 찾는 문제를, 그래프 이론의 오일러 경로 문제로 바꾸어 풀었다는 뜻입니다.

"DNA 단편들을 서로 겹치는 부분을 기준으로 연결해 전체 서열을 복원하는 문제를, 드브루인 그래프 상의 오일러 경로 탐색 문제로 변환하여 해결하였다."

생물정보학에서는 짧은 DNA 조각들로부터 전체 유전체 서열을 조립하는 문제를 오일러 경로 탐색으로 바꾸어 효율적으로 푸는 접근이 널리 쓰입니다.

조금 더 깊게 보면

오일러 경로는 연결된 그래프에서 홀수 차수를 가진 정점이 0개이거나 정확히 2개일 때만 존재한다는 명확한 판별 조건이 있어 다항 시간 안에 확인할 수 있습니다. 반면 해밀턴 경로가 존재하는지 일반적으로 판별하는 문제는 NP-완전으로 알려져 있어, 정점 수가 늘어나면 사실상 모든 경우를 확인하는 수준의 계산량이 필요해집니다. 이 때문에 논문에서는 해밀턴 경로 자체를 정확히 구하기보다, 근사 알고리즘이나 휴리스틱으로 대신 접근하는 경우가 많습니다.

주의할 점

오일러 경로와 해밀턴 경로는 그래프를 방문하는 순서 자체를 다루는 그래프 순회(너비 우선·깊이 우선 탐색)와 혼동하기 쉽습니다. 그래프 순회는 모든 정점을 "방문할 수만 있으면" 되는 탐색 절차인 반면, 오일러·해밀턴 경로는 간선이나 정점을 "정확히 한 번씩만" 지나야 한다는 훨씬 엄격한 조건을 만족해야 합니다.

헷갈리기 쉬운 용어

‘경로’와 ‘회로’, ‘간선’과 ‘정점’을 나누어 읽으면 정리됩니다.

용어	한 번씩 지나는 것	시작과 끝
오일러 경로	모든 간선	달라도 됩니다
오일러 회로	모든 간선	출발점으로 되돌아옵니다
해밀턴 경로	모든 정점	달라도 됩니다
해밀턴 회로	모든 정점	출발점으로 되돌아옵니다
외판원 문제	모든 도시를 한 번씩, 총거리 최소	해밀턴 회로 중 가장 짧은 것을 찾는 최적화 문제입니다.

참고 문헌

Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 128–140.
Hierholzer, C. (1873). Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6(1), 30–32.
Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of Computer Computations (pp. 85–103). Plenum Press.
Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
Pevzner, P. A., Tang, H., & Waterman, M. S. (2001). An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences, 98(17), 9748–9753.

표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.