網絡的最大流量是不是唯一的

Question

看看下面的圖片：

我試圖找到從S最大流量使用福特Fulkerson算法爲T，但我發現了兩個答案。一個是12返回12的另一個14

的答案：

s->a->d->t = 2 
s->b->e->t = 3 
s->b->g->t = 2 
s->c->b->d->t =2 
s->c->g->t = 3 

再次另一個它返回12：

​​

並返回14的答案：

s->a->e->t =2 
s->b->d->t =4 
s->b->e->t =3 
s->b->g->t =2 
s->c->g->t =3 

這是爲什麼？這是正常的還是我在做什麼錯？

Answer 1

的問題是，當你正在尋找可增廣流允許您：

1. 走邊前進，其中流量小於容量
2. 去向後沿着邊緣，其中流量大於0

   s->b->d->a->e->t (add 2 flow) 
   

   ：

所以在你的第一個例子中，你可以通過追蹤路徑添加更多的流量

請注意，d-> a部分正在沿着已經流過它的邊緣倒退。

從wikipedia：

注意，可能發生的是從v到u的流被允許的殘留網絡中，雖然禁止原有網絡中：如果f（U，V）> 0和c （v，u）= 0，則c_f（v，u）= c（v，u）-f（v，u）= f（u，v）> 0。

一旦你增加了所有可能的增廣路徑的流量，最大流量的值將始終是相同的值。 （雖然請注意可能有許多不同的方法來達到這個值。）