오일러와 해밀턴 경로

도로를 모두 한 번씩 점검하는 순찰과, 지점마다 한 번씩 들르는 배달은 비슷해 보이지만 전혀 다른 문제입니다. 앞의 것은 간선을 한 번씩 지나는 길이고, 뒤의 것은 정점을 한 번씩 지나는 길입니다. 앞의 문제는 차수만 세어도 답할 수 있지만, 뒤의 문제에는 그런 간단한 방법이 알려져 있지 않습니다. 이 글에서는 그래프의 모델과 표현의 차수, 트레일, 연결을 써서 두 문제를 비교합니다.

쾨니히스베르크의 일곱 다리

1736년 Leonhard Euler는 쾨니히스베르크라는 도시의 일곱 다리를 모두 한 번씩만 건너는 산책길이 있는지를 묻는 문제를 풀었습니다. 강으로 나뉜 네 땅을 정점으로, 다리를 간선으로 보면 같은 두 땅을 잇는 다리가 여러 개라서 다중 간선이 있는 그래프가 됩니다. 네 땅의 차수는 5, 3, 3, 3이고, 합 14는 다리 수 7의 두 배입니다. Euler는 차수가 홀수인 땅이 이렇게 많으면 그런 산책길이 있을 수 없다는 것을 보였고, 이것이 그래프 이론의 출발점으로 꼽힙니다.

오일러 경로가 있을 조건

모든 간선을 정확히 한 번씩 지나는 트레일을 오일러 경로(Euler trail)라 하고, 출발점으로 돌아오는 오일러 경로를 오일러 순환(Euler circuit)이라고 합니다. 오일러 순환은 오일러 회로라고도 부릅니다. 정점은 몇 번이든 다시 지나도 되고, 간선만 한 번씩 써야 합니다.

간선이 있는 정점들이 모두 한 연결 성분에 들어 있는 유한 무방향 그래프에서는 다음이 성립합니다. 모든 정점의 차수가 짝수이면 오일러 순환이 있고, 차수가 홀수인 정점이 정확히 두 개이면 그 두 정점을 양 끝으로 하는 오일러 경로가 있습니다. 홀수 차수인 정점이 그 밖의 개수이면 오일러 경로가 없습니다. 홀수 차수인 정점은 언제나 짝수 개이므로, 남는 경우는 4개 이상일 때뿐입니다. 쾨니히스베르크는 네 땅이 모두 홀수 차수라서 산책길이 없었습니다.

먼저 조건이 필요한 이유를 보겠습니다. 트레일이 어떤 정점을 지나갈 때마다 들어오는 간선 하나와 나가는 간선 하나를 쓰므로, 출발점과 도착점이 아닌 정점에서는 쓴 간선이 둘씩 짝을 이룹니다. 모든 간선을 쓴다면 이런 정점의 차수는 짝수여야 합니다. 출발점은 처음에 나가는 간선 하나, 도착점은 마지막에 들어오는 간선 하나가 짝 없이 남으므로, 둘이 다르면 그 두 정점만 차수가 홀수이고, 같으면 짝이 맞아 모든 차수가 짝수입니다. 간선이 있는 정점들이 이어져 있어야 한다는 조건도 필요합니다. 떨어진 부분의 간선은 한 번의 산책으로 지날 수 없기 때문입니다.

닫힌 트레일을 이어 붙여 만든다

조건이 충분하다는 것은 실제로 오일러 순환을 만드는 방법으로 보입니다. 모든 차수가 짝수일 때, 간선이 있는 아무 정점에서 출발해 아직 쓰지 않은 간선을 따라 더 갈 수 없을 때까지 걸어 봅니다. 출발점이 아닌 정점 v에 들어설 때마다 v의 간선은 홀수 개만 쓰인 상태입니다. 앞서 지나간 횟수마다 2개씩, 그리고 방금 들어온 간선 1개를 썼기 때문입니다. 차수가 짝수이므로 쓰지 않은 간선이 적어도 하나 남아 있어 계속 나갈 수 있고, 그래서 걸음은 출발점에서만 멈춥니다. 이렇게 닫힌 트레일 하나를 얻습니다.

아직 쓰지 않은 간선이 남았다면, 연결되어 있다는 조건 때문에 지금의 트레일 위에 쓰지 않은 간선이 붙은 정점이 반드시 있습니다. 그런 정점이 하나도 없다면 트레일이 지나간 부분과 남은 간선이 서로 떨어져 있게 되기 때문입니다. 닫힌 트레일은 각 정점의 간선을 짝수 개씩 썼으므로 남은 차수도 모두 짝수이고, 그 정점에서 같은 방법으로 닫힌 트레일을 하나 더 만들어 원래 트레일의 그 자리에 끼워 넣을 수 있습니다. 끼워 넣을 때마다 남은 간선이 줄어들므로 이 과정은 끝나고, 끝나면 모든 간선을 한 번씩 쓴 오일러 순환이 됩니다.

