algorithm - 最小割边最少的算法

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.

如何为此编写多项式时间算法？有什么想法吗？

Answer 1

我不会剧透这个答案，但是我会给以后看到这个帖子的同学留下一个提示。考虑一下如果您在 G 中采用两个最小切割 (A,B) 和 (C,D) 会发生什么情况，这样一个中的边数最少而另一个中的边数不是。然后将它们映射到 G' 并考虑这两个切割的值。