最小割的一些性質

自己總結的……有錯誤的話請大牛指出~~畢竟自己對流和割的了解還不夠……

【性質1】最小割中的邊一定是滿流邊。

粗略證明：我們預設最大流最小割定理已經存在并被證明，那麼有F[S,T] = fmax = C[S,T]。假設有某條邊不是滿流，即Fe < Ce，則易知必然存在某條邊的Fe' > Ce' ，與網絡流的流量限制條件沖突。

【★性質2】若删掉或減小某條滿流邊的容量後最大流不減小，則該邊一定不是最小割中的邊。

粗略證明：根據最大流最小割定理可知fmax = C[S,T]。假設該邊是某最小割中的邊，那麼 當删掉該邊後，C[S, T]減小，而fmax不減小，則此時fmax > C[S, T]，與最大流最小割定理沖突。

【

性質3

】滿流邊不一定可以是最小割中的邊。

這裡給出了一種情況，即在殘留網絡中該滿流邊兩端點連通，則這個邊不能是最小割中的邊。證明：如果我們令該邊容量減少1，則兩端點間減少的1個流可以通過另一條連通路流出，最大流不改變。根據[性質2]，該邊一定不是最小割中的邊。

【★性質4】網絡流的任意一條增廣路至少經過一條最小割邊。

證明：如果沒有經過割邊，則完全可以令這條增廣路上的邊的流量都無窮大oo（或者很大），則最大流f = oo，但是最小割容量C[S,T]卻沒變，導緻f > C[S,T]，與最大流最小割定理沖突。

【★性質5】若增加某條滿流邊的容量後，整個流網絡的流量增加（不一定增加此值），那麼該邊一定是最小割上的邊，即關鍵割邊。

證明：假設該條邊不是最小割邊，那我們隻增加該邊容量，則最大流f增加，而最小割邊容量C[S,T]不變，導緻f > C[S, T]，與最大流最小割定理沖突。

【求關鍵割邊】對于某滿流邊，如果在殘留網絡中，源點能到達該邊一端點，另一端點能到達彙點，則該滿流邊就是關鍵割邊。因為一旦該邊流量增加，則殘留網絡中将增加一條增廣路，最大流便增加了。

容易發現其中大部分性質的證明都要根據最大流最小割定理，是以正确了解此定理是非常重要的︿(￣︶￣)︽

性質應用：BZOJ 1797 [AHOI 2009]Mincut 最小割，判斷某個滿流邊是否可能是最小割邊和一定是最小割邊。

舉杯獨醉，飲罷飛雪，茫然又一年歲。 ------AbandonZHANG