Professor claims two distinct maximum flows implies an "infinite number of maximum flows"

StackOverflow https://stackoverflow.com/questions/19893003

  •  30-07-2022
  •  | 
  •  

Question

I will say right out that this is a homework problem that I have attempted for hours and I am not getting anywhere. The problem states "Suppose there exist two distinct maximum flows f₁ and f₂. Show that there exist infinitely many maximum flows." Now, I needed some clarification on what he meant by distinct and the email reply I received stated, "f₁ and f₂ are distinct if there exists (u,v) such that f₁(u,v) ≠ f₂(u,v)." So going off of this definition of distinct, I find the problem statement to not be true.

Take for example this graph:

example graph

It has two distinct maximum flows but no more. What do you guys think? Maybe I am going about this is the wrong way.

Was it helpful?

Solution

If F_1 and F_2 are two maximal flows, then pick any 0 < lambda < 1. Then lambda * F_1 + (1 - lambda) * F_2 is also maximal. This yields an infinite family of maximal flows.

Perhaps your mistake is that you're thinking that flow along a particular edge has to be integral?

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top