It's possible that by increasing an capacity in some edge that belongs to cross edge of an MIN-CUT, the max flow remain unchanged because there might be multiple min-cut. However, if I decrease the capacity; whether the MIN-CUT unique or not; it seems to me that the max flow will decrease the same amount. However, I can't prove that this holds for all cases (I mean not only integer capacity, but also non-integer, even irrationals)
0
$\begingroup$
$\endgroup$
0
$\begingroup$
$\endgroup$
Suppose $e$ is the edge whose capacity is reduced by $\delta$. The capacity of all cuts such that $e$ is one of their cross edges is decreased by $\delta$. The capacity of all other cuts is unchanged. If $e$ is a cross edge of a source-sink minimum cut, the capacity of the minimum cut decreases by $\delta$.
answered Nov 8 '17 at 2:49
-
$\begingroup$ isn't that with irrational capacity, we can never have a min-cut? because the algorithm of finding max-flow will never halt $\endgroup$ – ElleryL Nov 8 '17 at 3:15
-
$\begingroup$ Some variants of the Ford-Fulkerson augmenting path method may not terminate on some networks with irrational capacities, but other variants are guaranteed to terminate. $\endgroup$ – Fabio Somenzi Nov 8 '17 at 4:05
