最少边割算法

Question

Let G = (V, E) be a flow network
with source s, sink t, and capacity function c(·). Assume that, for every
edge e ∈ E, c(e) is an integer. Define the size of an s-t cut (A, B) in G
to be the number of edges directed from A to B. Our goal is to identify,
from among all minimum cuts in G, a minimum cut whose size is as small
as possible.
Let us define a new capacity function c'(·) for G as follows. For each
edge e ∈ E, by c'(e) = m·c(e)+1. Suppose (A, B) is a minimum
cut in in G with respect to the capacity function c'(·).
(a) Show that (A, B) is a minimum cut with respect to the original capacity
function c(·).
(b) Show that, amongst all minimum cuts in G, (A, B) is a cut of smallest
size.
(c) Use the results of parts (a) and (b) to obtain a polynomial-time algorithm
to find a minimum cut of smallest size in a flow network.

我该如何用多项式时间算法来解决这个问题？有什么想法吗？

- Programming lover

---

你可以通过谷歌搜索“多项式最小割”并获取这里的第一个搜索结果，然后可能会跟随链接到Edmonds-Karp算法。 - pjs

他们甚至为你提供了新的容量函数。VtC太宽泛，因为这是一个懒惰的作业问题。 - David Eisenstat

可能是查找最小割中的所有边的重复问题。 - grepcake

Answer 1

我不想揭示答案，但我会给未来看到这篇文章的学生一些提示。考虑如果在 G 中取两个最小割(A,B)和(C,D)，其中一个的边数是最小的，而另一个不是。然后将它们映射到 G' 上，并考虑这两个割的值。

提示：最初的回答

- Matthew Riley

Answer 2

搜索Dijkstra算法，通常用于图中的最短路径。我不完全理解您尝试实现的算法，但我觉得它非常相似，并且可以使用与Dijkstra相同的思想。

- R Nar

---

不，Dijkstra算法不适用于流/割。 - pjs