algorithm - 具有整数容量的流图可以在其最大流中具有非整数流的边吗？

Question

稍微重申一下这个问题：我们有一个流程图 G，它具有整数容量。我们能否找到一个最大流，其中至少有一个边 e，我们有 f(e) 等于一个非整数？

我第一次尝试这个时，我有点掩饰它，并认为这违反了完整性定理，因此它是错误的，但仔细阅读后发现它并没有违反任何规则。显然这是真的。

我一直在尝试绘制一个简单的示例来获得可视化，但我似乎无法提出任何建议。任何人都可以向我展示一个可以使用的示例流程图吗？

Answer 1

是的，maxflow 可能在边上具有非整数流，而图具有所有整数容量。参考图片。方框中的值是流量，没有方框的数字是容量。

PS：请记住，具有整数容量的图将始终具有整数 maxflow 值。但这并不排除边缘上存在非整数流的最大流的可能性。

Answer 2

通过应用 Ford Fulkerson 算法，所有流量值和所有剩余容量在整个执行过程中保持整数。这意味着至少存在一个仅具有整数分量的流。