The Integrality theorem in maximum flow
The integraloty theorem tells us that if all capacities in a flow network are integers, then there is a maximum flow where every value is an integer
But the most remarkable part is the existence, not every maximum flow! Which means this statement doesn't claim every maximum flow is integer-valued
I cannot figure out why if all capacities are integer, but there exists a maximum flow is not integer-valued!!
Or did I just get wrong idea of this theorem that tries to tell me?
Answer
Let
- e = edge in the graph.
- c(e) = capacity of the given edge e
- f(e) = amount of flow going through given edge e
The theorem states:
If c(e) for all edges, e, in graph are integers, then there exists a max flow f for which every flow value f(e) is an integer.
Notice the theorem does not place constraint on f(e).
Only c(e) must be integer.
Since "c(e) must be integer" does not imply "f(e) must be integer" as well.
Therefore it is perfectly valid to have non-integer flow with integer capacity.
Here is an example where all capacities are integer with a maximum flow that has some edges that has non-integer flow..
G is the flow Graph I am working with.. N is a maximum integral flow.. N` is a maximum flow where it has some edges has non-integer flow..
pair number on edges are of format: "flow/capacity"
Remember the theorem only says the upper bound of f(u,v) are integers.. it does not say anything about its lower bound.. therefore flow can be any number between 0 and c(u,v)..