Difference between revisions of "Maximum flow"

Revision as of 02:06, 7 September 2013

The maximum flow problem is an optimization problem in graph theory. It deals with a special kind of graph, known as a flow network. A flow network is a directed graph with the following properties:

1. There are two special nodes, the source (usually denoted s), and the sink (usually denoted t).
2. No edges enter the source nor leave the sink.
3. To each edge we associate a non-negative real number called the capacity. Thus, we can represent a flow network similarly to how we would represent a weighted graph.

A flow network may be used to model real-life systems in which some substance flows from one place (the source) to another (the sink), going through any number of intermediate locations (other nodes) along paths of various maximum capacities connecting locations (edges). This is the motivation behind the statement of the maximum flow problem.

In order to state the problem, we first have to define the concept of an admissible flow. An admissible flow is an assignment of a non-negative real number to each edge (which we call the flow along that edge) such that the flow along an edge never exceeds the capacity of that edge, and such the flow "balances" at each vertex other than the source and sink, meaning that the total flow at incoming edges equals the total flow at outgoing edges at each vertex.

The balance condition may be thought of as a precise statement of the idea that the vertices have no capacities of their own; they serve only as connecting points for the edges and cannot store excess incoming flow nor discharge stored flow when the incoming flow is running low. In one possible analogy, the edges represent pipes, each of which has some maximum rate at which it can transport water (the capacity). An admissible flow then corresponds to some way of sending water through the pipes from source to sink through a series of intermediate nodes. The rate at which water flows into an intermediate node must equal the rate at which water flows out of the same node, because the nodes can't store excess water, and water can't just come out of nowhere. In another possible analogy, the edges represent conducting wires, each of which has some maximum amount of current it can conduct before it overheats and melts; the source represents a generator and the sink represents a device that consumes electrical power. Here, the balance condition is Kirchhoff's current law, stating that the total current flowing into a vertex equals the total current flowing out of it, and corresponds to the fact that any imbalance in current would result in an accumulation of either positive or negative charge at that vertex.