오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로 포스팅을 할 생각도 있었는지라 블로그에 글을 쓰는 것이 늦어졌습니다. 색다른 주제는 바로 양자 컴퓨팅(quantum computing)입니다. 하도 화제인지라 개인적으로도 공부해 보고 싶었습니다. 처음에는 전혀 이해가 되지 않았는데 이 책 저 책 찾아보면서 공부하다 보니 이제는 좀 이해가 되는군요. 언젠가 해당 주제로 포스팅을 해 보도록 하겠습니다.
각설하고, 이번 글의 주제를 고민하게된 배경에 대해서 간략히 설명을 드리겠습니다. 요새 온라인 메트릭 매칭 문제(online metric matching problem)를 (제가 찾아본 바로는) 기존에는 없던 새로운 모델에서 해결해 보는 연구를 진행하고 있습니다. 그런데 일반적인 메트릭에서 바로 이 문제를 해결해 보려니 너무 어렵더군요. 그래서 라인 메트릭(line metric)이나 트리 메트릭(tree metric)과 같은 특수한 메트릭에서는 해결할 수 있는지 고민해 보았습니다. 그러는 중에 문득 머릿속에서 이런 궁금증이 들더군요.
어떤 거리 함수가 주어졌을 때, 그 함수가 실은 어떤 트리 상에서 두 지점 사이의 최단 경로로 정의될 수 있는지 판단할 수 있을까? 만약 그러한 트리가 존재한다면 이를 다항 시간에 찾을 수 있을까?
혼자서 곰곰이 생각해 봤지만 쉽게 결론이 나지 않았습니다. 그래서 연구실 동료들에게 이 궁금증을 공유했죠. 이런저런 아이디어들이 오갔습니다. 한 동료는 사실 모든 거리 함수가 어떤 트리 상에서의 최단 경로로 표현될 수 있는 것 아니냐는 예상을 했습니다. 이 예상은 함께 순댓국밥을 먹는 와중에 다른 동료가 길이가 4인 순환(cycle)에서 최단 경로로 정의되는 거리 함수는 트리로 표현될 수 없다는 것을 보이면서 논파되었습니다. 이번에는 혹시 이 문제가 NP-난해한(NP-hard) 문제는 아닌가하는 예상이 나왔습니다. 처음에 저는 혹시 그런가 싶었지만 인터넷에서 가볍게 검색을 해 보니 그 예상도 틀렸다는 것을 알게 되었습니다.
이 문제는 거리의 그래프 실현 가능성(graph realizability)이라는 이름으로 많이 연구되었습니다. 특히 어떤 거리 함수가 트리로 실현 가능하다면 해당 트리를 다항 시간에 찾을 수 있다는 결과도 있었습니다. 이번 포스트에서는 이 주제에 대해서 함께 알아 보고자 합니다. 관련된 논문들이 다소 오래된 것들이어서 그런지 읽는데 약간의 어려움이 따랐습니다. 혼자서 이 논문 저 논문 찾아 읽다가 드디어 모든 증명을 완성하고 이 글을 작성합니다.
그래프 실현 가능성
우리에게 지점의 집합 \(V\)와 임의의 두 지점 \(i, j \in V\)에 대해, 해당 두 지점 사이의 거리 \(d(i, j)\) 값이 주어졌다고 합시다. 거리는 대칭입니다. 즉, 임의의 쌍 \(i, j\)에 대해 \(d(i, j) = d(j, i)\)를 만족합니다.
만약 어떤 방향이 없는 그래프(undirected graph) \(G = (W, E)\)와 그 간선 위의 가중치 \(w : E \to \mathbb{R}_+\)에 대해,
- \(W\)가 \(V\)를 포함하고(즉, \(V \subseteq W\)이고),
- 원래부터 \(V\)에 속해있던 임의의 두 정점 \(i, j \in V\)에 대해, \((G, w)\) 위에서 \(i\)에서 \(j\)까지의 최단 경로의 거리가 정확히 \(d(i, j)\)와 같다면
거리 \(d\)가 \((G, w)\)로 실현 가능하다고 정의하겠습니다 반대로 \((G, w)\)는 \(d\)를 실현한다고 말하겠습니다.
정의에 따르면 \(V\) 사이의 거리 \(d\)를 실현하는 그래프 \((G = (W, E), w)\)의 정점 집합 \(W\)는 \(V\)를 모두 포함하고는 있어야 하지만 꼭 같을 필요가 없습니다. 다시 말해, 필요하다면 여분의 정점을 추가하여 \(G\)를 구성할 수 있다는 뜻이죠. 이때 기존부터 있던 \(V\)의 정점들을 주 정점, 새로 추가한 \(W \setminus V\)의 정점들을 보조 정점이라고 부르겠습니다.
필요충분조건
가장 먼저 궁금한 내용은 역시 거리 \(d\)가 언제 실현 가능한지에 대한 것이겠지요. 아래의 간단하지만 흥미로운 정리를 통해 그 답을 찾을 수 있습니다.
정리 1. 그래프 실현 가능성의 필요충분조건
어떤 거리 \(d : \binom{V}{2} \to \mathbb{R}_+ \)가 어떤 가중치가 있는 그래프로 실현 가능한 필요충분조건은
- 임의의 지점 \(i \in V\)에 대해, \( d(i, i) = 0 \);
- 임의의 세 지점 \( i, j, k \in V \)에 대해, \( d(i, j) \leq d(i, k) + d(k, j) \)
를 만족하는 것이다.
[증명] 먼저 거리 \(d\)가 위 조건들을 만족할 때 어떤 그래프로 실현 가능하다는 것을 보이겠습니다. 정점의 집합이 \(V\)와 같은 완전 그래프(complete graph) \(G = (V, E)\)를 하나 만들겠습니다. 그 간선 위의 가중치 \(w : E \to \mathbb{R}_+\)는 임의의 두 지점 \(i, j \in V\)에 대해, \(w(i, j) := d(i, j)\)가 되도록 정의하겠습니다.
이제 이렇게 생성한 \( (G, w) \)가 거리 \(d\)를 실현한다는 것을 보이겠습니다. 현재 \(G\)의 정점 집합은 \(V\)와 같으므로 \(d\)가 정의된 \(V\)를 모두 포함하는 것은 쉽게 알 수 있습니다. 따라서 임의의 \(i, j \in V\)에 대해 \((G, w)\) 위에서 \(i\)에서 \(j\)까지의 최단 경로의 길이가 \(d(i, j)\)와 동일함을 보이면 이쪽 방향 증명이 완료됩니다. 만약 \(i = j\)라면, \((G, w)\)에 음의 가중치를 갖는 간선이 없으므로 최단 경로의 길이는 0입니다. 명제의 조건에서 \(d(i, i) = 0\)이므로 만족합니다.
이제 \(i \neq j\)라고 합시다. 귀류법을 사용하기 위해 \(w(i, j) = d(i, j)\)의 가중치를 갖는 간선 \((i, j) \in E\)가 \((G, w)\) 위에서 \(i\)에서 \(j\)로 향하는 최단 경로가 아니라고 가정하겠습니다. 대신 최단 경로 \(P\)를 \[ P := \langle i, k_1, k_2, \cdots, k_\ell, j \rangle \]이라고 하겠습니다. 즉, 다음의 식이 성립하게 됩니다. \[ w(i, j) > w(i, k_1) + w(k_1, k_2) + \cdots + w(k_\ell, j) \] 이는 \(w\)의 정의에 의해, \[ d(i, j) > d(i, k_1) + d(k_1, k_2) + \cdots + d(k_\ell, j) \]로 쓸 수 있습니다. 이제부터 우변의 처음 두 항을 \(d\)의 두 번째 조건을 활용하여 계속 축소시켜 보겠습니다. 그러면 \[ \begin{array}{rcl} d(i, j) & > & d(i, k_1) + d(k_1, k_2) + \cdots + d(k_\ell, j) \\ & \geq & d(i, k_2) + \cdots + d(k_\ell, j) \\ & \geq & \cdots \\ & \geq & d(i, k_\ell) + d(k_\ell, j) \\ & \geq & d(i, j) \end{array} \]가 되어 모순이 발생합니다. 이것으로 한쪽 방향 증명이 완료되었습니다.
이제 반대 방향을 증명해 보겠습니다. 즉, 거리 \(d\)가 어떤 그래프 \((G=(W, E), w)\)로 실현 가능하면 정리의 두 조건을 모두 만족한다는 것을 보이겠습니다. 첫 번째 조건은 어렵지 않게 보일 수 있습니다. 두 번째 조건은 귀류법으로 증명하겠습니다. 어떤 세 지점 \(i, j, k \in V\)가 \( d(i, j) > d(i, k) + d(k, j) \)라고 가정해 보겠습니다. 그러면 \(d\)의 실현 가능성에 의해 \((G, w)\) 위에서 \(i\)에서 \(j\)까지의 최단 경로의 길이가 \(i\)에서 \(k\)까지의 최단 경로의 길이에 \(k\)에서 \(j\)까지의 최단 경로의 길이를 더한 것보다 길다는 사실을 이끌어 낼 수 있습니다. 하지만 \(i\)에서 \(k\)까지의 최단 경로를 탄 다음 \(k\)에서 \(j\)까지의 최단 경로를 타는 방법은 \(i\)에서 \(j\)까지의 한 가지 경로에 해당하므로 모순입니다. 이로써 모든 증명이 완성됩니다. ■
정리 1을 통해서 우리는 다음의 간단한 성질을 이끌어 낼 수 있습니다.
정리 2. 그래프 실현 가능한 거리에서 거리가 0인 쌍의 성질
그래프로 실현 가능한 거리 \(d : \binom{V}{2} \to \mathbb{R}_+\)와 임의의 지점 \(i, j \in V\)에 대해, \(d(i, j) = 0\)이라면 임의의 \(k \in V\)에 대해, \( d(i, k) = d(j, k) \)이다.
[증명] 정리 1의 두 번째 성질에서 \( i := i, j := k, k := j \)를 대입하면 \[ d(i, k) \leq d(i, j) + d(j, k) = d(j, k)\]를 얻을 수 있습니다. 반대로 \( i := j, j := k, j := i \)를 대입하면 \[ d(j, k) \leq d(j, i) + d(i, k) = d(i, k) \]를 유도할 수 있습니다. 둘을 조합하면 정리의 등식을 얻습니다. ■
위 정리가 알려 주는 사실은 그래프로 실현 가능한 거리에서 어떤 두 지점 \(i, j\)의 거리가 0이라면 다른 모든 지점 사이의 거리가 동일하므로 그냥 하나로 생각해도 무방하다는 것입니다. 그런 지점 쌍들을 모두 하나로 합치는 작업을 진행하면 우리는 일반성을 잃지 않고 모든 쌍에 대해 거리가 0보다 큰 값으로만 이루어져 있다고 가정할 수 있습니다. 이를 가정하면 여러 논의를 보다 편하게 진행할 수 있습니다. 따라서 아래부터는 이를 가정하겠습니다.
보조 정점을 두지 않는 경우
이 절에서는 주어지는 거리 \(d\)를 실현하는 가장 간단한 그래프에 대해서 알아 보겠습니다. 바로 보조 정점을 두지 않는 경우입니다. 정리 1의 증명에서 본 것과 같이, 임의의 \( i, j \in V \)에 대해, \( w(i, j) := d(i, j) \)를 만족하는 완전 그래프(complete graph)는 보조 정점이 없으면서 \(d\)를 실현하는 그래프입니다. 하지만 이 그래프에는 아무래도 \(d\)를 실현할 때 불필요한 간선들이 포함되어 있을 수 있습니다. 아래 정리는 불필요한 간선이 무엇이고, 그것을 제거해도 괜찮다는 사실을 알려 줍니다.
정리 3. 불필요한 간선 지우기
양수로만 이루어진 어떤 거리 \( d: \binom{V}{2} \to \mathbb{R}_+ \)를 실현하는 보조 정점이 없는 그래프 \((G = (V, E), w)\)에 만약 다음을 만족하는 간선 \( (i, j) \in E \)가 있다고 하자.
- \( w(i, j) \geq d(i, k) + d(k, j) \)를 만족하는 정점 \(k \in V\)가 존재한다.
그러면 \(G\)에서 \((i, j)\)를 제거한 그래프도 \(d\)를 실현한다.
[증명] \((G, w)\) 위에서 \(i\)에서 \(k\)를 잇는 최단 경로를 \(P_{ik}\), \(j\)에서 \(k\)를 잇는 최단 경로를 \(P_{jk}\)라고 하겠습니다. 보이고자 하는 것은 \(P_{ik}\)와 \(P_{jk}\) 모두 \((i, j)\)를 사용하지 않는다는 것입니다. 귀류법을 적용하기 위해 \( (i,j) \in P_{ik} \)라고 해 보겠습니다. 그러면 분명 \( P_{ik} \)는 \(i\)에서 \(j\)로 간 다음 \(j\)에서 \(k\)로 향하는 최단 경로를 따라가는 것이어야 합니다. 그러면, \[ d(i, k) = w(P_{ik}) = w(i, j) + w(P_{jk}) = w(i, j) + d(j, k) \]를 만족하게 됩니다. 여기서 첫 번째와 마지막 등식은 \((G, w)\)가 \(d\)를 실현한다는 사실에서 얻을 수 있습니다. 그런데 정리의 조건에서 \(w(i, j) \geq d(i, k) + d(k, j)\)라고 하였으므로, \[ w(i, j) \geq w(i, j) + d(j, k) + d(j, k) \Rightarrow d(j, k) \leq 0 \]을 유도할 수 있습니다. 이는 거리가 0보다 크기만 하다는 사실에 위배됩니다. \( (i, j) \in P_{jk} \)의 경우도 똑같이 증명하면 됩니다.
따라서 \(P_{ik}\)와 \(P_{jk}\)는 모두 \(G\)에서 \((i, j)\)를 제거한 그래프 \(G'\)에서도 살아남아 있습니다. 만약 \((G, w)\) 위에서 어떤 두 지점 사이의 최단 경로가 간선 \((i, j)\)를 사용한다면 \((i, j)\) 대신 \(P_{ik} \cup P_{jk}\)를 사용한 경로도 최단 경로가 됩니다. 더하여 새 경로는 \((i, j)\)를 사용하지 않으므로 분명 \(G'\)에서도 최단 경로를 이룰 것입니다. 따라서 \(G\)에서 임의의 두 지점 사이의 최단 경로 중에는 분명 \((i, j)\)를 쓰지 않는 최단 경로가 존재하고, 그 경로들은 분명 \(G'\)에서도 그대로 유지되므로 \(G'\)도 \(d\)를 실현합니다. ■
위와 같은 방식으로 불필요한 간선을 최대한 지워 보도록 하겠습니다. 과연 아무 순서대로 지워도 결과는 동일할까요? 만약 동일하지 않다면 컴퓨터 과학을 공부하는 사람으로서 남은 간선의 개수가 가장 적든지 남은 간선의 가중치의 합이 가장 적든지 어떤 기준에 따라 "최적의" 실현 그래프를 찾고 싶어할 것입니다. 흥미롭게도 보조 정점을 두지 않는 경우 불필요한 간선이 없는 실현 그래프는 유일합니다.
정리 4. 보조 정점이 없는 경우 실현 그래프의 유일성
양수로만 이루어진 어떤 거리 \(d : \binom{V}{2} \to \mathbb{R}_+\)에 대해, 다음을 만족하는 \( (G = (V, E), w) \)는 유일하다.
- \(G\)는 \(d\)를 실현한다.
- 임의의 간선 \( (i, j) \in E \)와 정점 \(k \in V \setminus \{i, j\} \)에 대해, \(w (i, j) < d(i, k) + d(k, j) \)이다.
[증명] 귀류법을 쓰기 위해 위 조건을 만족하면서 \((G, w)\)와는 다른 \((G' = (V, E'), w')\)을 가정해 보겠습니다. 먼저 어떤 간선 \( (i, j) \)가 \(E\)에도 있고 \(E'\)에도 있지만 \( w(i, j) \neq w'(i, j) \)인 경우를 생각해 보겠습니다. 일반성을 잃지 않고 \(w(i, j) < w'(i, j)\)라고 하겠습니다. (부등호 방향이 반대인 경우는 비슷하게 증명하면 됩니다.) \((G, w)\)는 \(d\)를 실현하므로 \( d(i, j) \leq w(i, j) \)입니다. 여기서 \((G', w') \)도 \(d\)를 실현한다고 했는데 \[ w'(i, j) > w(i, j) \geq d(i, j) \]이므로 간선 \( (i, j) \in E' \)는 \((G', w')\)에서 \(i\)에서 \(j\)로 향하는 최단 경로가 될 수 없습니다. 따라서 \((i, j)\)는 \((G', w')\)에 불필요한 간선이며, 이는 모순입니다.
이제 \((G, w)\)와 \((G', w')\) 중 한쪽에만 간선이 존재할 수 없다는 것을 보이면 증명이 완료됩니다. 일반성을 잃지 않고 \( (i, j) \in E \)이나 \( (i, j) \not\in E' \)라고 하겠습니다. 일단 \( (G, w) \)는 \(d\)를 실현하므로 \[ d(i, j) \leq w(i, j) \]를 만족합니다. 이제 \( (G', w') \)을 생각해 봅시다. \( (G', w') \)도 \(d\)를 실현하지만 \( (i, j) \)가 없으므로 \[ d(i, j) = d(i, k) + d(k, j) \]를 만족하는 \(k \in V \setminus \{i, j\} \)가 존재합니다. 위 두 부등식을 조합하면 \((G, w)\)의 \((i, j)\)가 불필요하다는 사실을 보일 수 있습니다. ■
정리 3과 4를 통해 거리 \(d\)를 보조 정점을 두지 않고 실현하는 그래프를 구하는 간단한 방법을 고안할 수 있습니다.
\(w(i, j) = d(i, j)\)인 완전 그래프를 만든다. 그 위의 모든 간선 \((i, j)\)와 정점 \(k \in V\)에 대해 만약 \( w(i, j) = d(i, k) + d(k, j) \)를 만족하면 \((i, j)\)를 지운다.
이 알고리즘이 \( O(|V|^3) \)에 동작한다는 것은 쉽게 알 수 있습니다. 과연 더 빠르게 구할 수 있을까요? 당장은 잘 모르겠습니다만, 아무래도 \(O(|V|^2)\)이나 \(O(|V|^2 \log |V|)\) 시간 정도에 동작하는 알고리즘이 존재하지 않을까 생각하고 있습니다. 좀더 고민해 보겠습니다.
보조 정점을 두는 경우의 최적의 실현 그래프
이전 절까지는 보조 정점을 두지 않는 경우에 대해서 논의했습니다. 이제는 보조 정점을 두는 경우를 생각해 보겠습니다. 사실 보조 정점을 아무렇게나 둔다면 거리를 실현하는 그래프를 무수히 많이 만들 수 있습니다. 하지만 그러한 실현 그래프들은 의미가 없겠죠. 따라서 보조 정점은 항상 차수(degree)가 3 이상이 되는 경우에만 만들도록 하겠습니다.
그럼에도 여전히 많은 그래프가 하나의 거리를 실현할 수 있습니다. 컴퓨터과학을 공부하는 사람으로서 자연스러운 다음 단계는 "최적의" 실현 그래프를 찾는 것입니다. 최적의 실현 그래프 \((G = (W, E), w) \)는 입력 거리 \(d\)를 실현하면서 모든 간선의 가중치의 합, 즉, \( w(E) := \sum_{e \in E} w(e) \)를 최소로 하는 그래프로 정의됩니다.
그러면 최적의 실현 그래프는 어떤 성질을 갖고 있을까요? 관련하여 몇 가지 흥미로운 성질들을 아래에서 알아 보도록 하겠습니다. 아래에서는 거리 \(d\)를 실현하는 어떤 그래프가 \((G=(W, E), w)\)로 주어졌을 때, 그 위에서 임의의 두 정점 \(x, y \in W\) 사이의 최단 경로의 거리를 \[d_{G,w}(x,y)\]로 표현하겠습니다. 이는 다만 입력으로 주어지는 \(d\)가 주 정점 사이의 거리만을 정의하지만 이제는 보조 정점들과의 거리도 고려해야 하므로 이를 구분하기 위해서 정의한 것입니다. 그렇지만 어차피 우리가 고려하는 그래프는 모두 어떤 거리 \(d\)를 실현하는 그래프이므로 \(d_{G,w}\)가 \(d\)를 확장한 것으로 생각하셔도 무방합니다.
처음으로 알아 볼 성질은 \(d\)를 최적으로 실현하는 그래프에는 길이가 3인 순환(cycle)이 존재하지 않는다는 것입니다.
정리 5. 최적의 실현 그래프에서 길이가 3인 순환의 비존재성
양수로만 이루어진 거리 \(d: \binom{V}{2} \to \mathbb{R}_+\)를 최적으로 실현하는 그래프 \((G = (W, E), w)\)에는 길이가 3인 순환이 존재하지 않는다.
[증명] 모순을 이끌어 내기 위해 \((G, w)\)에 길이가 3인 순환 \(\langle x, y, z, x \rangle\)가 존재한다고 하겠습니다. 만약 \(w(x, y), w(x,z), w(y,z)\) 중에서 어느 두 개의 합이 나머지 하나와 동일한 경우에는 가장 긴 거리의 간선을 지워도 그래프의 거리 실현성을 잃지 않는다는 사실을 쉽게 확인할 수 있습니다. 왜냐하면 어떤 최단 경로가 가장 긴 거리의 간선을 쓴다면, 그 대신 짧은 두 간선으로 교체한 경로도 똑같이 최단 경로가 되기 때문입니다. 이는 \((G, w)\)가 \(d\)의 최적의 실현 그래프라는 사실에 모순이 됩니다.
남은 경우는 어느 두 개의 합이 항상 나머지 하나 보다 크기만 한 경우입니다. 이때는 \((x,y), (x,z), (y,z)\)를 제거하고 대신 새로운 보조 정점 \(t\)를 추가한 후 이를 \(x, y, z\)와 연결해 줍니다. 새로 생긴 간선에 가중치를 적절히 부여하면 우리는 기존의 간선을 대체할 수 있습니다. 엄밀히 말하면, 우리는 그래프 \( (G' = (W \cup \{t\}, E'), w') \)을 다음과 같이 만들어 줍니다.
- \( E' := E \setminus \{ (x,y), (x,z), (y,z) \} \cup \{(t,x), (t,y), (t,z)\} \).
- \( w'(e) := \left\{ \begin{array}{ll} \frac{1}{2}(w(x, y) + w(x,z) - w(y, z)), & \text{if } e = (t,x), \\ \frac{1}{2}(w(x, y) + w(y,z) - w(x, z)), & \text{if } e = (t,y), \\ \frac{1}{2}(w(x, z) + w(y,z) - w(x, y)), & \text{if } e = (t, z), \\ w(e), & \text{otherwise.} \end{array} \right. \)
\((G', w')\)도 \(d\)를 실현합니다. 왜냐하면 \((G, w)\)에서의 \((x,y)\)는 \((G', w')\)에서의 \(\langle x, t, y \rangle\)로, \((x, z)\)는 \( \langle x, t, z \rangle \)로, \( (y, z) \)는 \( \langle y, t, z \rangle \)로 치환되기 때문입니다. 하지만 가중치의 합은 \(x, y, z\)만 고려했을 때, \( w(x, y) + w(x, z) + w(y, z) \)에서 \( \frac{1}{2} (w(x, y) + w(x, z) + w(y, z)) \)로 감소하게 됩니다. 이는 \((G, w)\)가 \(d\)를 최적으로 실현하는 그래프라는 사실에 모순입니다. ■
다음 성질은 \(d\)를 최적으로 실현하는 그래프의 차수가 2 이상인 정점들은 모두 어떤 주 정점의 쌍의 최단 경로를 이루는데 필수적이어야 한다는 것입니다.
정리 6. 최적의 실현 그래프에서 차수가 2 이상인 정점들의 성질
양수로만 이루어진 거리 \(d: \binom{V}{2} \to \mathbb{R}_+\)를 최적으로 실현하는 그래프 \((G = (W, E), w)\)에서 차수가 2 이상인 임의의 정점 \(x \in W\)에 대해, \[ d(i, j) = d_{G,w}(i, x) + d_{G,w}(x, j) \]를 만족하는 주 정점 \(i, j \in V \)가 존재한다.
[증명] 귀류법을 적용하기 위해 임의의 주 정점 쌍 \(i, j \in V\)에 대해, \[d(i, j) < d_{G, w}(i, x) + d(x, j)\]를 만족한다고 하겠습니다. \(G\)에서 \(x \in W\)의 차수가 2 이상이라고 했으므로, \(x\)에 인접한(adjacent) 서로 다른 두 정점 \(y, z \in W\)가 존재합니다. 정리 5에 의해 \((y, z) \not\in E\)이어야 합니다. 다음의 두 경우를 고려해 보겠습니다.
경우 1. \( d(i, j) - d_{G, w}(i, y) - d_{G, w}(z, j) > 0 \)을 만족하는 주 정점 쌍 \(i, j \in V\)가 있는 경우. 앞의 식의 좌변을 가장 크게 만드는 주 정점 쌍을 \(i^*, j^* \in V\)라고 하겠습니다. 이제 다음과 같은 그래프 \((G'=(W, E'), w')\)을 만들어 보겠습니다.
- \(E' := E \setminus \{(x, y), (x, z)\} \cup \{ (y, z) \} \)
- \( w'(e) := \left\{ \begin{array}{ll} d(i^*, j^*) - d_{G, w}(i^*, y) - d_{G, w}(z, j^*), & \text{if } e = (y, z), \\ w(e), & \text{otherwise.} \end{array} \right. \)
즉, 간선 \((x, y), (x, z)\)를 제거하고 \(y\)와 \(z\)를 곧장 이은 그래프에 가중치를 적절히 부여한 것입니다.
먼저, \((G', w')\)도 \(d\)를 실현한다는 것을 보이겠습니다. 가정에서 임의의 주 정점 쌍 \(i, j \in V\)에 대해 \(d(i, j) < d_{G, w}(i, x) + d_{G, w}(x, j)\)였으므로 \(x\)는 어느 최단 경로에도 등장하지 않습니다. 따라서 \((G, w)\) 위에서 임의의 주 정점 쌍을 잇는 최단 경로는 \((G', w')\) 위에서도 해당 쌍을 잇는 한 가지 경로가 되며, 이를 통해 \( d_{G', w'}(i, j) \leq d(i, j) \)임을 이끌어 낼 수 있습니다.
만약 \( d_{G', w'}(i, j) < d(i, j) \)라고 해 보겠습니다. 그러면 이는 분명 \((G', w')\)에 새로 넣은 간선 \((y, z)\) 때문일 것입니다. 즉, 일반성을 잃지 않고 \((G', w')\) 위에서 \(i\)와 \(j\)를 잇는 최단 경로는 \[ \langle i, \cdots, y, z, \cdots, j \rangle \]이라고 할 수 있습니다. 이때, \( \langle i, \cdots, y \rangle \)와 \( \langle z, \cdots, j \rangle \) 부분도 각각 \(i-y\)와 \(z-j\)를 잇는 최단 경로여야 하므로 \[ d_{G', w'}(i, j) = d_{G', w'}(i, y) + w'(y, z) + d_{G', w'}(z, j) \]로 쓸 수 있습니다. 그런데 \( \langle i, \cdots, y \rangle \), \( \langle z, \cdots, j \rangle \) 부분 모두 \( (y, z) \)를 사용하지 않으므로 \[ d_{G', w'}(i, y) = d_{G, w}(i, y), \quad d_{G', w'}(z, j) = d_{G, w}(z, j) \]를 만족합니다. 이 식들을 \(d_{G', w'}(i, j) < d(i, j)\)에 넣고 정리하면 \[ w'(y, z) < d(i, j) - d_{G, w}(i, y) - d_{G, w}(z, j) \]를 유도할 수 있습니다. 하지만 \(w'(y, z)\)의 정의에서 \(i^*, j^*\)는 우변을 최대로 만드는 주 정점 쌍이었으므로 이는 모순입니다. 이것으로 \( (G', w') \)도 \(d\)를 실현한다는 것을 모두 증명하였습니다.
이제 \( w'(y, z) < w(x, y) + w(x, z) \)임을 보이면 \((G, w)\)가 최적의 실현 그래프라는 사실에 모순을 이끌어 내어 이 경우의 증명을 완료할 수 있습니다. 다시, 가정에서 임의의 \(i, j \in V\)에 대해 \(d(i, j) < d_{G, w}(i, x) + d_{G, w}(x, j)\)를 만족하므로, \[ d(i^*, j^*) < d_{G, w}(i^*, x) + d_{G, w}(x, j^*) \]이기도 합니다. 반면, 앞에서 우리는 \[ d_{G', w'}(i^*, y) + w'(y, z) + d_{G', w'}(z, j^*) = d(i^*, j^*)\]라는 사실을 이끌어 냈습니다. 둘을 조합하면 \[ w'(y, z) < (d_{G, w}(i^*, x) - d_{G', w'}(i^*, y)) + (d_{G, w}(x, j^*) - d_{G', w'}(z, j^*)) \leq w(x, y) + w(x, z) \]를 보일 수 있습니다.
경우 2. 모든 주 정점 쌍 \(i, j \in V\)에 대해, \(d(i, j) - d_{G, w}(i, y) - d_{G, w}(z, j) \leq 0\)인 경우. 간선 \((x, y)\)와 \( (x, z) \)를 지우고, \(y\)와 \(z\)를 하나로 병합한 그래프 \((G', w)\)를 고려해 보겠습니다. 그러면 이전과 비슷한 논의를 통해 \((G', w)\)가 \(d\)를 실현하는 그래프임을 알 수 있습니다. 이는 \( (G, w) \)가 최적의 실현 그래프라는 사실에 모순입니다. ■
이제 흥미로운 작업 한 가지를 소개해 드리겠습니다. 이를 위해서는 정의가 하나 필요합니다. 어떤 거리 \(d : \binom{V}{2} \to \mathbb{R}_+\)에서 어떤 지점 \(k \in V\)와 어떤 수 \(a\)에 대해 \(d^{(k, a)} : \binom{V}{2} \to \mathbb{R}\)를 \[ d^{(k, a)}(i, j) := \left\{ \begin{array}{ll} 0, & \text{if } i = j = k, \\ d(i, j) - a, & \text{if } i = k \neq j \text{ or } j = k \neq i, \\ d(i, j), & \text{otherwise} \end{array} \right.\]로 정의하겠습니다. 직관적으로는 \(d^{(k, a)}\)가 \(d\)에서 \(k\)의 주위를 잡아 당겨 팽팽하게 만든 것으로 볼 수 있습니다. 다음의 정리는 \(d^{(k, a)}\)가 그래프 실현 가능한 거리가 되도록 만드는 \(a\)의 구간을 알려 줍니다.
정리 7. 축소된 거리가 그래프 실현 가능하기 위한 필요충분조건
어떤 그래프 실현 가능한 거리 \( d : \binom{V}{2} \to \mathbb{R}_+ \), 어떤 지점 \(k \in V\), 어떤 수 \(a\)에 대해, \( d^{(k, a)} \)가 그래프 실현 가능한 거리가 되기 위한 필요충분조건은 \[ a \leq \min_{i, j \in V \setminus \{k\}} \frac{1}{2} ( d(i, k) + d(k, j) - d(i, j) ) \tag{1} \]이다.
[증명] 해당 범위의 \(a\)라면 \(d^{(k, a)}\)가 정리 1을 만족한다는 것을 보이겠습니다. 반대 방향인 \(d^{(k, a)}\)가 정리 1을 만족하기 위해서는 \(a\)가 해당 범위를 가져야 한다는 것은 비슷한 논의로 보일 수 있습니다.
정의 상 임의의 \(i \in V\)에 대해 \( d^{(k, a)}(i, i) = 0 \)입니다. 이제 임의의 \( x, y, z \in V \)에 대해, \[ d^{(k, a)}(x, y) \leq d^{(k, a)}(x, z) + d^{(k, a)}(z, y) \tag{2} \]를 만족하는지 따져 보겠습니다. 몇 가지 경우로 나누어서 생각해 보겠습니다. 참고로 \(d\)는 그래프 실현 가능하므로 \[ d(x, y) \leq d(x, z) + d(z, y) \tag{3} \]를 만족합니다.
경우 1. \(x, y, z\) 모두 \(k\)와 다르거나 같을 때. 이는 식 2와 식 3이 동일하여 자명하게 성립합니다.
경우 2. \(x = k\)이고 \(y \neq k \), \(z \neq k\)일 때. (이 경우는 \(y = k, x \neq k, z \neq k\)를 포함합니다.)이때는 식 2가 식 3의 좌변과 우변이 각각 동일하게 \(a\)가 감소하는 꼴이므로 성립합니다.
경우 3. \(x = z = k\)이고 \(y \neq k\)일 때. (이 경우는 \(y = z = k, x \neq k\)를 포함합니다.) 식 2를 다시 쓰면 \[ d(k, y) - a \leq 0 + (d(k, y) - a) \Rightarrow 0 \leq 0 \]이 되므로 성립합니다.
경우 4. \(x = y = k\)이고 \(z \neq k\)일 때. 식 2를 다시 쓰면, \[ 0 \leq (d(k, z) - a) + (d(z, k) - a) \Rightarrow a \leq d(k, z) = \frac{1}{2} (d(z, k) + d(k, z) - d(z, z) ) \]가 됩니다. 식 1에서 \(a\)의 상한은 위 식의 우변보다 작습니다. 그러므로 성립합니다.
경우 5. \(z\)만 \(k\)일 때. 이 경우에서 식 2는 \[ d(x, y) \leq (d(x, k) - a) + (d(k, y) - a) \Rightarrow a \leq \frac{1}{2} ( d(x, k) + d(k, y) - d(x, y) )\]와 같이 다시 쓰일 수 있습니다. 경우 4과 같이 식 1에서 \(a\)의 상한은 위 식의 우변보다 작으므로 성립합니다. ■
이제 작업을 소개하겠습니다. \(a^*\)를 식 1의 우변, 즉, \[ a^* := \min_{i, j \in V} \frac{1}{2} (d(i, k) + d(k, j) - d(i, j)) \]로 정의하겠습니다. \(d\)는 그래프 실현 가능하므로 \(a^* \geq 0\)임은 자명합니다. 정리 7에 의해 \(a \leq a^*\)라면 \(d^{(k, a)}\)를 실현하는 어떤 그래프 \((G' = (W', E'), w')\)이 존재합니다. 이 그래프의 주 정점 \(k \in V\)는 어떤 새로운 보조 정점 \( t \)로 치환하고 대신 \(k\)는 \(t\)에만 연결하고 그 가중치를 \(a\)로 하는 그래프를 만들겠습니다. 엄밀히 정의하자면, 다음을 만족하는 \((G = (W, E), w)\)를 만듭니다.
- \( W := W' \cup \{t\} \)
- \( E := \{ (x, y) \in E' \mid x \neq k \text{ and } y \neq k \} \cup \{ (t, x) \mid (k, x) \in E' \} \cup \{ t \} \)
- \( w(e) := \left\{ \begin{array}{ll} w'(x, y), & \text{if } e = (x, y) \in E \cap E' \\ w'(k, x), & \text{if } e = (t, x) \text{ with } x \neq k, \\ a, & \text{if } e = (t, k) \end{array} \right. \)
이 작업은 \(a > 0\)일 때에만 진행합니다. 어차피 \(a = 0\)이면 \(d^{(k, a)} = d\)이고, \(a < 0\)이면 생성된 그래프가 음수의 가중치를 가져야 하기 때문입니다.
이 작업이 최적의 실현 그래프를 구하는데 요긴한 이유는 다음의 정리 때문입니다.
정리 8. 축소된 거리와 최적의 실현 그래프의 관계
임의의 \(0 \leq a \leq a^*\)에 대해, \((G', w')\)이 \(d^{(k, a)}\)를 최적으로 실현하는 그래프라면, 위 작업을 통해 얻은 \((G, w)\)도 \(d\)를 최적으로 실현하는 그래프이다.
[증명] \(a = 0\)이라면 앞에서 말한대로 \(d^{(k, a)} = d\)라서 자명하게 성립합니다. 이제부터 \(a > 0\)이라고 가정하겠습니다. \( (G, w) \)가 \(d\)를 최적으로 실현하는 그래프가 아니라고 합시다. 대신 최적의 실현 그래프를 \( (G^*=(W^*, E^*), w^*) \)라고 하겠습니다. 즉, \[ w^*(E^*) < w(E) = w'(E') + a \]을 만족합니다. 정의 상 \( k \in V \subseteq W^* \)입니다. 이제 경우를 두 가지로 나누어서 생각해 보겠습니다. 먼저 \((G^*, w^*)\)에서 \(k\)의 차수가 2 이상인 경우를 생각해 보겠습니다. 정리의 조건에서 \(a^* > 0\)이라고 했으므로, 임의의 \(i, j \in V \setminus \{k\} \)에 대해 \[ d(i, k) + d(k, j) - d(i, j) > 0 \]가 됩니다. 정리 6에 의해 그러한 \(k\)는 최적의 실현 그래프에 존재할 수 없으며, 따라서 모순입니다.
따라서 이제부터 \((G^*, w^*)\)에서 \(k\)의 차수가 1이라고 가정하겠습니다. 거기서 \(k\)에 인접한 유일한 정점을 \(x \in W^*\)라고 부르겠습니다. 먼저 \( w^*(x, k) > a \)라고 해 보겠습니다. 간선 \((x, k)\) 위에서 \(k\)로부터 \(a\)만큼 떨어진 장소에 정점을 만든 다음 기존의 \(k\)를 지운 후 새로 만들어진 정점을 \(k\)로 두겠습니다. 이렇게 얻은 그래프는 \( d^{(k, a)} \)를 실현한다는 것을 쉽게 알 수 있습니다. 그런데 이 그래프의 모든 간선의 가중치의 합은 \[ w^*(E^*) - a < w'(E') \]이 됩니다. 이는 \( (G', w') \)이 \(d^{(k, a)}\)를 최적으로 실현한다는 사실에 모순입니다.
그러므로 \( w^*(x, k) \leq a \)입니다. 이번에는 \( w^*(x, k) < a \)라면 어찌 될지 따져 보겠습니다. 임의의 주 정점 \(i \in V \setminus \{k\}\)에 대해, \[ d(i, k) = \frac{1}{2} ( d(i,k) + d(k, i) - d(i, i) ) \geq a^* \geq a > w^*(x, k) \]이므로 \(x\)는 보조 정점일 수밖에 없습니다. 앞에서 차수가 2 이하인 보조 정점은 존재하지 않는다고 하였으므로 \(x\)의 차수는 3 이상입니다. 임의의 \( i, j \in V \setminus \{k\} \)에 대해, \[ d(i, x) + d(x, j) - d(i, j) = d(i, k) + d(k, j) - d(i, j) - 2w(x, k) \geq 2a^* - 2w(x, k) > 0\]이 만족합니다. \((G^*, w^*)\)에서 \(k\)를 제거한 다음 \(x\)를 잠시 \(k\)로 치환한 그래프를 생각해 보겠습니다. 위 식에 의해 그 그래프는 그것이 실현하는 거리(즉, \(d^{(k, w^*(x,k))}\))를 최적으로 실현하지 않습니다. 따라서 그 거리를 최적으로 실현하는 그래프에 \(k\)를 다시 붙이는 자명한 방식으로 우리는 \((G^*, w^*)\)가 \(d\)를 실현하는 최적의 그래프라는 사실에 모순을 일으킬 수 있습니다. ■
트리 실현 가능성
이전 절에서 우리는 그래프 실현 가능한 거리의 최적의 실현 그래프가 갖는 몇 가지 흥미로운 성질들에 대해서 알아 보았습니다. 그렇다면 이제 자연스럽게 드는 의문은 어떻게 하면 최적의 실현 그래프를 찾을 수 있는가입니다. 안타깝게도 임의의 거리가 입력으로 주어졌을 때 최적의 실현 그래프를 찾는 문제는 NP-난해하다는 사실이 알려져 있습니다.
하지만 어떤 거리 함수가 어떤 트리로 실현 가능하다면 어떻게 될까요? 사실 이번 포스트를 작성하게된 계기는 어떤 거리 함수가 트리로 실현 가능한지, 만약 가능하다면 그 트리를 찾는 방법은 무엇인지가 궁금했기 때문입니다. 놀랍게도 우리는 다항 시간에 입력 거리의 트리 실현 가능 여부와 가능하다면 해당 트리를 찾는 것까지 할 수 있습니다.
그렇다면 그렇게 찾은 트리는 과연 입력 거리를 최적으로 실현하는 그래프가 될까요? 흥미롭게도 트리로 실현 가능한 거리의 최적의 실현 그래프는 반드시 트리 모양이어야 하며 그런 거리를 실현하는 트리는 유일합니다. 그러므로 앞에서 찾은 트리는 추가적인 작업 없이 바로 최적의 실현 그래프가 됩니다. 이제부터 이 내용들을 하나씩 짚어 보도록 하겠습니다.
첫 번째로 알아 볼 내용은 어떤 거리가 트리로 실현 가능하다면 그 트리는 유일하다는 것입니다.
정리 9. 거리를 실현하는 트리의 유일성
양수로만 이루어진 어떤 거리가 트리로 실현 가능하면, 그 트리는 유일하다.
[증명] 지점의 개수에 귀납적으로 증명해 보겠습니다. 기저 경우(base case)는 지점 개수가 두 개일 때입니다. 이때는 자명하게 해당 두 지점을 잇고 그 거리를 가중치로 두는 트리가 입력 거리를 실현하는 유일한 트리가 됩니다. 이제 귀납 가정(induction hypothesis)으로 지점 개수가 \(n - 1\)일 때의 모든 거리가 정리의 명제가 성립한다고 하겠습니다.
\(|V| = n\)에 대해 어떤 거리 \(d : \binom{V}{2} \to \mathbb{R}_+\)가 어떤 두 트리 \((T=(W, E), w)\), \((T' = (W', E'), w')\)로부터 실현 가능하다고 하겠습니다. 증명하고 싶은 것은 두 트리가 같을 수밖에 없다는 것입니다. 이제 임의의 한 지점 \(k \in V\)을 정해 \( (T, w) \)와 \( (T', w') \)에서 주 정점 \(k\)를 다음과 같이 제거해 보겠습니다. \((T, w)\)에서만 제거하는 방법을 소개하겠습니다. \((T', w')\)에서도 같은 방법을 적용하면 됩니다. 만약 \(k\)가 \((T, w)\)에서 차수가 1이라면 그냥 \(k\)를 떼어 냅니다. 만약 차수가 2라면 \(k\)를 빼면서 인접한 두 정점을 바로 이어 줍니다. 새로운 간선의 가중치는 원래 \(k\)에 딸린(incident) 두 간선의 가중치의 합으로 합니다. 마지막으로 차수가 3 이상이면 \(k\)를 새로운 보조 정점으로 치환합니다.
\((T, w)\)와 \((T', w')\) 각각에 위 작업을 적용하여 얻은 두 트리가 모두 \(V \setminus \{i\}\)의 지점 쌍의 \(d\)와 같은 거리를 실현한다는 것은 그리 어렵지 않게 보일 수 있습니다. 귀납 가정에 의해 두 트리는 동일하다는 것을 이끌어 낼 수 있습니다. 그 트리를 \((\bar{T}, \bar{w})\)라고 부르겠습니다. 이제 \((\bar{T}, \bar{w})\)에다가 위 작업을 역산하여 \((T, w)\)와 \((T', w')\)을 복원하겠습니다. \((T, w)\)에서 \(k\)가 \((\bar{T}, \bar{w})\)와 연결된 정점을 \(x\), \((T', w')\)에서는 \(x'\)이라고 부르겠습니다. (참고로, \(k = x\)이거나 \(k = x'\)일 수 있습니다.) \((\bar{T}, \bar{w})\)에 \(x\)나 \(x'\)이 없다면 굳이 생성하도록 하겠습니다.
(\(x\)나 \(x'\)을 제외한) 차수가 3 이하인 보조 정점은 존재하지 않으므로 \((\bar{T}, \bar{w})\)의 모든 리프(leaf)는 주 정점이어야 합니다. 따라서 분명 \((\bar{T}, \bar{w})\)에는 \[ d_{\bar{T}, \bar{w}}(i, x') = d_{\bar{T}, \bar{w}}(i, x) + d_{\bar{T}, \bar{w}} (x, x') \]를 만족하는 주 정점 \(i \in V \setminus\{k\} \)와 \[ d_{\bar{T}, \bar{w}} (i', x) = d_{\bar{T}, \bar{w}}(i', x') + d_{\bar{T}, \bar{w}}(x', x) \]을 만족하는 주 정점 \(i' \in V \setminus\{k\} \)가 존재합니다. (직관적으로 설명하면 \(i\)는 \(x\)의 바깥쪽, \(i'\)은 \(x'\)의 바깥쪽에 위치합니다.)
먼저 \(i\)에 대해서 고려해 보겠습니다. \( (T, w) \) 위에서 \(i\)에서 \(k\)까지 가는 경로는 \(i\)에서 \(x\)를 경유해서 \(k\)로 향하는 것이 유일하므로 \[ d_{T, w} (i, k) = d_{T, w} (i, x) + w(x, k) = d_{\bar{T}, \bar{w}} (i, x) + w(x, k) \]를 만족합니다. 반면 \( (T', w') \) 위에서 \(i\)와 \(k\)를 잇는 경로는 \(i\)에서 \(x\)와 \(x'\)을 지나 \(k\)로 향하는 것입니다. 따라서, \[ d_{T', w'} (i, k) = d_{T', w'} (i, x) + d_{T', w'} (x, x') + w'(x', k) = d_{\bar{T}, \bar{w}} (i, x) + d_{\bar{T}, \bar{w}} (x, x') + w(x', k)\]이 성립합니다. 두 식을 조합하면 \[ w(x, k) = d_{\bar{T}, \bar{w}} (x, x') + w'(x', k) \]을 얻을 수 있습니다.
위 논의를 \(i'\)에도 비슷하게 적용하면 \[ w'(x', k) = d_{\bar{T}, \bar{w}} (x', x) + w(x, k)\]라는 사실을 유도할 수 있습니다. 이 결과들을 조합하면 이번에는 \[d_{\bar{T}, \bar{w}} (x, x') = 0, \quad w(x, k) = w'(x', k)\]를 이끌어 낼 수 있습니다. 다시 말해, \((T, w)\)나 \((T', w')\)이나 \(k\)에서 \((\bar{T}, \bar{w})\)에 연결된 정점인 \(x\)와 \(x'\)은 사실 동일하고, \(x = x'\)과 \(k\)를 잇는 간선의 가중치 역시 동일합니다. 그러므로 \((T, w)\)와 \((T', w')\)도 같습니다. ■
이제 트리로 실현 가능한 거리는 그 트리가 곧 최적의 실현 그래프임을 보이겠습니다.
정리 10. 트리의 최적성
양수로만 이루어진 어떤 거리가 트리로 실현이 가능하면, 최적의 실현 그래프는 트리이다.
[증명] 전체적인 증명은 정리 9와 유사하게 귀납적으로 할 것입니다. 지점이 두 개로 이루어진 거리의 실현 그래프는 간선 하나이므로 기저 경우는 자명합니다. 귀납 가정으로 지점의 개수가 \(n - 1\)인 거리에 대해서는 정리의 명제가 성립한다고 하겠습니다. 이제 트리 \((T=(W, E), w)\)로 실현 가능한 거리 \(d : \binom{V}{2} \to \mathbb{R}_+\)와 임의의 지점 \(k \in V\)를 잡겠습니다. 그리고 정리 9의 증명에서 나온 작업을 \(k\)에 대해 \((T, w)\)에다 취한 결과를 \( (\bar{T}, \bar{w}) \)라고 하겠습니다. 그러면 귀납 가정에 의해 \( (\bar{T}, \bar{w}) \)는 \( V \setminus \{k\} \) 사이의 \(d\)와 같은 값을 갖는 거리의 최적의 실현 그래프가 됩니다.
정리 9에서와 논의한 것과 똑같이 \((T, w)\) 위에서 \(k\)에서 \((\bar{T}, \bar{w})\)로 연결된 정점을 \(x\)라고 하겠습니다. (앞에서 말한대로 \(k = x\)일 수 있습니다.) \(x\)는 분명 \((\bar{T}, \bar{w})\) 위에서 어느 두 주 정점 \(i', j' \in V \setminus \{k\} \)를 잇는 (유일한) 최단 경로 위에 있을 것이므로 \[ d(i', j') = d_{\bar{T}, \bar{w}}(i', x) + d_{\bar{T}, \bar{w}} (x, j') \]라는 사실을 얻을 수 있습니다. 따라서 \( (T, w) \)에서 \(a^*\)는 \[ a^* = \min_{i, j \in V \setminus \{k\}} \frac{1}{2} (d(i, k) + d(k, j) - d(i, j)) = \min_{i, j \in V \setminus \{k\} } \frac{1}{2}(d_{\bar{T}, \bar{w}}(i, x) + d_{\bar{T}, \bar{w}}(x, j) - d(i,j)) + w(x, k) = w(x, k) \]를 만족함을 알 수 있습니다.
게다가 \( (\bar{T}, \bar{w}) \)에다가 \(x\)를 굳이 넣고 이를 \(k\)로 치환한 트리는 \( d^{(k, a^*)} \)를 실현하는 트리라는 것도 어렵지 않게 알 수 있습니다. 역으로 말하면 \( (T, w) \)가 (작업이 가해진) \((\bar{T}, \bar{w})\)로부터 정리 8의 작업을 통해 얻은 결과라는 뜻입니다. \( (\bar{T}, \bar{w}) \)는 \(d^{(k, a^*)}\)를 최적으로 실현하는 트리이므로 \( (T, w) \)도 \(d\)를 최적으로 실현하는 트리가 됩니다. ■
정리 9와 10을 통해 알 수 있는 사실은 만약 거리가 어떤 트리로 실현 가능하면, 그 트리는 유일한 최적의 실현 그래프가 된다는 것입니다. 이제 다항 시간에 그 트리가 존재하면 찾는 알고리즘을 소개하겠습니다. 사실 앞에서 논의한 내용을 거의 그대로 확장한 것에 불과하기는 합니다.
알고리즘 1. 거리를 실현하는 트리 찾기
입력: 양수로만 이루어진 거리 \(d : \binom{V}{2} \to \mathbb{R}_+\)
출력: \(d\)를 실현하는 트리 \((T, w)\) 혹은 트리로 실현 불가능함
- \(|V| \leq 2\)인 경우에는 자명한 트리를 반환한다.
- 임의의 지점 \(k \in V\)를 정한다.
- \(V \setminus \{k\}\) 사이의 \(d\)에 대해서만 재귀적으로 실현 트리 \((\bar{T}, \bar{w})\)를 찾는다. 만약 존재하지 않으면 실현 불가능하다고 반환한다.
- \(a^* \gets \min_{i, j \in V \setminus \{k\}} \frac{1}{2} (d(i, k) + d(k, j) - d(i, j))\)
- \(d^{(k, a^*)}\)에서 \( d^{(k, a^*)}(i^*, k) + d^{(k, a^*)}(k, j^*) = d^{(k, a^*)}(i^*, j^*) \)를 만족하는 지점 \(i^*, j^* \in V \setminus \{k\}\)를 찾는다.
- \((\bar{T}, \bar{w})\) 위에서 \(i^*\)에서 출발해 \(j^*\)로 향하는 유일한 경로를 따라 \( d^{(k, a^*)}(i^*, k) \)만큼 이동한다. 만약 거기에 어떤 정점이 있으면 그 정점을 \(x\)로 한다. 만약 거기에 정점이 없으면 새로운 보조 정점 \(x\)를 만들고 가중치를 거리가 위배되지 않게 분배한다.
- \( ( \bar{T}, \bar{w} ) \)에 가중치가 \(a^*\)인 간선 \( (x, k) \)를 추가한다. 이렇게 얻어진 트리를 \((T, w)\)라고 부른다.
- 임의의 \(i \in V\)에 대해 \(d(k, i) = d_{T, w}(k, i)\)인지 확인한다.
- 만약 모두 맞으면 \((T, w)\)를 반환한다. 그렇지 않으면 실현 불가능하다고 반환한다.
이 알고리즘이 정확히 동작한다는 것은 앞에서 정리한 내용들을 통해서 충분히 유추할 수 있다고 판단하여 중언부언하지 않겠습니다. 대신 이 알고리즘의 수행 시간에 대해 분석해 보도록 하겠습니다. 이 알고리즘은 문제를 재귀적으로 해결합니다. 재귀 호출은 \(|V| - 1\) 번 수행됩니다. 단계 6에서 \(x\)를 찾거나 만드는 것과 단계 8은 트리에서 BFS 혹은 DFS를 수행하는 것으로 충분히 해결할 수 있습니다. 그외의 단계는 모두 \(O(|V|^2)\)에 수행이 가능합니다. 따라서 알고리즘의 전체 수행 시간은 \(O(|V|^3)\)입니다. 입력은 \(|V|\)의 모든 쌍에 대한 거리이므로 그 크기가 \(m := |V|^2 / 2\)임을 감안한다면 이 알고리즘의 입력에 대한 수행 시간은 \( O(m \sqrt{m}) \)이 되겠습니다.
마치며
이것으로 거리의 그래프 실현 가능성에 대한 소개를 마칩니다. 특히 거리가 트리로 실현 가능하다면 유일한 최적의 실현 그래프인 그 트리를 다항 시간에 찾을 수 있다는 사실을 확인하였습니다. 사실 처음에 이 주제에 대해 공부를 할 때나 글을 막상 적을 때는 이 포스트가 이렇게까지 길어질 줄은 몰랐습니다. 하지만 공부하다 보니 재미있어서 이 내용 저 내용 할 것 없이 다 옮기다 보니 글의 양이 상당해졌군요. 오랜만에 포스팅을 한 것도 재미있었고요.
다른 논문들을 좀더 훑어 보니 몇 가지 흥미로운 결과들이 있더군요. 본문에서 소개한 거리를 실현하는 트리를 찾는 알고리즘은 \(O(|V|^3) = O(m \sqrt{m})\)의 수행 시간을 가졌습니다. 그런데 놀랍게도 \(O(|V|^2) = O(m)\) 시간에 동작하는 알고리즘이 있다고 하네요. 이는 입력에 대해서 선형 시간에 동작하는 알고리즘입니다. 이 문제를 해결하려면 모든 거리를 최소한 한 번은 훑어야 하므로 그 알고리즘은 최적의 수행 시간을 갖습니다. 혼자서 어떻게 하면 가능할지 생각해 보고 있기는 합니다만, 나중에 궁금하면 그냥 논문을 읽어 봐야겠습니다.
또, 임의의 거리를 최적으로 실현하는 그래프를 찾는 문제는 근사해를 구하는 것도 쉽지 않다는 결과도 있었습니다. 대신 조건을 좀 완화하면 근사비를 상수로 낮출 수 있다고 주장하는 논문도 얼핏 봤습니다. 일단 궁금해서 출력해 놨습니다. 가볍게 읽어 보고 혹여나 공유할 만하면 포스팅해 보도록 하겠습니다.
읽어 주셔서 고맙습니다.
참조
[1] S. Louis Hakimi and Stephen S. Yau. "Distance matrix of a graph and its realizability." Quarterly of applied mathematics 22, no. 4 (1965): 305-317.
'수학적 도구 > Graph theory' 카테고리의 다른 글
| 하벨-하키미 알고리즘 (Havel-Hakimi Algorithm) (0) | 2022.06.17 |
|---|---|
| 그래프 트리에 관한 간단한 성질들 (0) | 2020.03.25 |
