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

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

쉽게 풀면

다리를 하나도 빼놓지 않고 딱 한 번씩만 건너서 산책하는 문제(쾨니히스베르크 다리 문제)에서 나온 오일러 경로는 그래프의 "길(간선)"을 하나도 빠뜨리지 않고, 겹치지도 않게 전부 지나가는 경로를 찾는 문제입니다. 반면 해밀턴 경로는 길이 아니라 "도시(정점)"를 하나씩 딱 한 번만 들르는 여행 코스를 찾는 문제입니다. 두 개념 모두 그래프 위를 한붓그리기처럼 움직이는 경로를 다루지만, 오일러 경로는 간선 기준, 해밀턴 경로는 정점 기준이라는 점이 다릅니다. 흥미롭게도 오일러 경로가 존재하는지는 각 정점에 연결된 간선 수(차수)만 확인하면 간단히 판별되는 반면, 해밀턴 경로가 존재하는지는 일반적으로 판별하기 매우 어려운 문제로 알려져 있습니다.

왜 중요한가

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

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

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

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

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

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

조금 더 깊게 보면

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

주의할 점

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