java - 关于最大流量的一些事实令人惊讶

Question

以下两个事实second one是正确的：

在 every中， to或to的max flow流量为零。uvvu

总是有一个最大流量，因此流向或流向为零。uvvu

为什么只有第二个事实是真的而第一个是假的？我无法理解。

标签： javaalgorithmdata-structuresgraphtree

Answer 1

可以在图中构建最大流量，其中一些流量基本上是一个独立的循环，对整体流量完全没有影响。例如，考虑这个图表：

A -2- B -1- C
|     |
2     2
|     |
D -2- E

想象一下，我们正在寻找从 A 到 C 的最大流量。一种可能的方法是执行以下操作：在路径 A -> B -> C 上放置一个流量单位，然后在周围逆时针放置一个流量单位循环 A -> D -> E -> B -> A。这确实是一个最大流量，但是在从 A 到 B 的边缘上各有一个流量单位。这里围绕循环的流量是“无用的”从某种意义上说，没有一个流程可以到达 C，但它确实遵守流程的所有其他规则。这就是为什么第一个说法是错误的。

但是，任何最大流量都可以转换为不具有此属性的最大流量。对于向前和向后推动流量的任何边缘，您可以简单地减少两个方向的流量，使得一个方向的流量为零，而剩余的流量则流向另一方向。这就是为什么第二个说法是正确的。