bipartite - 最大流量中的积分定理

Question

积分定理告诉我们，如果流网络中的所有容量都是整数，那么存在一个最大流，其中每个值都是整数

但最显着的部分是存在，不是每一个最​​大流量！这意味着该语句并未声称每个最大流量都是整数值

我无法弄清楚为什么如果所有容量都是整数，但存在最大流量不是整数值！

还是我只是对试图告诉我的这个定理有错误的想法？

Answer 1

让

• e = 图中的边。
• c(e) = 给定边 e 的容量
• f(e) = 通过给定边 e 的流量

该定理指出：

如果图中所有边 e 的 c(e) 都是整数，则存在一个最大流 f，其中每个流值 f(e) 都是整数。

请注意，该定理没有对f(e)施加约束。

只有c(e)必须是整数。
由于“c(e) 必须是整数”并不意味着“f(e)也必须是整数”。
因此，具有整数容量的非整数流是完全有效的。

这是一个示例，其中所有容量都是整数，最大流具有一些具有非整数流的边。

G 是我正在使用的流图.. N 是最大积分流.. N` 是最大流，它有一些边有非整数流..

边缘对数的格式为：“流量/容量”

请记住，该定理只说 f(u,v) 的上限是整数.. 它没有说明它的下限.. 因此流可以是 0 和 c(u,v) 之间的任何数字..

Answer 2

如果使用 Ford-Fulkerson 方法获得最大流量，则结果流量必须是整数值

但是，我们仍然可以有一个最大流，它使用实数作为边缘上的流值

检查这个例子：

          B
        /   \
       /     \
      /       \

s-----A t

      \       /
       \     /
        \   /
          C

边的方向都是从左到右，(s,a) 有 1 个流和 1 个容量，

其余的都是 0.5 流量和 1 容量。

这是具有最大流量但不是整数值的流量网络。