Question

Extend the flow properties and definitions to the multiple-source, multiple- sink problem. Show that any flow in a multiple-source, multiple-sink flow network corresponds to a flow of identical value in the single-source, single- sink network obtained by adding a supersource and a supersink, and vice versa.

Answer 1

Answer:

We add a super source s and add a directed edge (s, si) with capacity c(s, si) = ∞ for each i = 1, 2, . . . , m. We also create a new super sink t and add a directed edge (ti, t) with capacity c(ti, t) = ∞ for each i = 1, 2, . . . , n. The single source s simply provides as much flow as desired for the multiple sources si, and the single sink t likewise consumes as much flow as desired for the multiple sinks ti.

Because the virtual edges of s and t can consume as much flows as they want, they don't influence the actual edges.

Explanation: