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

Algorithm to determine if a function on a flow network is a valid flow

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

即它需要满足

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

如果我要在这个流网络上做一个 BFS，我担心我会 运行 进入这个问题，对于 DAG 中的每条边，我需要迭代每一个出边和我不确定这是否需要指数时间。这可以在多项式时间内完成吗？

我认为你可以在 O(V+E) 时间内完成:

  1. 对于每个顶点 v 在 0 处创建一个计数器 counter_v。

  2. 对于每条边e，检查f(e)<= c(e)（流量小于容量）。如果不是这种情况，你就完了，这不是一个有效的流程。否则，随着 e 从 v1 -> v2 开始，您按流程递减 v1 的计数器，并按流程递增 v2 的计数器：counter_v1 -= f(e); counter_v2 += f(e)

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

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