久久成人欧美亚洲天堂,亚州综合福利

割（Cut）

s-t cut：(A, B)，將圖分為兩部分A和B，源s∈A，終點(diǎn)t∈B
cut(A, B)的容量（capacity）：所有流出A的邊的容量和，注意區(qū)分與流量（flow）的區(qū)別。
$cap(A,B)=\sum_{e\,out\,of\,A}c(e)$ 如下圖

割的大小

最小的s-t cut：具有最小的容量（capacity）。
??割實(shí)際就是，徹底切斷s與t的通信，需去掉的邊的容量之和。用最小的勞動力斬斷通信，即最小割。

流

對任意流，均滿足條件：

? e∈E，有f(e)≤c(e). 經(jīng)過任意邊的流量不大于該邊的容量。（通過水管的水量不超過水管的負(fù)載能力）
? v∈V - {s, t}， $\sum_{e\,out\,of\,v}=\sum_{e\,in\,to\,v}$ . 任意點(diǎn)流出的流量與流入這點(diǎn)的流量相等——流一致性。（每個水管節(jié)點(diǎn)不消耗也不憑空產(chǎn)生水）

流大小的定義

??對流f，其大小為流出該點(diǎn)（部分）流量之和與流入的流量之差。
?????????????? $val(f)=\sum_{e\,out\,of\,s\,or\,A}-\sum_{e\,in\,to\,s\,or\,A}$

流的大小

最大流問題

兩個重要結(jié)論：

對任意流f，任意割(A, B)，流的大小為流出A的流量與流入A的流量之差。例如，自來水中轉(zhuǎn)站一共能向外供應(yīng)的水量。
?????????????? $\sum_{e\,out\,of\,A}-\sum_{e\,in\,to\,A}=val(f)$
任意流的大小不大于割的大小。v(f)≤cap(A, B). 例如，從我家到你家的自來水管的流量為520，若你惹我生氣了，我想切斷從我家到你家的自來水供應(yīng)。因此，我需要花費(fèi)不低于520的勞動力（割）?？梢姡髁磕苓_(dá)到的最大值就是割的大小。