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

Question

下面练习的一道题：

Let N = (V,E,c,s,t) be a flow network such that (V,E) is acyclic, and let m = |E|. Describe a polynomial- time algorithm that checks whether N has a unique maximum flow, by solving ≤ m + 1 max-flow problems. Explain correctness and running time of the algorithm

我的建议如下：

run FF (Ford Fulkerson) once and save the value of the flow v(f) and the flow over all egdes f(e_i)
for each edge e_i with f(e_i)>0:
    set capacity (in this iteration) of this edge c(e_i)=f(e_i)-1 and run FF. 
    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"
    Otherwise we continue 

we're done with looping without finding another max flow of same value, that means max flow is unique -> return "unique"

有什么反馈吗？我是否忽略了一些不起作用的情况？

Answer 1

您的问题留下了一些细节未解决，例如，这是一个整数流图吗（可能是的，尽管 Ford-Fulkerson 如果收敛，也可以运行在其他网络上收敛），以及究竟如何您是否定义两个流是否不同（将边映射到流的函数是否足够，或者实际流动某物的边集是否必须不同，这是一个更强的要求）。

如果网络不一定是整数流，那么，不，这不一定行得通。考虑下图，其中，在每条边上，括号内的数字代表实际流量，括号左边的数字代表容量（例如，每个 (a, c 的容量)和(c,d)为1.1,各自的流量为1.):

在此图中，流是非唯一的。通过 (a, b) 和 (b, d) 浮动 0.5 可以使总共 1 流动。但是，您的算法不会通过将每条边的容量减少到低于其当前流量的 1 来找到它。

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

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

足够如果你的算法找到了一个不同的流，总的结果是一样的，那么显然新的流是合法的，而且，也，必然，至少其中一条边的流动量与以前不同。
必要性假设存在与原始流量不同的流量（具有相同的总值），至少有一条边流量不同.也就是说，对于每条边，替代解决方案中的流量不小于原始解决方案中的流量。由于流量不同，因此必须至少有一个边缘，替代解决方案中的流量增加。但是，如果没有不同的边减少流量，就会违反流量守恒，或者原始解决方案不是最优的。因此，存在一些边缘 e，其中替代解决方案中的流量低于原始解决方案中的流量。由于是整数流网络，所以流在e上至少要低1。但是，根据定义，将 e 的容量减少到至少比当前流低 1，不会使替代流非法。因此，如果 e.

Answer 2

非整数，有理流可以'scaled'到整数
更改边缘容量是有风险的，因为某些边缘可能很关键并且包含在每个最大流量中

有更好的运行时间解决方案，您不需要检查每条边。创建一个残差网络 (https://en.wikipedia.org/wiki/Flow_network)。运行残差网络图上的DFS，如果你找到一个圆圈就意味着还有另一个最大流，其中至少有一条边上的流是不同的。

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

Algorithm: Check if max flow is unique

algorithm

graph

unique

max-flow