在以下两个事实中 second one 是真的：在每个 max flow ，流量 u 至 v 或者 v 至 u 是零。总有一个最大流，即 u 至 v 或者 v 至 u 是零。为什么只有第二个事实是真的而第一个是假的？我不明白。
second one
max flow
u
v
kknvjkwl1#
可以在一个图中构造最大流，其中一些流基本上是一个独立的循环，与整个流没有任何关系。例如，考虑以下图表：
A -2- B -1- C | | 2 2 | | D -2- E
假设我们在寻找从a到c的最大流量。一种可能的方法是这样做：在路径a->b->c上放置一个单位的流量，然后围绕循环a->d->e->b->a逆时针放置一个单位的流量。这确实是一个最大流量，但是在从a到b的边缘上有一个单位的流量。在这个意义上，循环中的流是“无用的”，因为没有一个流能够到达c，但是它遵守流的所有其他规则。这就是为什么第一个说法是错误的。但是，任何最大流都可以转换为不具有此属性的流。对于流动被向前和向后推动的任何边，可以简单地减少两个方向的流动，这样一个方向的流动为零，另一个方向的流动为零。这就是为什么第二种说法是正确的。
1条答案
按热度按时间kknvjkwl1#
可以在一个图中构造最大流，其中一些流基本上是一个独立的循环，与整个流没有任何关系。例如，考虑以下图表：
假设我们在寻找从a到c的最大流量。一种可能的方法是这样做：在路径a->b->c上放置一个单位的流量，然后围绕循环a->d->e->b->a逆时针放置一个单位的流量。这确实是一个最大流量，但是在从a到b的边缘上有一个单位的流量。在这个意义上，循环中的流是“无用的”，因为没有一个流能够到达c，但是它遵守流的所有其他规则。这就是为什么第一个说法是错误的。
但是，任何最大流都可以转换为不具有此属性的流。对于流动被向前和向后推动的任何边，可以简单地减少两个方向的流动，这样一个方向的流动为零，另一个方向的流动为零。这就是为什么第二种说法是正确的。