フロー

蟻本p.188~

まだ完成していないので読まないほうが良い

もくじ

フローネットワークについて

有向グラフの辺に容量がある

最大フロー(最大流)とは

残余ネットワーク

両側に辺→相殺できる、という話

何が嬉しい？

残余ネットワーク、逆の辺も作られうるってどういう意味、有向辺は？

最大フローを求めたい

Ford-Fulkersonのアルゴリズム

実装分からん

Dinic法

最大フロー最小カット定理

フローネットワークとは？

有向グラフの辺に容量が設定されていて、容量を超える流量を設定することはできない。

頂点s,t以外の全ての頂点について、「入ってくる流量の合計 = 出ていく流量の合計」が成り立つ

例えば

https://gyazo.com/1b15de1984fff480bc3c2428a964f518

こんなのがあったとして、

https://gyazo.com/3a2b2243b5257a89a93d8b70e7fb0bee

こんな風に流せたりする。A,B,Cの頂点について「入る量 = 出る量」になっているのを確認しておく。

ちなみにこれは最大フローではない（それはそう）

最大フロー

https://gyazo.com/2365e78df9e792ad009cecddedc497b2

こんな感じの、一番sからtに流れる合計が多い設定のこと。知らんけど。

https://gyazo.com/a86f367f86bdf8c4b89030101a9ac931

これWikiのやつだけど、相互に有向辺を繋ぐのはOK, たぶん逆向きに関しては逆向きの容量を超えなければOK

だから「辺なし」は容量が0になってるっぽい

逆向きの辺が無いときに0に設定しておくと、逆向きに1以上流れることがなくなる→逆向きに流れない

残余ネットワークの考え方

相殺する辺の話

頂点Aから頂点Bに、頂点Bから頂点Aにそれぞれ流れるタイプの有向辺が出ていて、

A→Bの流量は10、B→Aの流量が3だったとする

よく考えると、これA→Bに流量7って考えても同じでは？という考えに至る

こんな風に、逆向きの辺の流量を増やすことで

残余ネットワークは「この方向にあとこれだけ動かせるよ」みたいなイメージ

https://gyazo.com/02e4d8871c568552984c1c55f8ced4c2

例えば容量10の辺に7流れているとき、ふやす方向には残り3、へらす方向には残り7動かすことができる。

互いに有向辺を生やす

フローを増やす（EASY）

https://gyazo.com/c9cb83e4d25c4446f261d3a58e742baf

このフローは最大フローではない…このフローについて残余ネットワークをとると

https://gyazo.com/41f14ac4caac163b2c817d832fdf552c

こうなる。見にくいのでもうちょっとマシな表し方にする。

https://gyazo.com/631e1c684ef00e965076c59ea2c248c4

がーっとやる

メモ

増加道を探して流すってやつ、逆流も入ってるから「流入の合計＝流出の合計」が成り立たないのでは？みたいな

増加道で使った矢印の、矢印の向きに気をつけて考察すると理解しやすい

最大フローを求めたい