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

Question

稍微重述一下问题:我们有一个流图 G，其容量为整数。我们能否找到最大流，其中至少有一条边 e 的 f(e) 等于非整数？

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

我一直在尝试绘制一个简单的示例来进行可视化，但我似乎什么都想不出来。任何人都可以向我展示一个示例流程图吗？

Answer 1

是的，最大流有可能在具有所有整数容量的图的边上具有非整数流。请参阅图片。方框内的值是流量，没有方框的数字是容量。

PS:请记住，具有整数容量的图将始终具有整数 maxflow 值。但不排除边上有非整数流的最大流的可能。