具有整数容量的流程图在最大流量中是否具有非整数流量的边？

Question

稍微重申一下问题：我们有一个流程图G，它的容量为整数。我们是否可以找到最大流量，其中至少有一条边e（f（e）等于非整数）？

第一次尝试时，我对它有所掩饰，并认为它违反了完整性定理，因此它是错误的，但是在仔细阅读后清楚地表明它没有违反任何规则。显然是真的。

我一直在尝试绘制一个简单的示例以获得可视化效果，但是我似乎什么都没想。谁能告诉我一个流程图示例在哪里工作？

Answer 1

是的，maxflow可能在具有所有积分能力的图的边上具有非积分流。参考图像。框中的值是流量，没有框的数字是容量。

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