割（Cut）
s-t cut：(A, B)，將圖分為兩部分A和B，源s∈A，終點(diǎn)t∈B
cut(A, B)的容量（capacity）：所有流出A的邊的容量和绞蹦，注意區(qū)分與流量（flow）的區(qū)別。
如下圖
割的大小
最小的s-t cut：具有最小的容量（capacity）榜旦。
??割實(shí)際就是幽七，徹底切斷s與t的通信，需去掉的邊的容量之和溅呢。用最小的勞動(dòng)力斬?cái)嗤ㄐ旁杪牛醋钚「睢?p>
流
對(duì)任意流，均滿足條件：
- ? e∈E咐旧，有f(e)≤c(e). 經(jīng)過任意邊的流量不大于該邊的容量驶鹉。（通過水管的水量不超過水管的負(fù)載能力）
- ? v∈V - {s, t}，
. 任意點(diǎn)流出的流量與流入這點(diǎn)的流量相等——流一致性铣墨。（每個(gè)水管節(jié)點(diǎn)不消耗也不憑空產(chǎn)生水）
流大小的定義
??對(duì)流f室埋，其大小為流出該點(diǎn)（部分）流量之和與流入的流量之差。
??????????????
流的大小
最大流問題
兩個(gè)重要結(jié)論：
- 對(duì)任意流f踏兜，任意割(A, B)词顾，流的大小為流出A的流量與流入A的流量之差。例如碱妆，自來水中轉(zhuǎn)站一共能向外供應(yīng)的水量。
?????????????? - 任意流的大小不大于割的大小昔驱。v(f)≤cap(A, B). 例如疹尾，從我家到你家的自來水管的流量為520，若你惹我生氣了骤肛，我想切斷從我家到你家的自來水供應(yīng)纳本。因此，我需要花費(fèi)不低于520的勞動(dòng)力（割）腋颠》背桑可見，流量能達(dá)到的最大值就是割的大小淑玫。
最大流與最小割
推論 若流大小與割大小相等巾腕，那么這一定是最大流面睛。（前面的重要結(jié)論可以幫助理解）
如何尋找最大流？很容易想到的是貪心算法尊搬。
貪心算法求解最大流
思路：從流量為0的邊開始叁鉴，選取s到t的路徑（需滿足流量不大于容量）并修改流量，不停添加增廣路徑佛寿，直到?jīng)]有為止幌墓，然后再?gòu)牧髁繛?的邊開始重復(fù)操作。
貪心算法得出最大流16
實(shí)際最大流為19
貪心算法一旦提升了流量冀泻，就不再減小常侣，沒有回溯不佳的路徑選擇。
Ford Fulkerson算法
增廣路徑：剩余圖中弹渔，s到t的簡(jiǎn)單路徑袭祟。
瓶頸容量：一條增廣路徑的流量貢獻(xiàn)，取決于這條路徑上所有邊的最小剩余容量.
??區(qū)別于貪心算法捞附，我們每次在剩余圖中尋找s-t的簡(jiǎn)單路徑巾乳。
??剩余圖的畫法
剩余圖
??舉例，下圖用貪心算法計(jì)算出最大流為20鸟召。
貪心算法得出的錯(cuò)誤結(jié)果
??使用Ford Folkerson算法胆绊，每次更迭畫出剩余圖，剩余圖的相反路徑可用于回溯欧募。
FF算法求出最大流為30
Q
??無向圖如何構(gòu)造剩余圖压状，如何求解最大流？
