算法：检查最大流量是否唯一

Question

以下练习的一个问题：

\n\n

\n

令 N = (V,E,c,s,t) 为流网络，使得 (V,E) 是无环的，并令 m = |E|。描述一个多项式时间算法，通过解决 \xe2\x89\xa4 m + 1 最大流问题来检查 N 是否具有唯一的最大流。\n 解释该算法的正确性和运行时间

\n

\n\n

我的建议如下：

\n\n

run FF (Ford Fulkerson) once and save the value of the flow v(f) and the flow over all egdes f(e_i)\nfor each edge e_i with f(e_i)>0:\n    set capacity (in this iteration) of this edge c(e_i)=f(e_i)-1 and run FF. \n    If the value of the flow is the same as in the original graph, then there exists another way to push the max flow through the network and we\'re done - the max flow isn\'t unique --> return "not unique"\n    Otherwise we continue \n\nwe\'re done with looping without finding another max flow of same value, that means max flow is unique -> return "unique"\n

\n\n

任何反馈？我是否忽略了一些不起作用的情况？

\n

Answer 1

你的问题留下了一些细节，例如，这是一个整数流图（可能是的，尽管福特-富尔克森，如果它收敛，也可以在其他网络上运行），以及你如何准确定义两个流是否不同（将边映射到流的函数不同就足够了，还是实际流动的边集必须不同，这是一个更强的要求）。

如果网络不一定是整数流，那么，不，这不一定有效。考虑下图，其中，在每条边上，括号内的数字代表实际流量，括号左侧的数字代表容量（例如，（a，c）和（c， d)为1.1，各流量为1)：

在此图中，流不是唯一的。通过(a, b)和(b, d)浮动 0.5 可以总共流动 1 。然而，您的算法无法通过将每个边的容量减少到其当前流量以下 1 来找到这一点。

如果网络是整数，则不能保证找到与当前参与边不同的一组参与边。您可以通过下图看到：

最后，如果网络是整数流网络，并且不同流的含义只是边到流的不同函数，那么您的算法是正确的。

1. 充分性如果您的算法发现具有相同总结果的不同流，那么显然新流是合法的，而且，也必然至少有一条边的流动量与之前不同。

2. 必要性假设存在与原始流量不同的流量（具有相同的总值），并且至少有一条边的流量不同。假设对于每条边，替代解中的流量不小于原始解中的流量。由于流量不同，因此必须至少存在一条边，替代解决方案中的流量增加。但是，如果没有不同的边减少流量，则要么违反流量守恒定律，要么原始解决方案不是最优的。因此，存在一些边e，其中替代解决方案中的流量低于原始解决方案中的流量。由于它是一个整数流网络，因此流必须至少比e低 1 。不过，根据定义，将e的容量减少到至少比当前流低 1 不会使替代流非法。因此，如果e的容量减少，则必须找到一些替代流。