Flows and Cuts

From IFORS Education Resources
Jump to: navigation, search

By: Michel X. Goemans


Maximum Flows

Network flows deals with modelling the flow of a commodity (water, electricity, packets, gas, cars, trains, money, or any abstract object) in a network. The links in the network are capacitated and the commodity does not vanish in the network except at specified locations where we can either inject or extract some amount of commodity. The main question is how much can be sent in this network.

Cuts

In this section, we derive an important duality result for the maximum flow problem, and as usual, this takes the form of a minmax relation.


Link to material: http://math.mit.edu/~goemans/18433S09/flowscuts.pdf


Personal tools