Flow graph force flow to "move" together

64 Views Asked by At

Can I design a graph for finding maxflow where I force flow to go through a specific vertex "as a whole"? For example if a vertex get flow 10, and it has multiple outgoing edges, can I make sure he only moves 10 and not separates it to 5 and 5 for example?

I mean, make sure "by design" of the graph, and not by programming the maxflow algo this way.

Hopefully the question is well defined enough. Thanks!

1

There are 1 best solutions below

0
On BEST ANSWER

Technically, yes, but I'm not sure this what you are going for: make sure there is only one path between the source and the sink.

If there are multiple such paths, you cannot do this for every algorithm, because the algorithm can do suboptimal moves (it can push through only a fraction of available flow).

Yet, assuming you are using any augmenting-paths algorithm (one popular approach), the first thing the algorithm tries is to push the flow through a single path, so if that works, it won't split the flow (there are some cases to consider, but it's possible).

Finally, if capacities are integers, any standard flow algorithm (other than an LP solver) will keep all the flows as integers (it will not itroduce fractions). So if the maximum flow from that vertex to the sink is $1$, it will not be splitted.

I hope this helps $\ddot\smile$