2
$\begingroup$

Suppose I have a Network N

( i.e. just a Digraph D(A,V) with A=Arcs, V=Vertices; combined with a capacity function $c:V x V \to \mathbb{N}\cup\{0\}$ and two vertices s:=source, t:=sink singled out)

I call $f:V x V \to \mathbb{N}\cup\{0\}$ a flow if it does not exceed capacity for any pair (u,v) and the net flow at any vertex is zero expect at the source and sink where a net flow is allowed.

Now suppose I have a way of knowing the value of the maximum flow (this value just being the maximum flow $\sum_{(s,v)\in A} f(source,v)$ out of the source in any legal flow f. Similarly this value will equal the max total flow into the sink in any flow)

I am wondering whether there is a clever way to determine the actual flow function say $f^*$ given that I know what the maximum flow value is ?

If I had a way of knowing what the value of such a maximum flow is for any network N at no extra "cost" would this give me a more efficient way ? So far I have only used Ford Fulkerson to determine $f^*$

1 Answers 1

1

In "toy" examples (examples small enough to do easily by hand), knowing the maximal flow can often be used to find a flow achieving that maximum value. But in "real" examples, with hundreds of vertices and thousands of arcs, I don't think it helps at all. If it did, you could make a guess at the maximal flow, then use the clever method to find the flow with that value; if the clever method succeeds, guess a little higher, if it fails, guess a little lower, until you converge on the right answer, so you'd wind up beating Ford-Fulkerson.