어느 작은 마을의 우체부의 고민을 한번 들어봅시다. 이 마을은 하도 작아서 마을의 우체부는 이 사람 혼자입니다. 이 우체부의 하루 일과는 아침에 모든 우체통에 들어있는 편지나 소포를 우체국으로 가지고 오는 것으로 시작합니다. 잘 아시다시피 우체통은 길가에 듬성듬성 설치되어 있죠. 다시 말해, 마을의 모든 길을 최소한 한 번은 지나간다면 모든 우체통을 방문할 수 있게 됩니다. 이 우체부는 아침 일과를 빨리 끝내고 돌아와 아침 햇살을 쬐며 한 잔의 커피를 즐기는 낭만(?)적인 사람입니다. 그래서 어떻게 하면 가장 짧은 경로로 마을의 모든 길목을 지나칠 수 있을지 고민하고 있습니다. 과연 모든 길목을 최소 한 번씩은 지나는 가장 짧은 경로는 어떻게 구할 수 있을까요?
이 우체부가 고민하는 문제가 바로 중국인 우체부 문제(Chinese postman problem)입니다. 이 문제가 중국인 우체부 문제로 불리는 이유는 우체부가 중국 사람이라서가 아니라 이 문제를 연구한 중국인 수학자 Guan Meigu(管梅谷)를 기리기 위해서입니다. 개인적으로 이 사실을 알고 나서는 약간 기분이 상하더군요. 학계에 큰 영향을 준 문제나 알고리즘에 대해 이를 기리기 위하여 해당 연구자의 이름을 붙이는 경우가 많습니다. 그런데 '중국인'이라니요. 아무튼 그 때문인지는 모르겠지만, 영문 위키피디아에서는 경로 탐색 문제(route inspection problem)라는 제목으로 글이 등재되어 있더군요. 그럼에도 중국인 우체부 문제로 더 잘 알려져 있어서, 이 글에서도 중국인 우체부 문제라는 용어를 쓰도록 하겠습니다.
문제 정의 및 해결 전략
이 문제가 어떤 느낌의 문제인지는 알아봤으니, 이제 문제를 엄밀하게 정의해 보도록 하죠. 이 문제에서는 어떤 방향이 없고 연결된(undirected & connected) 그래프 \(G = (V, E)\)와 간선 위의 거리 \( d : E \rightarrow \mathbb{Q}_+ \)가 함께 주어집니다.
우리의 목표는 한 정점에서 출발하여 모든 간선을 적어도 한 번은 지나 다시 출발한 정점으로 돌아오는 방법 중 가장 거리가 짧은 것을 찾는 것입니다.
과연 이 문제를 어떻게 하면 풀 수 있을까요? 바로 들어가기 앞서, 한 가지 도움이 될 만한 것을 생각해 보도록 합시다. 아마 중학생 때나 고등학생 때 한붓그리기에 대해서 배우셨을 것입니다. 만약 입력된 그래프 \(G\)가 한붓그리기가 가능한 그래프라면 어떻게 될까요? 그러면 이 그래프에는 모든 간선을 정확히 한 번씩만 지나서 출발한 지점으로 되돌아오는 경로가 존재하며, 그 경로는 곧장 최적해가 될 것입니다. 모든 간선을 최소한 한 번은 지나야 하니, 정확히 한 번씩 지나는 경로는 당연히 가장 좋은 경로가 되겠죠?
잘 아시다시피, 어떤 그래프에 한붓그리기가 존재할 조건은 너무도 유명합니다. 굳이 아래 정리를 증명하지는 않겠습니다.
정리 1. 한붓그리기 조건
어떤 그래프에 한붓그리기가 존재할 필요충분조건은 그래프의 모든 정점의 차수가 짝수라는 것이다.
하지만 안타깝게도 입력된 그래프에 홀수의 차수를 갖는 정점이 존재할 수 있습니다. 당장 그림 1의 그래프에서도 홀수의 차수를 갖는 정점을 다음 그림과 같이 쉽게 확인할 수 있죠.
즉, 그래프에 홀수 차수를 갖는 정점이 존재하면 우리는 어쩔 수 없이 어떤 간선을 두 번 이상 방문할 수 밖에 없게 됩니다. 그러면 그 거리를 최소화 시키는 것이 중요하겠죠. 이렇게 추가로 지나야 하는 간선은 한 가지 재미있는 성질을 가지고 있습니다. 예시를 통해서 먼저 알아보죠. 그림 2의 경로에서 원래 그래프에 있던 간선을 하나씩 제외해 보겠습니다. 그러면 다음 그림과 같은 간선의 집합을 얻게 됩니다.
바로 이 간선들이 어쩔 수 없이 두 번 이상 지나간 것들입니다. 이들을 유심히 살펴보면 다음과 같은 사실을 발견할 수 있습니다. 바로, 원래 그래프에서 홀수의 차수를 가진 정점들은 이 간선들에 의해서도 홀수의 차수를 갖게 되고, 반대로 짝수 차수였으면 이 간선들에 의해서도 짝수의 차수를 갖는다는 점입니다.
이는 사실 모든 간선을 최소한 한 번은 지나면서 처음 출발했던 정점으로 돌아오는 아무 경로에 입력 그래프의 간선을 하나씩 빼면 반드시 성립하는 성질입니다. 앞의 경로를 일종의 multigraph라고 생각한다면, 이 경로 자체가 한붓그리기가 됩니다. 그러니 이 경로(로 만들어진 그래프)에 의해서는 모든 정점이 짝수의 차수를 갖게 되겠죠. 따라서 입력 그래프에서 홀수의 차수를 갖고 있다면, 짝수에서 홀수를 빼는 것이니 두 번 이상 방문한 간선들에 의해서는 홀수의 차수를 갖게 되고, 반대로 입력 그래프에서 짝수 차수의 정점이면 결과적으로 짝수의 차수를 반드시 갖게 되는 것입니다.
따라서 주어지는 그래프에서 홀수 차수를 갖는 정점의 집합에 대해 홀수의 차수를 갖고, 반대로 원래 짝수 차수를 갖는 정점이라면 짝수의 차수를 갖도록 하는 간선의 부분집합 중 가장 거리가 짧은 것을 구하면 중국인 우체부 문제를 해결할 수 있게 됩니다. 바로 위 과정을 역으로 돌리면 됩니다. 원래 그래프에다 위 조건을 만족하는 간선을 덧대면 모든 정점의 차수가 짝수인 (multi-)graph가 완성되고, 이렇게 만들어진 그래프에서 한붓그리기를 찾으면 그것이 바로 우리가 원하는 결과가 됩니다.
이제부터 찾고자 하는 것에는 특별한 이름이 붙어있습니다. 바로 \(T\)-join입니다.
정의 1. \(T\)-join
어떤 방향이 없는 그래프 \(G = (V, E)\)와 함께 정점의 부분집합 \(T\)가 주어졌다고 하자. 여기서 \(T\)의 크기는 반드시 짝수이다. 이때, 어떤 간선의 부분집합 \(J \subseteq E\)에 대해, \(T\)에 속한 정점은 \(J\)에 의해 홀수의 차수를 갖고 반대로 \(T\)에 속하지 않은 정점은 \(J\)에 의해 짝수의 차수를 갖는다면, \(J\)를 \(T\)-join이라고 부른다.
그림 4에서 나타난 간선들은 원래 그래프 \(G\)에서 홀수의 차수를 갖는 정점(빨간색으로 칠해진 정점)을 \(T\)라고 했을 때, \(T\)-join이 된다는 사실을 알 수 있습니다.
여기서 한 가지 짚고 넘어가야 할 점은 바로 원래 그래프에서 홀수의 차수를 갖는 정점의 개수가 짝수 개인지에 대한 것입니다. 왜냐하면 \(T\)-join의 정의 자체가 짝수 개수의 \(T\)를 가정하고 있기 때문이죠. 이 사실도 쉽게 알 수 있습니다. 바로 악수 정리(handshaking lemma)를 통해서 말이죠.
정리 2. 악수 정리(handshaking lemma)
어떤 방향이 없는 그래프가 주어졌을 때, 모든 정점의 차수의 합은 정확히 간선의 개수의 두 배이다.
[증명] 처음에는 정점만 주어지고, 간선을 하나씩 넣는다고 상상해보겠습니다. 간선이 하나 들어갈 때마다 간선의 양 끝점의 차수가 정확히 1씩 증가하게 됩니다. 즉, 간선이 하나 추가될 때마다 모든 정점의 차수의 합은 정확히 2씩 증가하게 되는 것이죠. 따라서 간선을 모두 집어넣으면 모든 정점의 차수의 합이 그 개수의 정확히 두 배가 되게 됩니다. ■
악수 정리를 통해서 알 수 있는 것은 반드시 모든 정점의 차수의 합은 짝수가 되어야 한다는 것입니다. 여기서 짝수 차수를 갖는 정점의 개수가 아무리 많다고 하더라도 모든 정점의 차수의 합의 홀짝성(parity)에는 영향을 주지 않습니다. 근데 홀수 차수의 정점이 만약 홀수 개가 있다면, 모든 정점의 차수의 합은 홀수가 되게 됩니다. 이는 모순이죠. 그러니 홀수 차수의 정점은 반드시 짝수 개가 존재한다는 사실을 알 수 있게 됩니다.
참고로 홀수 크기의 \(T\)에 대해서는 \(T\)-join이 정의되지 않습니다. 그 이유도 악수 정리를 통해서 쉽게 보일 수 있습니다.
Minimum \(T\)-join 구하기
이 절에서는 임의의 \(T\)에 대해서 minimum \(T\)-join을 구하는 방법을 알아보도록 하겠습니다. 문제를 좀더 상세히 기술해보자면, 입력으로는 어떤 방향이 없는 그래프 \(G = (V, E)\), 간선 위의 거리 \(d : E \rightarrow \mathbb{Q}_+\)와 함께 짝수 크기를 갖는 정점의 부분집합 \(T \subseteq V\)가 주어집니다. 우리가 구해야 하는 것은 거리가 가장 짧은 \(T\)-join입니다.
어떻게 하면 이를 구할 수 있을까요? 바로 minimum-cost perfect matching을 통해서 구할 수 있습니다. 물론 minimum-cost pefect matching을 구하는 것도 간단한 일은 아니지만, 다항 시간에 구할 수 있다는 것이 잘 알려져 있습니다. 따라서 minimum-cost perfect matching을 구하는 알고리즘을 알고 있다는 전제 아래 minimum \(T\)-join을 구하는 알고리즘을 적어 보도록 하겠습니다.
알고리즘 1. An algorithm for the minimum \(T\)-join
입력: 방향이 없는 그래프 \(G = (V, E)\), 거리 \(d: E \rightarrow \mathbb{Q}_+\), \(T \subseteq V\) (단, \(|T|\)는 짝수)
출력: 거리가 가장 짧은 \(T\)-join
- 다음과 같이 간선 비용 \(c\)가 있는 새로운 보조 그래프(auxiliary graph) \(H\)를 만든다.
- \(H\)는 \(T\)를 정점으로 하는 완전 그래프(complete graph)이다.
- 임의의 두 정점 \(u, v \in V(H)\)에 대해 간선 비용 \(c(u, v)\)는 \(G\) 위에서 \(u\)에서 \(v\)로 가는 최단 경로의 거리로 정의한다. 만약 도달할 수 없으면 \(+ \infty\)로 정의한다.
- \(H\) 위에서 비용을 \(c\)로 하는 minimum-cost perfect matching \(M\)를 찾는다.
- 만약 \(M\)의 비용이 \(+\infty\)이면 \(G\)에는 \(T\)-join이 존재하지 않는다고 반환하고 알고리즘을 끝낸다. 그렇지 않으면 아래를 수행한다.
- \(J \gets \emptyset \)
- 각 간선 \( (u, v) \in M\)에 대해 다음을 수행한다.
- \(G\) 위에서 \(u\)에서 \(v\)로 가는 최단 경로 \(P\)를 구한다.
- \(P\)의 각 간선 \(e\)에 대해, 만약 \(e \in J\)이면 \(e\)를 \(J\)에서 제거한다. 반대로 \(e \notin J\)이면 \(e\)를 \(J\)에 추가한다.
- \(J\)를 반환한다.
이 알고리즘을 간략히 설명하자면, 정점은 \(T\), 간선의 비용은 \(G\)의 최단 경로의 거리로 하는 완전 그래프 \(H\)를 만들고 그 위에서 minimum-cost pefect matching \(M\)를 찾습니다. 그후, \(M\)의 각 간선 \((u,v)\)에 대해서 \(G\) 위에서 \(u\)와 \(v\)를 잇는 최단 경로 \(P\)를 구합니다. 만약 \(P\)의 각 간선이 \(J\)에 이미 포함되어 있으면 제거하고 \(J\)에 없으면 집어넣는 작업을 합니다. 다시 말해, \(J\)와 \(P\)의 대칭차(symmetric difference)를 새로운 \(J\)로 갱신하는 것이죠. 그렇게 얻은 \(J\)가 minimum \(T\)-join이 되겠습니다.
이제부터 이 알고리즘이 올바르게 동작한다는 것을 보이도록 하겠습니다. 첫 번째로 증명할 것은 원래 입력 \(G\)에 minimum \(T\)-join \(J\)가 존재하면 \(H\) 위에는 \(d(J)\)보다 작거나 같은 비용의 perfect matching이 존재한다는 것입니다. 다음 정리는 아래에서 요긴하게 사용될 minimum \(T\)-join이 갖는 특성을 나타낸 것입니다.
정리 3. Minimum \(T\)-join의 비순환성
어떤 그래프 \(G = (V, E)\), 거리 \(d : E \rightarrow \mathbb{Q}_+\), 짝수 크기의 \(T \subseteq V\)가 주어졌을 때, 만약 \(G\) 위에 \(T\)-join이 존재한다면, \(G\) 위에는 순환(cycle)이 없는 minimum \(T\)-join도 존재한다.
[증명] \(G\) 위의 아무 minimum \(T\)-join \(J\)를 가지고 오고 \(J\)에 어떤 순환 \(C\)가 존재한다고 합시다.
모든 정점은 임의의 순환에 대해 짝수의 차수를 가지므로 \(J\)에서 \(C\)의 간선을 제거한다고 하여도 모든 정점의 홀짝성에는 아무런 영향을 주지 않습니다. 따라서 \(J \setminus C\)도 \(T\)-join입니다. 거리 \(d\)는 음이 아닌 수이기 때문에 \( J \setminus C \)는 \(J\)보다 거리가 길지 않습니다. 따라서 \(J \setminus C\)도 minimum \(T\)-join이 됩니다. 이 작업을 순환이 없을 때까지 반복하면 원하는 결과를 얻을 수 있습니다. ■
위 정리를 통해 만약 \(G\)에 minimum \(T\)-join \(J\)가 존재하면, \(J\)에 순환이 없다고 가정할 수 있습니다. 추가로 일반성을 잃지 않고 \(J\)를 tree라고 하겠습니다. 이렇게 생각할 수 있는 이유는, 만약 \(J\)가 forest라면 각 연결 성분(connected component)이 tree가 되고, 아래 보여드릴 작업을 각 연결 성분마다 수행하면 되기 때문입니다.
\(J\) 위의 아무 정점을 하나 고른 후 이를 root로 하는 rooted tree로 보겠습니도. 또, \(\ell := \frac{|T|}{2}\)라고 하겠습니다. 최종적으로 보이고자 하는 것은 다음의 조건을 만족하는 \(\ell\) 개의 서로 다른 경로 \(P_1, \cdots, P_\ell\)입니다.
- 각 경로는 \(J\) 위에 존재한다. 즉, \( P_1 \cup \cdots P_\ell \subseteq J \)이다.
- 이 경로들은 서로 간선을 공유하지 않는다.
- 각각의 경로의 끝점은 반드시 \(T\)에 속한 정점이며, 모든 경로는 서로 끝점을 공유하지 않는다. 다시 말해, 모든 경로의 끝점을 모아 놓으면 정확히 \(T\)가 된다.
이는 귀납적으로 증명하도록 하겠습니다. \(J\) 위의 어떤 정점 \(v\)에 대해 이를 root로 하는 subtree를 \(S_v\)라고 부르겠습니다. 아래 정리는 모든 subtree에 대해서도 위와 비슷하게 분석할 수 있다는 것을 보여줍니다.
정리 4. Packing paths on a \(T\)-join
순환이 없는 rooted tree인 \(T\)-join \(J\)의 임의의 subtree \(S_v\)에 대해, \(T^\prime := V(S_v) \cap T\), \(\ell^\prime := \left\lfloor \frac{|T|}{2} \right\rfloor \)라고 하자. 만약 \(|T^\prime|\)이 짝수이면 다음을 만족하는 \(\ell^\prime\) 개의 서로 다른 경로 \(Q_1, \cdots, Q_{\ell^\prime}\)이 존재한다.
- 각 경로는 \(S_v\) 위에 존재한다.
- 이 경로들은 서로 간선을 공유하지 않는다.
- 모든 경로의 끝점을 모아 놓으면 정확히 \(T^\prime\)이 된다.
반대로 만약 \(|T^\prime|\)이 홀수이면 다음을 만족하는 \(\ell^\prime + 1\) 개의 서로 다른 경로 \( Q_1 \cdots Q_{\ell^\prime} \), 그리고 \(R\)이 존재한다.
- 각 경로는 \(S_v\) 위에 존재한다.
- 이 경로들은 서로 간선을 공유하지 않는다.
- 각 \(Q_i\)는 \(T^\prime\)에 속한 정점을 끝점으로 가진다. 반면 \(R\)은 한 끝점은 \(T^\prime\)에 속한 어떤 정점으로 다른 끝점은 \(v\)로 하는 경로이다. 즉, 모든 경로의 끝점을 전부 모으면 정확히 \( T^\prime \cup \{ v \} \)가 된다.
[증명] \(J\)의 root로 부터의 거리가 먼 순서대로, 즉 leaf에서 root의 방향으로 귀납적으로 증명하도록 하겠습니다. 만약 \(v\)가 leaf라면 \( T^\prime = \{v\} \)를 만족하게 됩니다. 따라서 \(R\)을 \(v\)에서 시작해서 \(v\)에서 끝나는 길이가 0인 경로로 두면 홀수일 때의 조건 a, b, c를 모두 만족하게 됩니다.
이제 임의의 \(v\)에 대해 보이도록 하겠습니다. 아래에서는 \(|T^\prime|\)이 홀수인 경우에 대해서만 고려하고자 합니다. 비슷한 분석 방식을 활용하면 짝수인 경우에 대해서도 쉽게 증명하실 수 있으리라 생각합니다. \(v\)의 자식을 \(u_1, \cdots, u_k\)라고 부르겠습니다. \(v\)가 \(T^\prime\)에 속하지 않을 때와 속할 때로 나누어 분석하겠습니다.
첫 번째로 \(v \notin T^\prime\)인 경우입니다. \(|V(S_{u_i}) \cap T^\prime|\)이 짝수인 \(S_{u_i}\)는 induction hypothesis에 의해서 그 자체로 \(V(S_{u_i}) \cap T^\prime\)의 모든 정점을 짝지어 잇는 경로가 존재하게 됩니다. 반대로 \(|V(S_{u_i}) \cap T^\prime|\)이 홀수인 \(S_{u_i}\)는 indcution hypothesis에 의해 어떤 \(V(S_{u_i}) \cap T^\prime\)에 속한 정점과 \(v\)를 연결하는 경로가 존재합니다.(나머지는 모두 연결되어 있고요.) 각각을 \(R_i\)라고 부르겠습니다.
\(|T^\prime|\)은 홀수이면서 \(v \notin T^\prime\)이므로 \( |V(S_{u_i}) \cap T^\prime| \)이 홀수인 subtree \(S_{u_i}\)의 개수는 홀수가 됩니다. 이 성질을 만족하는 자식들을 두 개씩 짝을 짓겠습니다. 그러면 정확히 하나의 자식을 빼고 모든 자식이 짝지어집니다. 만약 \(u_i\)와 \(u_j\)가 짝이 지어졌다면, \[R_i \circ (u_i, v) \circ (v, u_j) \circ R_j\]를 만들어 줍니다.(여기서 \(\circ\)는 경로를 연장하는 것을 나타내는 연산자입니다.) 반대로 짝이 없는 자식은 곧장 \(v\)와 연결해 줍니다. 즉, 해당 자식을 \(u_t\)라고 하였을 때 \[ R := R_t \circ (u_t, v) \]를 만들어 주면 됩니다. 이 경로를 \(R\)로 하고 induction hypothesis에 의해 이전부터 만들어 졌거나 짝이 지어져서 양 끝점이 \(T^\prime\)에 속하는 경로들은 모두 \(Q_1, \cdots, Q_{\ell^\prime}\)으로 해주면 모든 조건을 충족하게 됩니다.
마지막으로 \(v \in T^\prime\)인 경우는 \( |V(S_{u_i}) \cap T^\prime| \)이 홀수인 자식의 개수가 짝수가 될 것이기 때문에 이 자식들을 서로 모두 짝짓는 방법이 존재합니다. 따라서 위와 같이 경로를 만들어 준 후, \(R\)은 \(v\)에서 \(v\)로 끝나는 길이가 0인 경로로 설정하면 모든 조건을 충족하게 됩니다. ■
위 정리를 사용하면 우리가 원하는 결과를 얻을 수 있습니다.
정리 5. \(T\)-join과 perfect matching의 관계 1
알고리즘 1의 입력 그래프 \(G\) 위에 minimum \(T\)-join \(J\)가 존재할 때, \(H\) 위에는 \(d(J)\)보다 작거나 같은 비용의 perfect matching이 존재한다.
[증명] \(|T|\)가 짝수라는 사실과 정리 4를 통해 조건 A, B, C를 모두 만족하는 경로 \(P_1, \cdots, P_\ell\)이 존재한다는 것을 알 수 있습니다. 각 \(P_i\)의 끝점을 \(u_i\)와 \(v_i\)라고 할 때, \[ M := \{ (u_1, v_1), \cdots, (u_\ell, v_\ell) \} \]이라고 하겠습니다. 조건 C에 의해 \(M\)이 \(H\) 위의 perfect matching이라는 사실을 이끌어 낼 수 있습니다. 또한 정의에 따르면 \(c(u_i, v_i)\)는 \(G\) 위에서 \(u_i\)에서 \(v_i\)로 가는 최단 경로의 거리이므로 \[ c(u_i, v_i) \leq d(P_i) \]라는 사실을 이끌어낼 수 있습니다. 이를 통해 \[ c(M) \leq \sum_{i = 1}^{\ell} d(P_i) \leq d(J)\]라는 사실을 얻을 수 있습니다. 이때, 두 번째 부등식은 조건 A와 조건 B를 통해 유도할 수 있습니다. ■
이것으로 \(G\) 위에 minimum \(T\)-join이 존재할 경우 그 거리보다 길지 않은 크기의 비용을 갖는 perfect matching이 \(H\)에 존재함을 보였습니다. 따라서 알고리즘 1의 단계 2에서 얻는 minimum-cost perfect matching은 그 비용이 minimum \(T\)-join의 거리보다 작거나 같다는 사실을 알 수 있죠. 이제 반대의 사실을 보이도록 하겠습니다. 즉, \(H\) 위의 minimum-cost perfect matching \(M\)을 가지고 그 비용보다 작거나 같은 거리를 갖는 \(G\) 위의 \(T\)-join을 만들어 보겠습니다. 특히 알고리즘 1의 단계 5를 거치는 것으로 원하는 결과를 얻을 수 있다는 것을 보이도록 하죠. 그러면 자연스럽게 \( d(J) \geq c(M) \geq d(J) \)가 성립하여 알고리즘이 반환하는 \(J\)가 minimum \(T\)-join이라는 것을 증명하게 됩니다.
정리 6. \(T\)-join과 perfect matching의 관계 2
\(H\)의 어떤 minimum-cost perfect matching \(M\)에 대해, 알고리즘 1을 수행한 후에 얻은 \(J\)는 \(d(J) \leq c(M)\)을 만족한다.
[증명] 알고리즘에서 매번 \(P\)를 덧댈 때마다 정확히 \(P\)의 끝점인 \(u\)와 \(v\)의 홀짝성만 뒤바꾼다는 것을 보이도록 하겠습니다.
단계 5를 시작할 때의 \(J\)를 \(J^{\mathsf{beg}}\), 끝난 후의 \(J\)를 \(J^\mathsf{end}\)라고 하겠습니다. 먼저 \(J^\mathsf{beg}\)에 중복을 허용하여 \(P\)의 간선을 모두 넣은 것을 \(J^\prime\)이라고 하겠습니다. 일반성을 잃지 않고 \(P\)를 순환이 없는 단순 경로라고 가정하겠습니다. 그러면 정확히 \(u\)와 \(v\)의 차수만 \(P\)에 의해 1이고 나머지 정점은 2(또는 0)이 됩니다. 따라서 \(J^\mathsf{beg}\)에 \(P\)를 덧대면 정확히 \( u \)와 \(v\)의 차수만 홀짝성이 뒤바뀌게 됩니다.
만약 어떤 간선이 \(J^\mathsf{beg}\)와 \(P\)에 동시에 참여한다면 \(J^\prime\)에서는 이 간선이 두 개가 중복된 상태입니다. 따라서 이 두 간선을 동시에 제거하면 양 끝점의 차수를 2씩 낮추는 효과이므로 홀짝성에는 영향을 주지 않습니다. 이 작업을 그러한 모든 간선에 적용하면 정확히 \( J^\mathsf{end} \)가 됩니다. 각 간선이 이루는 거리는 음이 아닌 수이므로 간선을 제거한다고 거리가 늘어나지 않습니다. 따라서 \[ d(J^\mathsf{end}) \leq d(J^\mathsf{beg}) + d(P) \]라는 사실을 알 수 있습니다.
\(M\)은 perfect matching이므로 \(M\)의 간선들은 서로 정점을 공유하지 않습니다. 그러므로 알고리즘의 마지막에 반환되는 \(J\)에 대해 \[ d(J) \leq \sum_{(u,v) \in M} c(u,v) = c(M) \]을 만족하게 됩니다. ■
마치며
이번 시간에는 그래프의 모든 간선을 최소한 한 번은 거쳐서 처음에 출발한 정점으로 다시 돌아오는 방법 중 가장 거리가 짧은 것을 구하는 문제인 중국인 우체부 문제를 공부하였습니다. 이는 한붓그리기의 필요충분조건인 모든 정점의 차수가 짝수여야 한다는 성질을 활용했는데요. 만약 주어지는 그래프에 홀수의 차수를 갖는 정점이 존재하면, 그 정점에 대해서만 홀수의 차수를 갖는 간선의 집합을 본래 그래프에 덧대는 방식으로 원하는 결과를 얻을 수 있다고 논증하였습니다.
따라서 이 문제를 어떤 정점 집합 \(T\)가 주어졌을 때의 거리가 가장 짧은 \(T\)-join을 구하는 문제로 환원하였습니다. 이는 \(T\)를 정점으로 하는 complete graph에서 minimum-cost perfect matching을 구하는 알고리즘을 사용하면 해결할 수 있다는 것을 본문에서 보였습니다. 참고로 임의의 그래프가 주어졌을 때 minimum-cost perfect matching을 구하는 다항 시간 알고리즘이 존재합니다만, 많이 복잡합니다. 개인적으로도 예전에 수업 시간에 들은 것이 다인데, 언젠간 한번 블로그에 정리해 보도록 하죠.
위 문제의 형제 격인 문제가 있습니다. 이번에는 그래프의 모든 간선이 아니라 모든 정점을 최소한 한 번은 거쳐서 처음에 출발한 정점으로 돌아오는 방법을 생각해 봅시다. 이것도 충분히 현실에서는 가능한 이야기죠. 본문에서는 마을의 모든 길목에(그리고 자연스럽게 정점은 교차로에) 비유하고 우체부가 모든 길목을 돌아야 한다고 가정했다면, 이번에는 정점을 모든 집에 비유하고, 우체부가 모든 집을 방문해야 한다고 가정해 보도록 하겠습니다.(굳이 길목을 모두 돌아다닐 필요는 없습니다.) 과연 모든 집을 최소한 한 번은 거치면서 다시 처음 시작한 장소로 돌아오는 방법 중에서 가장 거리가 짧은 것은 어떻게 구할 수 있을까요?
결론부터 말씀을 드리자면, 구하기 어렵습니다. 중국인 우체부 문제에서는 모든 간선을 지나야 한다는 조건에서 한붓그리기, 즉 오일러 회로(Eulerian circuit)와 유사합니다. 오일러 회로를 구하는 건 다항 시간에 가능하다는 것이 잘 알려져 있기도 하고요. 하지만, 이 문제는 일종의 외판원 문제(traveling salesman problem)로 볼 수 있습니다. 외판원 문제는 해밀턴 순환(Hamiltonian cycle)과 유사하죠. 안타깝게도 P=NP가 아닌 이상에야 해밀턴 순환을 다항 시간에 찾기란 불가능합니다.
한 가지 추가로 설명을 드리자면, 어떤 그래프가 주어졌을 때 모든 정점을 최소한 한 번은 지나는 가장 거리가 짧은 방법을 구하는 문제는 거리가 메트릭(metric)으로 주어진 외판원 문제와 동치(equivalent)입니다. 그 증명을 보이지는 않겠습니다만, 한 문제를 푸는 알고리즘을 알고 있으면 다른 문제를 해결할 수 있기 때문입니다. 이 문제를 근사적으로 해결하려는 여러 노력이 있어 왔습니다. 자세한 사항이 궁금하시면 관련된 제 다른 글을 참고하시면 되겠습니다.
[외판원 문제 / TSP] 메트릭 & 2-근사 (Metricity & 2-Approximation)
안녕하세요. 이번에는 traveling salesman problem에 대해서 알아보도록 하겠습니다. 주로 줄여서 TSP라고도 부르며, 제가 알기로 우리말로는 외판원 문제로 불립니다. 개괄적인 설명은 이전 글에서 했습니다. 201..
gazelle-and-cs.tistory.com
궁금하신 점이 있으시거나, 글에 잘못된 내용이 발견되면 알려주시기 바랍니다. 고맙습니다. :)