홀수 차수인 정점이 s와 t 두 개일 때는 s에서 출발합니다. 같은 홀짝 계산으로 걸음은 t에서만 멈추고, 그 뒤에 남은 차수는 모두 짝수이므로 닫힌 트레일을 끼워 넣는 과정을 그대로 쓸 수 있습니다. 이 증명을 그대로 옮긴 코드는 다음과 같습니다.

def walk_until_stuck(adjacency, start):
    trail = [start]
    while adjacency[trail[-1]]:
        v = trail[-1]
        u = adjacency[v].pop(0)
        adjacency[u].remove(v)
        trail.append(u)
    return trail


def euler_trail(graph, start):
    odd = [v for v in graph if len(graph[v]) % 2 == 1]
    if len(odd) not in (0, 2) or (odd and start not in odd):
        return None
    adjacency = {v: list(neighbors) for v, neighbors in graph.items()}
    trail = walk_until_stuck(adjacency, start)
    print("처음:", " → ".join(trail))
    i = 0
    while i < len(trail):
        if adjacency[trail[i]]:
            detour = walk_until_stuck(adjacency, trail[i])
            print("끼워 넣기:", " → ".join(detour))
            trail[i:i + 1] = detour
        i += 1
    if any(adjacency.values()):
        return None
    return trail


bowtie = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D", "E"],
          "D": ["C", "E"], "E": ["C", "D"]}
print(" → ".join(euler_trail(bowtie, "A")))
example = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"]}
print(" → ".join(euler_trail(example, "D")))
print(euler_trail(example, "A"))
two = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"],
       "D": ["E", "F"], "E": ["D", "F"], "F": ["D", "E"]}
print(euler_trail(two, "A"))

처음: A → B → C → A
끼워 넣기: C → D → E → C
A → B → C → D → E → C → A
처음: D → C → A → B → C
D → C → A → B → C
None
처음: A → B → C → A
None

walk_until_stuck은 쓰지 않은 간선이 있는 동안 계속 걷고, 간선 하나를 쓸 때마다 양 끝의 목록에서 함께 지웁니다. euler_trail은 먼저 홀수 차수 조건을 확인하고, 처음 걸음을 만든 뒤 트레일을 앞에서부터 훑으며 쓰지 않은 간선이 남은 정점을 만나면 그 자리에 새 닫힌 트레일을 끼워 넣습니다. trail[i:i + 1] = detour는 i번째 원소 하나를 리스트 detour 전체로 바꾸는 슬라이스 대입입니다.

두 삼각형이 C에서 만나는 나비넥타이 모양의 그래프 bowtie는 처음 걸음이 A → B → C → A에서 멈추지만, C에 남은 간선으로 C → D → E → C를 만들어 끼워 넣어 오일러 순환을 완성합니다. 앞 글의 예제 그래프는 C와 D가 홀수 차수라서 D에서 출발하면 C에서 끝나는 오일러 경로가 나오고, 홀수 차수가 아닌 A에서는 출발할 수 없습니다. 떨어진 두 삼각형은 모든 차수가 짝수이지만, 다른 삼각형의 간선이 남아 None이 됩니다. 차수만으로는 판정할 수 없고 연결 조건이 함께 필요한 이유입니다.

이 코드는 증명을 그대로 보여 주려고 리스트에서 원소를 지우고 끼워 넣는 일을 반복하므로 느린 편입니다. 같은 아이디어를 스택으로 구현한 Hierholzer 알고리즘은 간선 수에 비례하는 시간에 오일러 경로를 찾습니다. 방향 그래프에서는 홀짝 대신 진입 차수와 진출 차수를 비교합니다. 모든 정점에서 두 값이 같으면 오일러 순환이 있고, 진출 차수가 1 큰 정점과 진입 차수가 1 큰 정점이 하나씩 있으며 나머지 정점에서는 두 값이 같으면 앞의 것에서 출발해 뒤의 것에서 끝나는 오일러 경로가 있습니다. 이때도 간선이 있는 정점들이 방향을 지웠을 때 하나로 이어져 있어야 합니다.

해밀턴 경로는 정점을 한 번씩 지난다

모든 정점을 정확히 한 번씩 지나는 경로를 해밀턴 경로(Hamiltonian path)라 하고, 모든 정점을 한 번씩 지난 뒤 출발점으로 돌아오는 사이클을 해밀턴 사이클(Hamiltonian cycle)이라고 합니다. 이번에는 정점을 다시 지나면 안 되고, 쓰지 않는 간선이 있어도 됩니다. 예제 그래프에서 D → C → A → B는 해밀턴 경로입니다. 하지만 해밀턴 사이클은 없습니다. 사이클에서는 모든 정점이 들어오는 간선과 나가는 간선 두 개를 써야 하는데, D는 차수가 1이기 때문입니다.

