3

Restating the problem a bit: We have a flow graph, G, with integer capacities. Can we find a maximum flow where for at least one of the edges, e, we have f(e) equal to a non-integer?

The first time I tried this I kind of glossed over it and thought that this violated the Integrality Theorem and therefore that it was false, but reading it carefully after makes it clear that it does not break any rules. Apparently it is true.

I've been trying to draw up a simple example to get a visualization, but I can't seem to come up with anything. Can anyone show me an example flow graph where this works?

Improve this question
3
  • Are you aware of en.wikipedia.org/wiki/Max-flow_min-cut_theorem ?
    – Vincent van der Weele
    Commented Nov 23, 2016 at 19:10
  • 1
    Or wait, are you asking if such a flow exists? Of course, if you have multiple outgoing edges from a vertex and their total capacity is greater than the incoming capacity, you can divide the flow in any way you like. But there is no need to use non-integer flows.
    – Vincent van der Weele
    Commented Nov 23, 2016 at 19:13
  • Ah geez, it's so obvious now. Thank you.
    – Maximus Hermius
    Commented Nov 23, 2016 at 19:24

3 Answers 3

Reset to default
13

Yes, it is possible for a maxflow to have non-integer flows on edges with graphs having all integer capacities. Refer to the image. The values in boxes are the flows and the numbers without boxes are capacities.

Flow network

PS : Remember that a graph with integer capacities will always have a integer maxflow value. But it does not rule out the possibility of max flow with non-integer flows on edges.

Improve this answer
1
  • @Maximus Hermius, if you think this answer this correct, can you accept it.
    – foo
    Commented Dec 14, 2016 at 6:50
1

By applying the Ford Fulkerson algorithm, all flow values and all residual capacities remain integer throughout the execution. This means that there exist at least one flow only with integer components.

Improve this answer
-1

One thing I know is it does not terminate yet converge to some input of irrational number.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.