無向グラフの全点対間最大流
#グラフ #フロー
カット木
あらゆる無向グラフには、どの2点間の最大流も元のグラフと等しくなるような全域木（カット木）が存在する
カット木上では、最大流はパス上の$ \minを求めることで求められる
Gomory-Huのアルゴリズム
最小カットの性質を使って、$ V-1回最大流を計算することでカット木を求める
実装
アルゴリズム
1. すべての頂点を縮約し、$ C = \{1, 2, \ldots, V\}とする
2. $ Cに含まれる頂点の中から任意の$ 2頂点$ s, tを選び、元のグラフでの$ s-t最小カットを求める
3. 頂点$ s, tの間にカット容量の辺を貼る
4. $ s, tが含まれるカット$ S, Tを新しく縮約された頂点とする
5. 1に戻り、$ C = S, $ C = Tに対して再帰的に行う
計算量
最大流の計算量を$ O(f)とすると、$ O(Vf)
Dinicなら$ O(V^3 E)
Dinic+容量スケーリングなら$ O(V^2 E \log U)
Highest Label Selection Preflow-Pushなら$ O(V^3 \sqrt E)
実行例
このグラフのカット木を求める
https://scrapbox.io/files/69a2f947f1c53c17321b8004.png
左図は元のグラフ、右図はGomory-Hu木
すべての頂点を1つのグループに入れる
https://scrapbox.io/files/69a2f94af1c53c17321b8007.png
グループ$ \{a, b, c, d\}から適当な$ 2頂点を選び元のグラフ上の最小カットを求める
https://scrapbox.io/files/69a2f94cf1c53c17321b8008.png
選んだ$ 2頂点にカット容量の辺を貼り、最小カットによってグループを分割する
https://scrapbox.io/files/69a2f94ef1c53c17321b800b.png
グループ$ \{a, d\}から$ 2頂点を選び元のグラフ上の最小カットを求める
https://scrapbox.io/files/69a2f950f1c53c17321b800c.png
選んだ$ 2頂点にカット容量の辺を貼り、最小カットによってグループを分割する
https://scrapbox.io/files/69a2f952f1c53c17321b800e.png
グループ$ \{b, d\}から$ 2頂点を選び元のグラフ上の最小カットを求める
https://scrapbox.io/files/69a2f954f1c53c17321b8010.png
選んだ$ 2頂点にカット容量の辺を貼り、最小カットによってグループを分割する
https://scrapbox.io/files/69a2f956f1c53c17321b8011.png
すべてのグループが大きさ$ 1になったので終了
Stoer-Wagnerのアルゴリズムでもカット木が求まる？
全域最小カットを求める→縮約してカットに容量分の辺を貼るを繰り返すとカット木が求まりそうな気がする
多分無理（2021-08-28追記）
全域最小カットはStoer-Wagnerのアルゴリズムで求まる
計算量 $ O(V^4) or $ O(V^2E + V^3\log V)
Stoer-Wagner
隣接行列 $ O(V^3)
フィボナッチヒープ $ O(VE + V^2 \log V)
繰り返し回数: 木を作るので$ V-1回