# 最大流最小カット定理・Ford-Fulkerson法 (チラ裏)

(wip)

- アルゴリズムイントロダクション(赤)p308
- 蟻本 191p
- https://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E3%83%95%E3%83%AD%E3%83%BC%E6%9C%80%E5%B0%8F%E3%82%AB%E3%83%83%E3%83%88%E5%AE%9A%E7%90%86

主張: **ネットワークにおける最大流と最小カットは一致する**

#### ネットワークってなんですか

フローネットワーク$G = (V, E, s, t)$

- 有向グラフ$(V, E)$について、各辺$(u, v)\in E$が非負の容量$c(u, v)$を持つ
- $(u, v)\in E\to (v, e)\notin E$ を満たす
- 自己ループを持たない(容量は0)
- $s\in V, t\in V$

#### フローってなんですか

ネットワーク$G = (V, E, s, t)$に対するフロー$f$とは
1. 実数値関数$f: V\times V\to \mathbb{R}$である
2. 容量制限を満たす$\forall_{(u, v)\in E}\ 0\le f(u, v)\le c(u, v)$
4. フロー保存則を満たす$\forall_{u\in V-\{s, t\}}\ \sum_{v\in V}f(v, u) = \sum_{v\in V} f(u, v)$
- 始点と終点以外の頂点について、入ってくる水の量とでていく水の量は一緒！

フローの値$|f|$を$\sum_{v\in V} f(s, v) - \sum_{v\in V}f(v, s)$とする
- 入口から入って入口に帰ってこなかった水の量
- 入口に帰ってきてしまった水以外は、出口から抜けている？

最大フローはこのフローの値が最大であるフローを発見せよという問題

#### カットってなんですか

ネットワーク$(V, E, s, t)$のカット$(S, T)$とは、$V$を$S$と$T$の2つの頂点集合に分割すること
- $s\in S$
- $t\in T$
- 任意の頂点は、必ずどちらか一方に属する必要がある

カットの容量を$c(S, T) = \sum_{u\in S}\sum_{v\in T} c(u, v)$と定義する

最小カット問題は、このカットの容量が最小であるカットを発見せよという問題

## 最大流最小カット定理証明

ネットワーク$G = (V, E, s, t)$についてフロー$f$とカット$(S, T)$と交差する純フロー

$f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u, v) - \sum_{u\in S}\sum_{v\in T} f(v, u)$
- $T$から$S$に戻ってくる水を差し引いている

**補題: フロー$f$とカット$(S, T)$について$f(S, T) = |f|$が成り立つ**

証明

式$\sum_{v\in V}f(s, v) - \sum_{v\in V}f(v, s) + \sum_{u\in S - \{s\}} (\sum_{v\in V} f(u, v) - \sum_{v\in V}f(v, u))$について考える。

前2項はフローの定義そのものであり、フロー保存則より後ろの項は$0$である。つまりこれは$|f|$と一致する
- $t\notin S$であることに注意

$|f| = \sum_{v\in V}f(s, v) - \sum_{v\in V}f(v, s) + \sum_{u\in S - \{s\}} (\sum_{v\in V} f(u, v) - \sum_{v\in V}f(v, u))$

$|f| = \sum_{v\in V}f(s, v) - \sum_{v\in V}f(v, s) + \sum_{u\in S - \{s\}} \sum_{v\in V} f(u, v) - \sum_{u\in - \{s\}}\sum_{v\in V}f(v, u)$

$|f| = \sum_{v\in V}(f(s, v) + \sum_{u\in S - \{s\}}f(u, v))- \sum_{v\in V}(f(v, s) - \sum_{u\in - \{s\}}f(v, u))$

$|f| = \sum_{v\in V}\sum_{u\in S}f(u, v) - \sum_{v\in V}\sum_{u\in S}f(v, u)$

- ここまで全部機械的な式変形

$S\cap T = \phi$より

$|f| = \sum_{v\in S}\sum_{u\in S}f(u, v) + \sum_{v\in T}\sum_{u\in S}f(u, v) - \sum_{v\in S}\sum_{u\in S}f(v, u) - \sum_{v\in T}\sum_{u\in S}f(v, u)$

$\sum_{T}\sum_{S}$のやつを前側にもってくる

$|f| = \sum_{v\in T} \sum_{u\in S} f(u, v) - \sum_{v \in T}\sum_{u\in S} f(v, u) + \sum_{v\in S} \sum_{u\in S} f(u, v) - \sum_{v \in S}\sum_{u\in S} f(v, u)$

$\sum_{u\in S}\sum_{v\in S} f(u, v) = \sum_{u\in S}\sum_{v\in S}f(v, u)$なので(それはそう)、後ろ二項が$0$

$|f| = \sum_{v\in T} \sum_{u\in S} f(u, v) - \sum_{v \in T}\sum_{u\in S} f(v, u)$ 右辺が純フローの定義と一致している (終了)

**系[^1]: 任意のフロー$f$は同一ネットワーク上の任意のカット容量で抑えられる**

純フローの式とカット容量の式を見比べると一目瞭然

**この事から、フロー$|f|$が最小カット容量$c(S, T)$と一致するなら$f$は最大フローであることがわかる**

次にフロー$f$が最大フローならば$|f| = c(S, T)$であることを証明しなければならない
- もしかしたら最大フローの値が最小カット容量より小さいかもしれない。これがありえないことを示さなければいけない

#### 残余ネットワークと増加路

フローアルゴリズムでは残余ネットワークが良く出現するのは流石に知ってる。
- 押し戻しの辺があるやつ

増加路(augument path)は残余ネットワーク上の$s-t$パス$p$を指す。この$p$の残余容量(residual capacity)を$\min c_f(p)$で定義する
- 当然残余容量は正
- 英語問題の解説で見かける単語だ。
- 増加路を発見したら、そこにめいいっぱい(残余容量分)流すやつがFord-Fulkersonだよね(だよね？)

[^1]: ある定理から容易に導けるものを系と呼ぶそうです。

この用語を使って、証明の続きが。

最大フロー$f$から誘導される残余ネットワーク上では増加路は存在しない(存在したらそこに水を流して真に$f$より大きい値のフローを得られるため$f$が最大フローであることと矛盾している)
- 本当は増加路$p$に水を流したらフローが水を流した分だけ増加することを証明しなければいけない(書くのがだるくなってしまった)

フロー$f$から誘導される残余ネットワークが増加路を持たない時、$|f| =$最小カット容量であることを示す。