爲什麼我們使用最大流法來求解最大二分配匹配？

Question

例如

有A [0]和A [1]和B [0]和B [1]

LINK（A [0]，B [0]）

LINK （A [0]，B [1]）

LINK（A [1]，B [0]）

最大匹配是（A [0] .B [1]）和（A [ 1]，B [0]）

但是對於最大流量查找方法，我們在後面建立一個源A和B後水槽

，並且該方法將在每次嘗試外面有一個路徑

時間找到一個路徑是：它首先得到A [0]對與B [0]

然後使用路徑B [0]到接收器，沒有路徑A [1]對B [0]

它絕對不能解決這個問題，但我發現教科書，維基，博客和網站只是說它的結果是相同的作爲最大二分配匹配

PS

設C（X，Y）是X-> Y「S值

通過應用ALG，

第一迭代：設置C（S，A [0]）= 0;集C（A [0]，S）= 1（反轉流動）

並且還，A [0]與B [0]，B [0]與叔

第二迭代：它找到路由從s到t，只有C（B [1]，T）= 1

所以，第二次迭代沒有發現點用於連接B [1]

Answer 1

實際上最大流將能夠事正確鏈接。將有第二次迭代，其中來自A [1]的流可以轉到B [0]，同時反轉從鏈路中的流從A [0]到B [0]。

您可以查看它可以做到的Ford-Fulkerson算法。

編輯：

假設你開始與源節點S（LINK（S，A0）和LINK（S，A1））（和一個結束節點F）如果應用在第一次迭代你的算法最後會像你說的那樣以A0-> B0結束。我將詳細介紹第二次迭代。

1）「S」; T = {S}; E = {}

• 標籤（A1）= {S +，1}，T = {S A1}
• E = {S}

2） 「A1」; T = {S A1}; E = {S}

• 標籤（B0）= {A1 +，1}，T = {S A1 B0}
• E = {S A1}

3） 「B0」; T = {S A1 B0}; E = {S A1}

• 標籤（A0）= {B0-，1}; T = {S A1 B0 A0}
• E = {S A1 B0}

4） 「A0」; T = {S A1 B0 A0}; E = {S A1 B0}

• 標籤（B1）= {A0 +，1}; T = {S A1 B0 A0 B1}
• E = {S A1 B0 A0}
• 不要檢查「S」，因爲它已經在T！

5）「B1」; T = {S A1 B0 A0 B1}

• 標籤（F）= {B1 +，1}; T = {S A1 A0 B0 B1 F}
• E = {S A1 A0 B0 B1}

而且它超過，則流程現在最大化。