13. 그래프 이론과 오일러 순회, 해밀턴 경로 (Euler Tour, Hamiltonian Path)

오일러 경로, 오일러 순회는 연결 그래프의 모든 간선을 단 한 번씩만 방문하며, 시작과 끝이 같은 노드인 보행을 말한다.
이름을 보면 추측할 수 있다시피 레온하르트 오일러가 만들었다.

모든 노드가 짝수 차수를 갖는 연결 그래프는 오일러 경로를 갖는다.

반대로 오일러 경로가 있는 그래프는 모든 노드의 차수가 짝수인 연결 그래프이다.

증명

$W$가 $v_0 - v_1 - \cdots - v_k$로 구성된, 각 간선을 한 번씩만 방문하는 가장 긴 보행, 즉 오일러 경로라 하자.
이때, $G=(V,E)$에서 모든 노드의 차수는 짝수이다.

$v_k$이후로 $W$에는 속하지 않은 다른 간선이 더 이어지는 경로가 있을 경우, 이는 $W$가 가장 긴 보행이라는 전제를 깨므로 거짓이다.

$v_0 \neq v_k$라면, $v_k$가 홀수인 차수를 갖게 되는데, 이렇게 되면 오일러 경로가 아니므로 $v_0 = v_k$이다. 이때, 위 증명에 의해 $G$의 모든 노드가 $W$에 속해있으므로, 모든 노드는 짝수인 차수를 갖는 것을 알 수 있다.

방향 그래프와 인접행렬

방향 그래프에서는 간선의 방향이 제한된다. 또한 차수도 내차수^indegree와 외차수^outdegree로 나뉘는데, 예를들어 $v_1$의 내차수는 1, 외차수는 3이다.

위 방향 그래프 $G=(V,E)$에 대한 인접행렬 $A={a_{i,j}$는 다음과 같이 나타낼 수 있다.

$$ A = \begin{bmatrix} 1&1&1\\0&0&1\\0&1&0 \end{bmatrix}$$

이때, 인접행렬을 $k$ 제곱한 행렬의 값 $p_{i,j}^k$는 $v_i$에서 $v_j$까지의 길이 $k$인 방향 보행의 수를 나타낸다.

예를들어, 위 행렬 $A$를 제곱한 아래 행렬을 보자.

$$A^2 = \begin{bmatrix}1&2&2\\0&1&0\\0&0&1\end{bmatrix}$$

이는, $v_1$에서 $v_3$으로 향하는 길이가 2인 보행이 2가지 존재함을 나타낸다. 실제로 세어보면, $v_1 - v_1 - v_3$와 $v_1 - v_2 - v_3$로 두 가지가 있다.

방향 그래프 용어

어떤 방향 그래프 $G$에서, 모든 노드간에 오고갈 수 있는 경로가 존재하면 강하게 연결되었다^{Strongly Connected}고 한다.

순환이 없는 방향 그래프를 Directed Acyclic Graph(DAG)라고 한다.

토너먼트 그래프^{Tournament Graph}

출처: 위키백과

어떤 방향 그래프 $G=(V, E)$에서, $V$안의 모든 서로 다른 노드 $u, v$에 대해 $u\rightarrow v$ 혹은 $v \rightarrow u$ 경로가 존재하면, 토너먼트 그래프라고 한다.

해밀턴 경로^{Hamiltonian Path}

해밀턴 경로는 방향 그래프의 모든 노드를 각각 한 번씩만 방문하는 경로이다.
토너먼트 그래프는 하나의 해밀턴 경로를 가진다.

증명

귀납법을 통해 토너먼트 그래프가 해밀턴 경로를 가짐을 증명할 수 있다.
n이 그래프의 노드 갯수라고 할 때, $P(1)$은 참이다.

$P(n+1)$에서, 노드 $v$하나를 그래프에서 제외해보자. $P(n)$이 참이므로, 남은 노드들은 나름의 해밀턴 경로를 만들 것이다.

이제 다시 $v$를 그래프에 넣어보자. 토너먼트 그래프이므로, 해밀턴 경로가 끝난 노드 $v_n$에서, $v$로 향하는 간선이나, $v_{n-k}$에서 $v$, $v$에서 $v_{n-k+2}$로 향하는 간선들이 존재한다. 즉, $v$를 노드가 $n$개인 해밀턴 경로에 끼워넣을 수 있다.

그러므로 토너먼트 그래프에선 항상 해밀턴 경로가 존재하게 된다.