# Gomory-Hu Tree Gomory-Hu Tree는 무향 그래프의 모든 정점 쌍 minimum cut 값을 `N-1`번의 min-cut 계산으로 압축하는 구조입니다. 완성된 tree에서는 두 정점 사이 경로의 최소 edge weight가 원래 그래프에서의 두 정점 min cut 값이 됩니다. ## 문제 신호 | 문제 표현 | Gomory-Hu Tree 관점 | | --- | --- | | 무향 그래프에서 모든 쌍 min cut | cut-equivalent tree | | 많은 `s-t` cut 질의 | tree path minimum | | edge connectivity를 여러 쌍에 대해 묻는다 | min cut value table 압축 | | 정점 수는 작고 max-flow는 가능 | `N-1` max-flow | | 방향 그래프이다 | Gomory-Hu Tree 기본형은 맞지 않음 | Gomory-Hu Tree는 무향 그래프용입니다. 방향 그래프의 모든 쌍 min cut은 같은 방식으로 tree 하나에 압축되지 않습니다. ## Tree가 담는 의미 Gomory-Hu Tree `T`는 원래 그래프와 같은 정점 집합을 갖고 edge가 `N-1`개입니다. 임의의 두 정점 `u`, `v`에 대해: ```text minCut_G(u, v) = minimum edge weight on path_T(u, v) ``` 즉 모든 쌍에 대해 max-flow를 다시 돌리지 않고 tree에서 LCA/RMQ 또는 단순 path traversal로 답할 수 있습니다. ## Construction 개요 처음에는 모든 정점의 parent를 0으로 둡니다. 정점 `s`를 1부터 `N-1`까지 보면서 `s`와 `parent[s]` 사이 min cut을 계산합니다. ```text for s in 1..N-1: t = parent[s] (cutValue, side) = minCut(s, t) parent가 t이고 side에 속한 정점들을 s 아래로 옮긴다 필요하면 s와 t의 parent 관계를 회전한다 weight[s] = cutValue ``` `side`는 residual graph에서 `s`로부터 도달 가능한 정점 집합입니다. 이 정보가 있어야 cut tree를 갱신할 수 있습니다. ## 4정점에서 parent 갱신 따라가기 ### 예시 그래프 정점은 `0, 1, 2, 3`이고, 무향 edge capacity는 아래와 같습니다. | edge | capacity | | --- | ---: | | `0-1` | 3 | | `0-2` | 2 | | `1-2` | 4 | | `1-3` | 2 | | `2-3` | 5 | 초기 cut tree parent는 모두 0입니다. ```text parent[1] = 0 parent[2] = 0 parent[3] = 0 ``` 아래 trace에서는 min-cut oracle이 `s` 쪽 source side를 `reachable side`로 반환한다고 가정합니다. ### 1단계: `s=1`, `t=parent[1]=0` `1-0` min cut을 구합니다. 이 그래프에서는 `{1,2,3}`과 `{0}`을 가르는 cut이 capacity `3 + 2 = 5`로 최소입니다. ```text cut value = 5 reachable side = {1,2,3} ``` 현재 `parent[v] == 0`인 정점 중 reachable side에 있는 `2`, `3`은 `1`과 같은 쪽에 있으므로 `1` 아래로 옮깁니다. ```text parent[1] = 0, weight[1] = 5 parent[2] = 1 parent[3] = 1 ``` tree 모양은 아직 임시입니다. ```text 0 --5-- 1 |\ 2 3 ``` 여기서 `2`, `3`의 edge weight는 아직 확정되지 않았습니다. ### 2단계: `s=2`, `t=parent[2]=1` `2-1` min cut을 구합니다. `{2,3}`과 `{0,1}`을 가르면 crossing edge는 `0-2`, `1-2`, `1-3`이고 총 capacity는 `2 + 4 + 2 = 8`입니다. ```text cut value = 8 reachable side = {2,3} ``` 현재 `parent[v] == 1`인 정점 중 `s=2`보다 뒤에 있고 reachable side에 있는 정점은 `3`입니다. 따라서 `3`을 `2` 아래로 옮깁니다. ```text parent[1] = 0, weight[1] = 5 parent[2] = 1, weight[2] = 8 parent[3] = 2 ``` 임시 tree는 아래처럼 더 세분화됩니다. ```text 0 --5-- 1 --8-- 2 | 3 ``` ### 3단계: `s=3`, `t=parent[3]=2` `3-2` min cut을 구합니다. `{3}`과 `{0,1,2}`를 가르면 crossing edge는 `1-3`, `2-3`이고 총 capacity는 `2 + 5 = 7`입니다. ```text cut value = 7 reachable side = {3} ``` 더 옮길 자식이 없으므로 `3`의 parent edge weight만 확정합니다. ```text parent[1] = 0, weight[1] = 5 parent[2] = 1, weight[2] = 8 parent[3] = 2, weight[3] = 7 ``` 완성된 Gomory-Hu Tree는 아래와 같습니다. ```text 0 --5-- 1 --8-- 2 --7-- 3 ``` ### Query를 답하는 방법 완성된 tree에서 `2`와 `3` 사이 경로는 edge 하나입니다. ```text 2 --7-- 3 ``` 따라서 원래 그래프의 `minCut(2, 3)` 값은 path minimum인 `7`입니다. `0`과 `3`을 묻는다면 tree path는 `0-1-2-3`이고 edge weight는 `5, 8, 7`입니다. 이때 답은 합 `20`이 아니라 최솟값 `5`입니다. ```text minCut_G(0, 3) = min(5, 8, 7) = 5 ``` ## 구현 골격 아래 코드는 max-flow 구현을 주입받아 Gomory-Hu parent tree를 만드는 골격입니다. `minCut(s, t)`는 min cut 값과 residual reachable side를 반환해야 합니다. n>=1, 비음수 무향 용량, oracle의 길이 n인 source-side 배열을 전제로 합니다. side[s]=true, side[t]=false이며 매 호출은 원본 용량에서 시작합니다. 질의 u,v는 서로 달라야 합니다. 병렬 간선은 합산하거나 별개의 용량 간선으로 보존할 수 있습니다. > **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다. ```cpp compile-check #include #include #include #include using namespace std; struct MinCutResult { long long value = 0; vector reachableFromSource; }; struct GomoryHuTree { int n; vector parent; vector weightToParent; function minCut; GomoryHuTree(int vertexCount, function oracle) : n(vertexCount), parent(vertexCount, 0), weightToParent(vertexCount, 0), minCut(oracle) {} vector> build() { parent.assign(n,0); weightToParent.assign(n,0); for (int s = 1; s < n; ++s) { int t = parent[s]; MinCutResult result = minCut(s, t); const vector& side = result.reachableFromSource; for (int v = s + 1; v < n; ++v) { if (parent[v] == t && side[v]) { parent[v] = s; } } if (side[parent[t]]) { parent[s] = parent[t]; parent[t] = s; weightToParent[s] = weightToParent[t]; weightToParent[t] = result.value; } else { weightToParent[s] = result.value; } } vector> edges; for (int v = 1; v < n; ++v) { edges.push_back({v, parent[v], weightToParent[v]}); } return edges; } }; ``` 실전에서는 매 min-cut마다 원본 capacity graph를 복사하거나 capacity를 초기화해야 합니다. 이전 flow의 residual graph를 그대로 쓰면 다음 cut이 깨집니다. ## 질의 처리 완성된 Gomory-Hu Tree에서 `u-v` 경로의 edge weight 최솟값이 답입니다. ```text answer(u, v): path = tree path from u to v return min(edge.weight for edge in path) ``` 질의가 많으면 tree에 LCA binary lifting을 올리고, 각 jump마다 최소 edge weight를 함께 저장합니다. 정점 수가 작으면 DFS로 경로를 찾아도 됩니다. ## 왜 `N-1`번이면 충분한가 각 단계에서 구한 cut은 현재 tree의 한 edge에 해당하는 분할을 확정합니다. reachable side에 따라 parent를 재배치하면 이전에 확정된 cut과 충돌하지 않는 형태로 cut-equivalent tree가 유지됩니다. 직관적으로는 현재 parent tree가 "아직 구분이 덜 된 정점 묶음"을 들고 있고, `s-parent[s]` min cut은 그 묶음 안에서 `s` 쪽과 `parent[s]` 쪽을 가르는 새 경계 하나를 확정합니다. `side`에 같이 들어온 형제들은 `s`와 같은 쪽에 있었으므로 `s` 아래로 이동합니다. 이렇게 옮겨도 이전 단계에서 확정한 cut은 uncrossing 성질 때문에 더 나빠지지 않습니다. 증명은 submodularity와 cut uncrossing에 기대지만, 구현 관점에서는 아래 세 조건을 기억하면 충분합니다. 1. 매번 `s`와 `parent[s]`의 실제 minimum cut을 구한다. 2. reachable side에 속한 같은 parent 자식들을 `s` 아래로 옮긴다. 3. 완성된 tree 질의는 path sum이 아니라 path minimum으로 답한다. ## 시간 복잡도 | 항목 | 복잡도 | | --- | ---: | | Gomory-Hu construction | `N-1`번 max-flow | | tree edge 수 | `N-1` | | 단순 질의 | `O(N)` | | LCA 전처리 후 질의 | `O(log N)` | 전체 병목은 max-flow입니다. `N`이 크고 edge도 많은 경우에는 global min cut만 필요한지, 모든 쌍 질의가 정말 필요한지 먼저 확인합니다.