如何在二分流網絡的殘差圖中有完美匹配的有向循環？

Question

我正在研究算法的分析。我目前正在閱讀Network Flow算法。我正在考慮應用Network Flow算法有關尋找最低成本bipartite matchings。

• 讓G與相應的網絡流量G'
• 讓M是在G
• perfect matching讓G<sub>M</sub>與此匹配

從喬恩·克萊因伯格和伊娃·塔爾多斯Algorithm Design 7.13相關的residual graph第406頁，

Theorem 7.62陳述：

（7.62）設M是完美匹配。如果在G _中號負成本向圈C，則M不是最低的成本

這個定理是有道理不過，我很困惑，一個perfect matching的bipartite flow network'sresidual graph如何實際包含週期。我能看到一個週期的唯一方法是如果涉及sink或source。

但是在perfect matching中source將不包含離開它的邊，並且sink將不包含進入它的邊。此外，內部節點中出現的週期似乎與Bipartite graph的定義相矛盾。

有人可以在殘差圖中提供這樣一個循環的例子嗎？

Answer 1

當然。考慮a =成本和c =容量的圖：

a=3,c=1 
Ao----->oB 
    \ ^
    \ /a=1,c=1 
    \/ 
    /\ 
/\a=1,c=1 
/ v 
Co----->oD 
    a=3,c=1 

所以顯然有2個可能的最大流量。一個使用水平邊，另一個使用對角線。

對於沿水平線的流動，我們有一個剩餘圖：

a=-3,c=1 
Ao<-----oB 
    \ ^
    \ /a=1,c=1 
    \/ 
    /\ 
/\a=1,c=1 
/ v 
Co<-----oD 
a=-3,c=1 

通知循環B-> A-> D->下用容量1和成本-3 + 1 -3 + 1 = -4。

這個循環的直觀解釋是，每個單位的流量沿着循環的邊緣流動增加 - 或者相反，每個沿相反方向沿其邊緣流動的每個流量的減少 - 我們都會降低總流量成本這是因爲我們將沿着較便宜的對角線邊緣替代沿着相對昂貴的水平邊緣的流動。

在最小成本流量的增廣路徑算法中，我們會繼續前進，沿着這個循環推動1個流量單位，並最終產生沿着對角線的新的更便宜的流量。這將提供新的剩餘圖：

a=3,c=1 
Ao----->oB 
^/
    \ /a=-1,c=1 
    \/ 
    /\ 
/\a=-1,c=1 
    v \ 
Co----->oD 
    a=3,c=1 

現在週期是A-> B-> C-> d和已經花費3 - 1 + 3 - 1 = 4，所以沿着對角線的最大流是一個最小成本最大流量。