最小割/在向圖

Question

最大流量我有向圖

首先，我用福特 - 富爾克森的算法，以增加網絡的流量。當我標了頂點，我看到了路徑流動：s->a->b->d->t可以增加一個這樣圖表改爲：

我知道，最大流量搜索的時候，你需要添加了所有的capacaties連接圖的最小切割和外部部分的邊。 我最小割包含頂點：s, a, c，所以當我加入了我的c(G, !G) = 3 + 2 +2 + 1所有邊緣，然而，這是不是流向t這是5

我在做什麼錯大了很多，我已經搞砸了用FF還是最小限度？

Answer 1

你最低限度的不是s, a, c，而是s, a, b, c。其容量是5，這是您計算的最大流量。

您可以使用剩餘網絡的定義找到最小切割。回想一下，當剩餘網絡中的s和t之間沒有路徑時，Ford-Fulkerson終止。

的最小切(S,T)被定義爲

S = { v | there exists a path from s to v in the residual network } 

在你曲線圖中，節點b可達從殘餘網絡中c因爲流動b->c與重量3的。