Ore's theorem & Palmer's algorithm

Ore's theorem은 그래프에 해밀턴 회로가 존재할 조건과 관련된 정리이다.

Statement를 바로 쓰면 다음과 같다.

 

\(n \ge 3\)개의 정점으로 구성된 단순그래프 \(G\)에서, 모든 비인접(non-adjacent) 정점 \(x, y\)에 대해 \(\deg x + \deg y \ge n\)이 성립하면, \(G\)에는 해밀턴 회로가 존재한다.

 

여담으로 좀 더 강한 조건인 Dirac's theorem (모든 정점의 차수가 \(n/2\) 이상)도 있는데, 딱히 Ore's theorem 증명에 비해 쉬운지는 잘 모르겠다.

 

---

스포일러 방지선

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

Step 1. \(G\) is connected

두 정점 \(x\), \(y\)가 이미 인접(adjacent)한 경우에는 상관이 없다. \(x\)와 \(y\)가 인접하지 않은 경우를 생각하자.

\(\deg x + \deg y \ge n\)이므로, \(x,y\)를 제외한 \(n-2\)개의 정점 중 \(x,y\) 모두와 인접한 정점이 반드시 존재하므로, \(G\)는 connected graph이다.

 

Step 2. The maximal path is a cycle

\(G\)에서 가장 길이가 긴 simple path를 \(P = [v_{1}, v_{2}, \cdots, v_{L}]\)이라고 하자. \(v_{1}\)과 \(v_{L}\)이 인접한 경우는 \(P\)자체가 cycle이 되므로 OK. 역시 인접하지 않은 경우를 생각하자. 여기서 \(n = 3\)인 경우를 배제할 수 있으므로 \(n \ge 4\)를 가정해도 좋다.

일단 simple path가 가장 길다는 조건 때문에,  \(v_{1}\)이나 \(v_{L}\)은 어떤 \(w \notin P\)와도 인접할 수 없다.

즉, \(v_{1}\)과 \(v_{L}\)의 neighbor는 \([v_{2}, \cdots , v_{L-1}]\)로 한정된다. 다음을 만족하는 \(i\)의 존재성을 보이면 \(P\)의 정점들이 단순 cycle을 이룸을 증명할 수 있다:

$$ \exists \ 2 \le i \le L-2 \text{ s.t. } v_{1} - v_{i+1}, v_{i} - v_{L}$$

대충 비둘기집 원리로 보여지게 생겼다. \(i\)로 가능한 수는 \(L-3 \le n-3\)개이고, \((\deg x - 1) + (\deg y - 1) \ge n-2\)이므로 위 조건을 만족하는 \(i\)의 존재성을 보였다. \(\blacksquare\)

 

언젠가 이 증명을 까먹고 이해하지 못할 나를 위해 접은글로 보다 상세한 설명을 써두었다.

\(a_{i}\)를 "\(v_{1}\)과 \(v_{i+1}\)이 adjacent하다",

\(b_{i}\)를 "\(v_{i}\)와 \(v_{L}\)이 adjacent하다"라고 보자.

\(2 \le i \le L-2\)이므로, 적어도 \(\deg x - 1\)개의 \(i\)에 대해 \(a_{i}\)가 참이고, \(\deg y - 1\)개의 \(i\)에 대해 \(b_{i}\)가 참이다. 이 둘의 합이 \(n-2 > n-3 \ge L-3\)이므로 적어도 어떤 하나의 \(j\)에 대해 \(a_{j}\)와 \(b_{j}\)가 모두 참이다.

 

Step 3. The maximal cycle is Hamiltonian

마무리 단계다. 만약 \(w \notin P\)가 존재한다고 하자. \(G\)는 connected이기 때문에 어떤 \(v \in P\)와 \(w\)가 인접해야 하는데, \(P\)의 정점들은 cycle을 이루므로 \(P \cup \{w\}\)가 path가 되도록 할 수 있다. 이는 \(P\)가 maximal path라는 가정에 모순이고, 따라서 \(P\)는 모든 정점을 포함한다. 이는 Hamiltonian cycle의 정의와 부합한다. \(\blacksquare\)

 

 

Palmer's CRISS - CROSS algorithm

Ore's theorem을 만족시키는 그래프에서는 Hamiltonian cycle을 찾는 \(\mathcal{O}(n^2)\) 알고리즘이 존재한다.

주어진 정점들을 원 위에 놓은 것을 \(v_{1}, v_{2}, \cdots, v_{n}, v_{n+1}=v_{1}\)이라고 하자.

 

<algorithm>

\(i = 1\cdots n\)을 돌면서 \(v_{i} , v_{i+1}\)이 인접하지 않은 \(i\)를 찾지 못했다면 사이클을 찾은 것이므로 terminate.

 

그런 \(i\)를 찾았다면 \(j = 1\cdots n\)을 돌면서 \(v_{i} - v_{j}\), \(v_{i+1} - v_{j+1}\)을 만족하는지 체크한다. Ore's theorem의 전제 조건에 의해 이를 만족하는 \(j \neq i, i+1\)는 반드시 존재해야만 한다.

 

\(j\)를 찾았다면 \([\cdots v_{i} , v_{i+1}, \cdots , v_{j}, v_{j+1}, \cdots ]\)를 재배치해서 \([\cdots v_{i} , v_{j}, \cdots , v_{i+1}, v_{j+1}, \cdots ]\)가 되도록 만들고, \(v_{i+1}\)과 \(v_{j}\) 사이에 있었던 모든 정점의 순서를 뒤집는다.

</algorithm>

 

<algorithm>을 반복할 때마다 인접한 \(v_{i}, v_{i+1}\)의 쌍은 1개 또는 2개씩 반드시 늘어난다. 따라서 <algorithm>은 \(n\)회 안에 terminate함이 보장되며, <algorithm> 한 번은 \(\mathcal{O}(n)\)에 수행할 수 있으므로 전체 시간복잡도는 \(\mathcal{O}(n^{2})\)이 된다.

 

DFS를 이용하여 적당히 긴 경로를 찾아놓는 등의 최적화가 도움이 된다고 한다.

원본 논문에는 Random graph에서 \(p\)를 잘 주면 대부분 잘 된다는 이야기가 적혀 있는데, 별로 관심이 없어 적지 않기로 한다.