이 글에서는 데이터 구조에서 중요한 개념인 오일러 그래프(Eulerian Graph)와 해밀턴 그래프(Hamiltonian Graph)에 대해 살펴봅니다. 본격적으로 들어가기에 앞서, 이 두 개념을 이해하는 데 필수적인 기초 개념인 '트레일(Trail)'부터 먼저 알아보겠습니다.
다음과 같은 그래프가 있다고 가정해 보겠습니다.
그래프에서의 트레일(Trail)이란?
트레일이란 간선(edge)들의 수열 (v1, v2), (v2, v3), …, (vk-1, vk)로 이루어진 경로를 의미합니다. 여기서 중요한 조건은 다음과 같습니다.
- 정점(vertex): (v1, v2, …, vk)가 반드시 서로 다를 필요는 없습니다. 즉, 같은 정점을 여러 번 방문할 수 있습니다.
- 간선(edge): 모든 간선은 반드시 서로 달라야 합니다. 즉, 동일한 간선을 두 번 이상 지나갈 수 없습니다.
위 예제 그래프에서 {(B, A), (A, C), (C, D), (D, A), (A, F)}는 하나의 트레일입니다. 하지만 정점 A가 두 번 방문되었기 때문에 '단순 경로(Simple Path)'로는 분류되지 않습니다. 또한, 시작 정점과 마지막 정점이 같은 경우에는 이를 '닫힌 트레일(Closed Trail)'이라고 부릅니다.
오일러 경로와 오일러 그래프
그래프 G(V, E)에서 오일러 경로(Eulerian Trail)란 그래프의 모든 간선을 정확히 한 번씩만 통과하는 트레일을 말합니다. 만약 이 오일러 경로가 닫힌 형태라면, 즉 시작점으로 돌아올 수 있다면 해당 그래프를 오일러 그래프라고 부릅니다.
좀 더 쉽게 설명하자면, 한 정점에서 출발하여 모든 간선을 딱 한 번씩만 지나면서 다시 출발 정점으로 되돌아올 수 있는 그래프가 바로 오일러 그래프입니다.
수학자 오일러(Euler)는 오일러 그래프에 관한 유명한 정리를 증명했습니다. 그 내용은 다음과 같습니다.
하나의 그래프가 오일러 그래프일 필요충분조건은 그 그래프의 모든 정점의 차수(degree)가 짝수여야 한다.
즉, 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 그래프가 될 수 있습니다.
해밀턴 사이클(Hamiltonian Cycle)
해밀턴 사이클은 그래프 G의 모든 정점을 정확히 한 번씩 지나가는 순환(cycle)을 의미합니다. 오일러 경로가 '간선'에 초점을 맞춘 개념이라면, 해밀턴 사이클은 '정점'에 초점을 맞춘 개념이라는 점에서 차이가 있습니다.
그래프가 해밀턴성을 가지기 위한 충분조건을 제시하는 여러 정리들이 존재하지만, 임의의 그래프가 해밀턴 그래프인지 판별하는 문제 자체는 NP-완전(NP-Complete) 문제로 알려져 있습니다. 따라서 대규모 그래프에서 해밀턴 사이클의 존재 여부를 확인하는 것은 계산적으로 매우 어려운 문제에 속합니다.