最大流量

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被允许去做。