Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:deirdre:chapter6 [2014/04/02 03:16] – [7.5 - Bipartite Matching Problem] tobind | courses:cs211:winter2014:journals:deirdre:chapter6 [2014/04/02 03:16] (current) – [7.7 - Extensions to the Max-Flow Problem] tobind | ||
|---|---|---|---|
| Line 252: | Line 252: | ||
| ======7.7 - Extensions to the Max-Flow Problem ====== | ======7.7 - Extensions to the Max-Flow Problem ====== | ||
| - | **The Problem: | + | **Circulations with Demands** |
| Suppose there is now a set //S// of sources generating flow and a set //t// of sinks. Instead of maximizing the flow values, we will consdier a problem where sources have fixed supply values and sinks have fixed demand values. given a flow network with capacities on the edges, each node //v// has a demand //dv//. If //dv// > 0, the node is a sink. If //dv// < 0, it is a source. //S// denotes the nodes with negative; //T// is the set of nodes with positive demands. | Suppose there is now a set //S// of sources generating flow and a set //t// of sinks. Instead of maximizing the flow values, we will consdier a problem where sources have fixed supply values and sinks have fixed demand values. given a flow network with capacities on the edges, each node //v// has a demand //dv//. If //dv// > 0, the node is a sink. If //dv// < 0, it is a source. //S// denotes the nodes with negative; //T// is the set of nodes with positive demands. | ||
| Line 261: | Line 261: | ||
| (7.49) If there exists a feasible circulation with demands {dv}, then Σdv = 0. | (7.49) If there exists a feasible circulation with demands {dv}, then Σdv = 0. | ||
| | | ||
| - | *D & a the alg* | + | |
| See p 382 for proof of: | See p 382 for proof of: | ||
