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?
Best Answer
One way to think about this is by the infamous max flow - min cut theorem which states;
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.