[Discrete Mathematics] 오일러 사이클(Euler cycle) 및 해밀턴 사이클(Hamiltonian cycle)

---

오일러 사이클

 

그래프 안의 모든 정점과 모든 간선을 포함하는 사이클을 오일러 사이클이라 한다. 쾨니히스베르크 다리 문제가 대표적인 오일러 사이클을 확인하는 문제이다.

어떤 그래프 $ G $ 가 오일러 사이클을 가진다면, $ G $ 는 연결 그래프이고, 각 정점의 차수는 짝수여야 한다. 이를 증명하기 위해 $ G $ 가 오일러 사이클을 가진다 가정하자. $ v $ 와 $ w $ 가 $ G $ 의 정점이면 $ v $ 에서 $ w $ 까지 취한 오일러 사이클의 일부는 $ v $ 에서 $ w $ 까지의 경로이고, 따라서 $ G $ 는 연결 그래프이다. 어떤 간선으로 $ v $ 에 도착하면 다른 간선을 따라 반드시 떠나야 하기 때문에, 또한 $ v $ 에 연결된 모든 간선이 반드시 사용되어야 하기 때문에 $ v $ 에 연결된 간선은 짝수개여야 한다. 즉 $ G $ 가 오일러 사이클을 가진다면 $ G $ 는 연결 그래프이면서 각 정점의 차수는 짝수여야 한다. 역으로 어떤 그래프 $ G $ 가 연결된 그래프이고, 모든 정점이 짝수 차수를 가진다면 $ G $ 는 오일러 사이클을 가진다.

어떤 그래프 $ G $ 가 $ m $ 개의 간선과 $ n $ 개의 정점 $ V = \{ v_1, v_2, \cdots, v_n \} $ 을 가진 그래프라면, $ \sum_{i=1}^n \delta(v_i) = 2m $, 즉 그래프 안의 모든 정점의 차수의 합은 짝수이다. 모든 정점의 차수를 합할 때, 각 간선을 두 번씩 세기 때문이다. 예를 들어 $ (v_i, v_j) $ 의 차수를 센다면 $ v_i $ 에서 $ (v_i, v_j) $ 로 한 번 세고, $ v_j $ 에서 $ (v_j, v_i) $ 로 한 번 세기에 두 번 세고, 따라서 짝수번 센다.

이를 통해서 어떤 그래프에서도 홀수 차수의 정점의 수는 짝수 개라는 것을 증명할 수 있다. 정점을 두그룹으로 나누어서 짝수 차수를 가지는 것을 $ x_1, x_2, \cdots, x_m $ 으로, 홀수 차수를 가지는 것을 $ y_1, y_2, \cdots, y_n $ 으로 만든다. $ S = \delta(x_1) + \delta(x_2) + \cdots + \delta(x_m) $, $ T = \delta(y_1) + \delta(y_2) + \cdots + \delta(y_n) $ 이라 하면, $ S + T $ 는 짝수이다. 그런데 $ S $ 가 짝수의 합이므로 $ S $ 는 짝수이고, 따라서 $ T $ 역시 짝수이다. 그런데 $ T $ 는 $ n $ 개의 홀수의 합이므로 $ n $ 은 짝수이다.

어떤 그래프와 그 그래프의 서로 다른 정점 $ v $ 와 $ w $ 가 있을 때, 그 그래프에 모든 정점과 모든 간선을 포함하면서 $ v $ 에서 $ w $ 로 가는 반복된 간선이 없는 경로 $ P $ 가 존재한다는 것은 그 그래프가 연결 그래프이고 $ v $ 와 $ w $ 만이 홀수 차수를 가진다라는 것은 동치이다. 이를 증명하기 위해 앞서 언급한 조건이 성립할 때 뒷 조건이 성립함을 증명하면 되며, 이는 다음과 같다. 우선 모든 정점과 간선을 포함하는 경로가 존재해야 하기에 해당 그래프는 연결 그래프이다. $ v $ 에서 $ w $ 로 가는 경로 $ e $ 를 임시로 추가한다면 모든 정점과 모든 간선을 포함하는 사이클, 즉 오일러 사이클이 만들어지기 때문에 이 그래프는 오일러 사이클을 가진다. 또한 앞선 정리에 의해 모든 정점은 짝수 차수를 가진다. $ e $ 를 제거한다면 원래 그래프로 돌아오게 되는데 $ v $ 와 $ w $ 의 차수는 1씩 감소하게 된다. 따라서 원래 그래프에서 $ v $ 와 $ w $ 는 홀수 차수를 가지고, 다른 모든 정점은 짝수 차수를 가진다는 것이 증명된다. 반대로 어떤 그래프가 연결 그래프이고 $ v $ 와 $ w $ 만이 홀수 차수를 가진다면 이 둘을 잇는 간선 $ e $ 를 임시로 추가했을 때 이 그래프의 모든 정점은 짝수 차수를 가지고, 이 그래프는 오일러 사이클을 가지게 된다. 이 오일러 사이클에서 $ e  $ 를 제거한다면 $ v $ 에서 $ w $ 로 가는 모든 정점과 간선을 포함하는 반복되는 간선이 없는 경로를 얻을 수 있다.

어떤 그래프 $ G $ 가 $ v $ 에서 $ v $ 로의 사이클을 포함한다면 $ G $ 는 $ v $ 에서 $ v $ 로의 단순 사이클을 포함한다. 이에 대한 증명은 다음과 같다. $ v = v_0 = v_n $ 이라 할 때 $ C = (v_0, e_1, v_1, \cdots, e_n, v_n) $ 을 $ v $ 에서 $ v $ 로의 사이클이라 하자. $ C $ 가 단순 사이클이 아니라면 $i < j < n $ 에 대하여 $ v_i = v_j $ 이다. 따라서 $ C $ 를 $ C^\prime = (v_0, e_1, v_1, \cdots, e_i, v_i, e_{j+1} , v_{j+1} , \cdots, e_n, v_n ) $ 처럼 대체할 수 있다. $ C^\prime $ 이 $ v $ 에서 $ v $ 로의 단순 사이클이 아니라면 앞과정을 반복하고, 결국 $ v $ 에서 $ v $ 로의 단순 사이클을 얻을 수 있다.

 

---

해밀턴 사이클

 

주어진 그래프에서 출발과 도착 정점은 각 한 번씩 두 번, 나머지 각 정점은 한 번씩만 포함되는 사이클을 해밀턴 사이클이라 한다. 판매원 방문 문제(traveling salesperson problem)가 대표적인 헤밀턴 사이클을 찾는 문제이다.

판매원 방문 문제는 가중 그래프 $ G $ 가 주어질 때 $ G $ 안에서 최소 길이를 가지는 해밀턴 사이클을 찾는 문제이다. 어느 판매원이 도시를 출발하여 존재하는 각 도시를 한 번씩만 방문하여 출발지로 돌아오는 최소 길이의 경로를 찾고자 할 때, 각 도시를 정점으로, 각 도시를 연결하는 도로를 간선으로, 도로의 길이를 가중치로 보면 된다.

$ n $ 개의 간선을 가지는 그래프에 대해서 오일러 사이클을 찾는 시간복잡도가 $ \mathcal{O}(n) $ 인 알고리즘이 알려져 있지만, 실행 시간이 다항식인 해밀턴 사이클을 찾는 알고리즘은 알려져 있지 않다.