Extension of Integrality Lemma for min-max flow

209 Views Asked by At

The integrality lemma states that if all of the values of the capacities are integers, there is maximum flow in the network which uses an integer value on each edge. One of the ways to prove this is by using 'greedy'(? I'm not sure of the exact name actually) method where you find the maximum flow a path from source to sink, keeping in mind bottlenecks. Since all of the maximum capacities are integers, maximizing the flow per path will give you integer values for every edge.

My question is whether or not this extends to a graph where all of the capacities, say, are a multiple of $n$? Using the same proof as above lemma, I would think that this holds, with the exact same proof. I'm just asking if there is any mistakes in my deduction.

1

There are 1 best solutions below

0
On BEST ANSWER

I think that you are right. The algorithm you are referring to is the Ford-Fulkerson algorithm. You can prove your statement with an inductive argument. So, after each iteration of the algorithm, all flow values on the edges are multiples of $n$, which is presumably indeed analogous to the original proof.