Suppose we have a Directed Graph and each edges has a positive capacity. if C is a positive constant, i say, if we add or subtract C to all edges capacity, the maximum flow, changed, (maybe increase or decrease). my question is, why if we multiply all edges capacity into C, the maximum flow is product by C?
why this is true?
On
One way to think about this is by the infamous max flow - min cut theorem which states;
The maximum value of the flow from a source node s to a sink node t in a capacitated network equals the minimum capacity among all s-t cuts. [S,Sbar]
Since, after multiplying all capacities by a constant C, the minimum s-t cut doesn't change, moreover the capacities of arcs emanating from S are all multiplied by C, the new capacity of the min s-t cut will be C times the previous capacity, which means the new maximum flow value will be the old max flow value * C.
Suppose you are given some flow function and some capacity function. Observe that if we multiply all capacities and flows by $C$, then we get the proper flow. Indeed, it is trivial to check that capacity constraints, skew symmetry and flow conservations still hold. Moreover, the value of the flow is $C$ times as big. Similarly for any flow in network with capacities multiplied by $C$ we can construct a flow with $C$ times smaller value.