最大流量和一些条件

Question

假设我们有一个有向图,每个边都有一个正容量.如果C是正常数,我说,如果我们将C加到或减去所有边缘容量,最大流量就会改变,(可能增加或减少).我的问题是,为什么如果我们将所有边缘容量乘以C,最大流量是C乘积？

为什么这是真的？

Answer 1

声称是正确的,因为最大流量也是最小流量.

让老容量w:E->N,而新产能w':E->N,使得w'(e) = C*w(e)

最小切割是切割中w'(e_i)每个切割的总和e_i,但从那以后w'(e_i) = C*w(e_i),我们可以说最小切割是sum (C*w(e_i)) = C * sum(w(e_i)).

另外,因为对于每个切割X sum(w(e_i) | e_i in min cut) <= sum(w(e_i) | e_i in cut sum X):,通过乘以任何常数,C我们得到:

C* sum(w(e_i) | e_i in min cut) <= C*sum(w(e_i) | e_i in some cut X)
sum(C * w(e_i) | e_i in min cut) <= sum(C*w(e_i) | e_i in some cut X)
sum(w'(e_i) | e_i in min cut) <= sum(w'(e_i) | e_i in some cut X)

因此,"旧"最小切割也是"新"最小切割(乘以C),因此网络的总体最大流量增加了C倍.