The Integrality theorem in maximum flow

Question

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?

Burkhard

Answer 1

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)..

Crackerbarrel

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review – Celisse

@eirenaios Picture added. Thank you for the tip! – Crackerbarrel

looks great! Keep it up! – Celisse

Answer 2

If using Ford-Fulkerson method to get a maximum flow, then the resulted flow must be integer-valued

But, we still can have a maximum flow that use real number as the flow value on the edges

Check this example:

          B
        /   \
       /     \
      /       \

s------A　　　　　　t

      \       /
       \     /
        \   /
          C

the directions of edges all go from left to right , and the (s,a) has 1 flow and 1 capacity,

and rest of all all go with 0.5 flow and 1 capacity.

This is flow network having a maximum flow but not integer-valued.

Burkhard