查找流網絡的最小割

Question

我試圖找到下面網絡的最小割

我使用下面的算法：

1. 潤福特Fulkerson算法，並考慮最終殘差圖。

2. 找到殘差圖中可以從源訪問的一組頂點。

3. 從可到達頂點到不可到達頂點的所有邊都是最小切割邊。打印所有這些邊緣。

在第一步驟中，我的算法找到3條路徑：

- s->b->h->t **value: 1** 
- s->d->e->t **value: 1** 
- s->c->h->i->m->d->g->t **value: 0.5** 

所以最大流量（並且因此最小割）等於2.5。

然而，當我稍後嘗試消除來自網絡I結束了這樣的上述路徑：

可到達頂點是S，C和H，其形成等於3.5的切口。

我錯過了什麼？爲什麼我不能像通常那樣遍歷圖表來得到最小值？

Answer 1

每次增加殘差圖中邊的容量時，都需要增加相同邊的容量。

實施例圖：

這裏是不向後邊緣剩餘圖和從S的該組頂點的可達（其不構成最小割）：

以及最小切割的正確殘差圖：

Answer 2

我假定，您的剩餘圖的定義是，你把邊緣A-> B在剩餘圖，如果：

一個）有流和容量之間的一些不同的方向A-> B（又名向前邊沿） b）方向B-> A（又名後沿）有一些流動

在這個定義中你的第2步是錯誤的。

要找到最小剪裁，您只能從開頭走過前緣。現在，您可以將從起點到達的頂點表示爲集合R，並將其作爲集合R'休息。 現在切割由R和R'之間的邊緣完成。 切割的大小是R和R'之間的流動。