Solution Found!
Consider the following generalization of the maximum flow problem.You are given a
Chapter 7, Problem 7.20(choose chapter or problem)
Consider the following generalization of the maximum flow problem.
You are given a directed network \(G=(V, E)\) with edge capacities \(\left\{c_{e}\right\}\). Instead of a single \((s, t)\) pair, you are given multiple pairs \(\left(s_{1}, t_{1}\right),\left(s_{2}, t_{2}\right), \ldots,\left(s_{k}, t_{k}\right)\), where the \(s_{i}\) are sources of \(G\) and \(t_{i}\) are sinks of \(G\). You are also given \(k\) demands \(d_{1}, \ldots, d_{k}\). The goal is to find \(k\) flows \(f^{(1)}, \ldots, f^{(k)}\) with the following properties:
\(f^{(i)}\) is a valid flow from \(s_{i} \text { to } t_{i}\).
For each edge e, the total flow \(f_{e}^{(1)}+f_{e}^{(2)}+\cdots+f_{e}^{(k)}\) does not exceed the capacity \(c_{e}\).
The size of each flow \(f^{(i)}\) is at least the demand \(d_{i}\).
The size of the total flow (the sum of the flows) is as large as possible.
How would you solve this problem?
Questions & Answers
QUESTION:
Consider the following generalization of the maximum flow problem.
You are given a directed network \(G=(V, E)\) with edge capacities \(\left\{c_{e}\right\}\). Instead of a single \((s, t)\) pair, you are given multiple pairs \(\left(s_{1}, t_{1}\right),\left(s_{2}, t_{2}\right), \ldots,\left(s_{k}, t_{k}\right)\), where the \(s_{i}\) are sources of \(G\) and \(t_{i}\) are sinks of \(G\). You are also given \(k\) demands \(d_{1}, \ldots, d_{k}\). The goal is to find \(k\) flows \(f^{(1)}, \ldots, f^{(k)}\) with the following properties:
\(f^{(i)}\) is a valid flow from \(s_{i} \text { to } t_{i}\).
For each edge e, the total flow \(f_{e}^{(1)}+f_{e}^{(2)}+\cdots+f_{e}^{(k)}\) does not exceed the capacity \(c_{e}\).
The size of each flow \(f^{(i)}\) is at least the demand \(d_{i}\).
The size of the total flow (the sum of the flows) is as large as possible.
How would you solve this problem?
ANSWER:Step 1 of 4
Flow network:
Flow network comprises a directed graph G(V, E), two special vertices in a graph, a source (s), and a sink (t). Flowing of the network starts from ‘s’ and flows end up at ‘t’. All other vertices are called internal. Every edge of the graph has a capacity that indicates how much flow is possible to send directly between the two vertices. That’s a flow network. The flow itself is a function from a pair of vertices to the non-negative real and it can’t exceed the capacity of edges.