모든 차수가 2 이상이라는 조건만으로는 해밀턴 사이클이 생기지 않습니다. 나비넥타이 그래프 bowtie는 모든 차수가 2 이상이고 오일러 순환까지 있지만, 해밀턴 사이클이 없습니다. 한쪽 삼각형에서 다른 쪽으로 넘어가는 길이 C를 지나는 것뿐이라서, 모든 정점을 돌고 돌아오려면 C를 두 번 지나야 하기 때문입니다. 반대로 충분조건으로는 Dirac 정리가 알려져 있습니다. 정점이 n개(n ≥ 3)인 단순 그래프에서 모든 정점의 차수가 n/2 이상이면 해밀턴 사이클이 있습니다. 다만 이것은 필요조건이 아니라서, 정점 5개를 원 모양으로 이은 그래프는 차수가 2로 5/2보다 작지만 그 자체가 해밀턴 사이클입니다.

오일러 경로의 홀짝 조건처럼 모든 그래프에서 빠르게 판정할 수 있는 조건은 해밀턴 경로에 대해 알려져 있지 않습니다. 이 문제는 계산 복잡도 이론에서 NP-완전(NP-complete) 문제로 분류되며, 효율적인 일반 알고리즘이 있는지는 아직 풀리지 않은 문제입니다. 작은 그래프에서는 정점의 순서를 모두 나열해 확인할 수 있습니다.

from itertools import permutations
from math import factorial


def hamilton_paths(graph):
    return [order for order in permutations(graph)
            if all(b in graph[a] for a, b in zip(order, order[1:]))]


example = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"]}
for path in hamilton_paths(example):
    print(" → ".join(path))
print(factorial(4), factorial(10), factorial(20))

A → B → C → D
B → A → C → D
D → C → A → B
D → C → B → A
24 3628800 2432902008176640000

permutations(graph)는 딕셔너리의 키, 곧 정점들을 늘어놓는 모든 순서를 차례로 만들고, zip(order, order[1:])는 이웃한 두 정점의 쌍을 만듭니다. 이웃한 쌍마다 간선이 있는 순서만 남기면 해밀턴 경로입니다. 결과의 네 줄은 같은 두 경로를 양쪽 방향으로 적은 것이고, 모두 차수가 1인 D가 한쪽 끝에 있습니다. 정점이 4개이면 순서가 4! = 24가지뿐이지만, 10개이면 약 363만 가지, 20개이면 약 $2.4\times10^{18}$가지로 늘어나 이런 방법으로는 감당할 수 없습니다.

정리

• 오일러 경로는 모든 간선을 한 번씩 지나는 트레일이고, 해밀턴 경로는 모든 정점을 한 번씩 지나는 경로입니다. 각각 출발점으로 돌아오면 오일러 순환, 해밀턴 사이클입니다.
• 간선이 있는 정점들이 이어져 있을 때, 모든 차수가 짝수이면 오일러 순환이 있고, 홀수 차수인 정점이 정확히 둘이면 그 둘을 양 끝으로 하는 오일러 경로가 있습니다.
• 조건이 필요한 이유는 지나가는 정점마다 간선이 둘씩 짝을 이루기 때문이고, 충분한 이유는 닫힌 트레일을 만들어 이어 붙이는 방법으로 보일 수 있습니다.
• 방향 그래프의 오일러 경로는 홀짝 대신 진입 차수와 진출 차수의 차이로 판정합니다.
• 해밀턴 경로에는 간단한 판정 조건이 알려져 있지 않습니다. Dirac 정리 같은 충분조건은 있지만, 일반적으로는 경우를 나열해야 하고 그 수는 정점 수의 계승만큼 늘어납니다.

연습 문제

1. 별 모양 그래프

중심 O에 잎 A, B, C가 하나씩 이어진 별 모양 그래프에 오일러 경로와 해밀턴 경로가 있나요?

2. 쾨니히스베르크에 다리 놓기

차수가 5, 3, 3, 3인 쾨니히스베르크의 네 땅에 다리를 하나 더 놓아 오일러 경로가 생기게 하려면 어떻게 해야 하나요? 출발점으로 돌아오는 산책길까지 만들려면 다리가 몇 개 더 필요한가요?

3. 완전 그래프의 두 순회

$K_4$와 $K_5$에 오일러 순환과 해밀턴 사이클이 각각 있나요? 일반적인 $K_n$에서는 어떤가요?

오일러 경로를 찾았다면 원래 간선 목록에서 쓴 간선을 하나씩 지우며 검산해 보세요. 다음 글 최단 경로와 단계별 갱신에서는 간선에 비용이 붙은 그래프에서 가장 싸게 이동하는 길을 찾습니다.