最大流量

Question

基本defintions：

容量約束：對於所有的U，V V，我們需要F（U，V）< = C（U，V）。對於所有u，v V，我們需要u（u，v）= -f（v，u）。

流守恆：對於所有u屬於N - {S，T}，我們需要（（（Ⅴ總和屬於V））F（U，V））= 0

讓F1 f2是流動網絡G =（V，E）中的流量。對於所有（u，v）屬於V，總和f1 + f2由 （f1 + f2）（u，v）= f1（u，v）+ f2（u，v）定義。以下由f1 + f2滿足。

容量限制：可能會被明顯違反。我們有： （f1 + f2）（u，v）= f1（u，v）+ f2（u，v）= -f1（v，u）-f2（v，u）歪斜的對稱性： = - （F1（v，U）+ F2（v，U））= - （F1 + F2）（v，U）

我的問題是下面

1. 容量contraint是如何侵犯在上面？

2. 什麼是流量守恆？以及爲什麼在不包含源和罐的頂點的流量守恆總和爲零？請求幫助簡單的例子。

謝謝！

Answer 1

1. 流量確實被侵犯。看下面的例子：f1(u,v) = f2(u,v) = c(u,v) > 0。對於每個f1,f2保留約束，因爲它們都不大於c。但是，看看f1+f2：f1+f2(u,v) = f1(u,v) + f2(u,v) = 2*c(u,v)，因爲對於這個例子c(u,v) > 0，明確f1+f2(u,v) > c(u,v)，所以容量約束不保留。

2. 流量守恆基本上是：除了s，t之外的每個頂點：相同的流量進入頂點並離開頂點。所以V \ {s，t}中的每個v不是「創建」任何流，也不是消耗任何流：只有s，t被允許去做。