确定流网络上的函数是否为有效流的算法

Question

​

​

假设在流网络上给出了一些映射f，该映射表示为每个边上的稀疏流矩阵。是否有可能验证这种映射确实是多项式时间内的流？

也就是说，它需要满足

1. 流网络中的每一条边都分配了一个小于容量
2. 的正数，进入一个节点的边等于边缘，留下节点

。

如果我要在这个流网络上做一个BFS，我担心我会遇到这样的问题:对于DAG中的每一个边缘，我都需要遍历每一个输出边缘，我不确定这是否会花费指数时间。这能在多项式时间内完成吗？

Answer 1

我认为你可以在O(V+E)时间内做到这一点：

1. 对于每个顶点v在0.

处做一个计数器counter_v

1. 对于每个边缘e，检查f(e)<= c(e) (流量小于容量)。如果不是这样，你就完事了，这不是一个有效的流程。否则，使用从counter_v1 -= f(e); counter_v2 += f(e)

到e的v1 -> v2，将v1的计数器按流递减，并按流增加v2的计数器：v1 -> v2。

对于除和t以外的每个顶点，请检查计数器是否为0 (通过顶点的总流量为0。)。

就是这样，你检查了每一个顶点两次，每一个边一次，所以O(V+E)