There are many common variations of the maximum flow problem. Here are four of t
ID: 3671491 • Letter: T
Question
There are many common variations of the maximum flow problem. Here are four of them.
(a) There are many sources and many sinks, and we wish to maximize the total flow from all sources to all sinks.
(b) Each vertex also has a capacity on the maximum flow that can enter it.
(c) Each edge has not only a capacity, but also a lower bound on the flow it must carry.
(d) The outgoing flow from each node u is not the same as the incoming flow, but is smaller by a factor of (1 u), where u is a loss coefficient associated with node u.
Each of these can be solved efficiently. Show this by reducing (a) and (b) to the original max-flow problem, and reducing (c) and (d) to linear programming.
Explanation / Answer
Im just giving breif answer for the problem,
a) This can be done by introducing a super source vertex S and a super sink vertex T.
connect all sources vertices in the given network to S and all sink vertices to T and find the max flow
from S to T in this graph.
b) let u be any vertex and let cu be the maximum flow that can enter u. split u into tow vertices u1 and u2.
Connect all incoming edges into u to u1 ad outgoing edges from u to u2. Also connect u1 to u2 with an edge of
capacity cu. The following figure shows this transformation.
c) In this standard reduction of max flow an Lp, we have a lower bound of 0 on the flow across any edge. To allow
for this variation, we replace the non-negativity conditions with conditions of lower bounds on the edge flows. If
for edge e, the upper and lower are given by ce and le respectively, then the capacity constraint for edge e is
le<=fe<=ce
d) In the conservation constraints for each vertex u, add a factor of(1-u) to the side representing the flow incoming to vertex u.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.