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

Question

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

algorithmgraphuniquemax-flow

5

以下是需要翻译的内容：

关于以下练习的问题：

设 N=(V,E,c,s,t) 为一个流网络，其中 (V,E) 无环，令 m=|E|。描述一个多项式时间算法，通过解 ≤ m+1 次最大流问题来检查 N 是否具有唯一的最大流。解释算法的正确性和运行时间。

我的建议如下：

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"

有任何反馈吗？我是否忽略了一些不适用的情况？

- Harry

2个回答

3

非整数有理流可以“缩放”为整数
更改边的容量是有风险的，因为某些边可能是关键的，并包含在每个最大流中

有一个更好的运行时解决方案，您不需要检查每条边。创建剩余网络（https://en.wikipedia.org/wiki/Flow_network）。在剩余网络图上运行DFS，如果找到一个环，那么意味着存在另一个最大流，其中至少一条边上的流量不同。

- morgan

这个答案是不正确的！假设G由两条边s->v->t组成，其中s->v的容量为1，v->t的容量为2。显然，G具有唯一的最大(s,t)-流，其值为1。但该流的剩余网络具有通过v和t的长度为2的循环。 - JeffE

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ami Tavory · Accepted Answer

您的问题还有一些细节未明确，例如，这是否是一个整数流图（可能是，尽管如果Ford-Fulkerson收敛，则可以在其他网络上运行），以及您如何定义两个流是否不同（将边缘映射到流的函数是否不同就足够了，还是实际流动的边缘集合必须不同，这是更强的要求）。

如果网络不一定是整数流，则不一定会起作用。考虑以下图形，在每条边上，括号内的数字表示实际流量，括号左侧的数字表示容量（例如，每个和的容量均为1.1，每个流量都为1）。

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

如果网络是整数，则无法保证找到不同的参与边集合。您可以通过以下图表进行查看：

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

充分性 如果您的算法发现了一个与总结果相同但不同的流，则新的流明显是合法的，并且必然至少有一条边的流量与之前不同。
必要性 假设存在一个与原始流（具有相同的总值）不同的流，其中至少有一条边的流量不同。假设对于每条边，替代解决方案中的流量不小于原始解决方案中的流量。由于流量不同，必须至少存在一条边，在该边上，替代解决方案中的流量增加了。然而，如果没有其他边降低流量，就会违反流量守恒定律，或者原始解决方案不是最优解。因此，存在某些边e，在替代解决方案中，其流量低于原始解决方案的流量。由于它是整数流网络，因此流必须至少在e上减少1。然而，根据定义，将e的容量降低至当前流量的至少1，不会使替代流非法。因此，如果降低e的容量，则必须找到一些替代流。