Difference between revisions of "Maximum flow"

Latest revision as of 03:22, 9 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.

The flow network[edit]

A flow network is a directed graph with the following properties:

There are two special nodes, the source (usually denoted s), and the sink (usually denoted t).
No edges enter the source nor leave the sink.
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.

We may describe a flow network mathematically as a tuple $(V, s, t, c)$ where $s, t \in V$ , $c:V \times V \to [0, \infty)$ , and $\forall v, c(v, s) = c(t, v) = 0$ . Here $c(u, v)$ is the capacity of the edge from $u$ to $v$ . When we talk about an edge in a flow network, we are talking about an ordered pair of vertices $(u, v)$ for which $c(u, v) > 0$ . That is, we say that an edge exists from $u$ to $v$ if and only if $c(u, v) > 0$ .

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.

Admissible flows[edit]

In order to state the maximum flow problem, we must first define the concept of an admissible flow. We have a flow network, and this flow network has a capacity function that represents, in some sense, the maximum rate at which flow can occur between a given pair of vertices. An admissible flow is an actual choice of how much flow to send between each pair of vertices. Of course, this cannot exceed the capacity. Furthermore, sending $x$ units of flow from vertex $u$ to vertex $v$ is equivalent to sending $-x$ units of flow from vertex $v$ to vertex $u$ . Finally, flow is not allowed to "accumulate" at a vertex; the amount flowing in must equal the amount flowing out.

Mathematically, an admissible flow is a function $f: V \times V \to \mathbb{R}$ such that:

Capacity constraint: $\forall u, v \in V \times V, f(u, v) \leq c(u, v)$ .
Skew symmetry: $\forall u, v \in V, f(u, v) = -f(v, u)$ .
Conservation of flow: $\forall u \in V, \sum_{v \in V} f(u, v) = 0$ .

Note that the conservation constraint is more naturally translated as $\forall u \in V, \sum_{v \in V} f(u, v) = \sum_{v \in V} f(v, u)$ based on our description above ("the amount flowing in must equal the amount flowing out"). However, as a consequence of the skew symmetry constraint, $\sum_{v \in V} f(v, u) = \sum_{v \in V} -f(u, v) = -\sum_{v \in V} f(u, v)$ . If this is to equal $\sum_{v \in V} f(u, v)$ , then this quantity must be identically zero.

An edge $(u, v)$ and its reverse edge $(v, u)$ may have different capacities. For example, if $c(u, v) = 5$ and $c(v, u) = 3$ , then we can, for example, send 4 units of flow from $u$ to $v$ and -4 units from $v$ to $u$ . (Negative flow always satisfies a capacity constraint.) We cannot send 4 units of flow from $v$ to $u$ and -4 units from $u$ to $v$ , however, because $4 > 3 = c(v, u)$ . If positive flow goes from $v$ to $u$ , we can only send up to 3 units. We also cannot send 5 units from $u$ to $v$ and 3 units from $v$ to $u$ , because this violates skew symmetry.

In the remainder of this article, flow will mean admissible flow when the context is appropriate.

Analogies[edit]

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. In this analogy, the role of skew symmetry is clearer. In circuit analysis, sending a positive current from one node to another is equivalent to sending the same amount of negative current in the other direction.

Residual network[edit]

Given a flow network $(V, s, t, c)$ and a flow $f$ , we may form the residual capacity network or simply residual network $(V, s, t, r)$ . This is a new flow network in which $r(u, v) = c(u, v) - f(u, v)$ . Because $c(u, v) - f(u, v) \geq 0$ for any valid flow, $r$ is a valid capacity function (takes on nonnegative values only). The residual network may contain edges that the original network does not. In particular, if $c(u, v) > 0$ and $c(v, u) = 0$ , and we send flow from $u$ to $v$ in $f$ , that is, $f(u, v) > 0$ , then $r(v, u) = c(v, u) - f(v, u) = 0 + f(u, v) > 0$ . In other words, sending flow in one direction between two vertices can generate a back edge in the residual network. If a reverse edge already existed, then sending flow along the forward edge causes the capacity of the reverse edge to increase in the residual network.

The residual network tells us how much capacity is left in the original flow network after we've already sent some flow through it. The appearance of back edges corresponds to the fact that we are now allowed to send flow in the other direction to cancel out the existing flow. For example, if $c(u, v) = 8$ and $c(v, u) = 0$ , and $f(u, v) = 6$ , then $r(u, v) = 2$ and $r(v, u) = 6$ . We can send further flow of up to 2 units in the $u$ to $v$ direction, or we can send flow from $v$ to $u$ of up to 6 units. As long as we do not send more than 6 units in the $v$ to $u$ direction, this will just cancel out the existing flow and the total flow from $v$ to $u$ will still be less than or equal to zero, which makes the flow valid for the original network.

Statement of the problem[edit]

Given an admissible flow, although incoming flow and outgoing flow balance at all vertices other than the source and the sink, the same is not true at the source and sink. Indeed, we can have flow out from the source, but not in, since no edges enter the source; we can have flow into the sink but not out, since no edges leave the sink. The objective of the problem is to find an admissible flow that maximizes the total flow out of the source or into the sink. Such a flow is called a maximum flow.

Proposition: The total outgoing flow at the source equals the total incoming flow at the sink.

Proof: Consider the total outgoing flow at all vertices, $\sum_{u \in V} \sum_{v \in V} f(u, v)$ . This is zero by skew symmetry. Explicitly:

\sum_{u \in V} \sum_{v \in V} f(u, v)

= \sum_{u \in V} \sum_{v \in V} \frac{1}{2} (f(u, v) + f(u, v))

= \sum_{u \in V} \sum_{v \in V} \frac{1}{2} (f(u, v) - f(v, u))

= \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v) - \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(v, u)

= \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v) - \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v)

= 0

where, between the third-to-last and second-to-last lines, we have relabelled the dummy variables $u$ and $v$ in the second term and exchanged the order of summation.

We now rewrite the original sum as $\sum_{u \in V-\{s, t\}} \sum_{v \in V} f(u, v) + \sum_{v \in V} f(s, v) + \sum_{v \in V} f(t, v)$ . The first term is zero, by the conservation constraint. The entire expression also equals zero. Therefore $\sum_{v \in V} f(s, v) = -\sum_{v \in V} f(t, v) = \sum_{v \in V} f(v, t)$ , which is what we wanted. $_\blacksquare$

This common value is called the value of the flow. This is what we wish to maximize in the maximum flow problem.

Algorithms[edit]

There are a variety of algorithms for finding a maximum flow in a flow network. The simplest are the Ford–Fulkerson method and the preflow push algorithms.

Ford–Fulkerson method[edit]

The Ford–Fulkerson method (q.v.) comprises a set of algorithms that each proceed in a series of steps, gradually building up an admissible flow until it has reached its maximum value. Each step of the algorithm takes the previous step's output, an admissible flow, as input, and produces an admissible flow of greater value, until no further refinement is possible. The input for the first step is the empty flow ( $\forall u, v \in V, f(u, v) = 0$ ), which is always admissible. The refinement is done by finding an s-t path in the flow network that can be "added" to the current admissible flow, called an augmenting path. In subsequent stages, we find an augmenting path in the residual network rather than the original network. Once an augmenting path can no longer be found in the residual network, the network is saturated with flow and the algorithm terminates.

There is flexibility in how to choose the augmenting path at each step. A simple approach is to always pick the path with the fewest edges; this gives the Edmonds–Karp algorithm. A faster and more sophisticated approach involves partitioning the graph into level sets by distance from the source and only considering paths in which each edge proceeds from a level to the next. This is called Dinic's algorithm.

Preflow push algorithms[edit]

Preflow push algorithms differ from augmenting path algorithms in that they do not maintain an admissible flow in each step, but instead maintain a preflow, in which the total flow entering a vertex is allowed to exceed the total flow exiting the vertex (but not vice versa). The algorithm begins by generating a preflow in which every edge leaving the source is saturated (so that the source's neighbours all have excess incoming flow). Each step of the algorithm then attempts to discharge some vertex's excess by pushing flow from that vertex to an adjacent vertex. Some flow will be discharged into the sink, and whatever flow cannot be discharged into the sink eventually finds its way back to the source. The algorithm terminates when the intermediate vertices have completely discharged all of their excess incoming flow, and thus an admissible flow has been found.

Other approaches[edit]

The max flow problem may be expressed as a linear program and solved using the techniques of linear programming. Here the vector to be optimized corresponds to the flow $f$ , and has one entry for each edge in the graph. Both the capacity constraints and the balance condition are linear, and may be expressed in the form $A\mathbf{x} \leq \mathbf{b}$ . The value of the flow is also a linear function of the vector $\mathbf{x}$ . Details are left as an exercise for the reader.

Even more sophisticated approaches were given by King, Rao, and Tarjan (1994) and Orlin (2012). Combining the two approaches gives a lower bound of $O(VE)$ on the general max flow problem, the best known to date.

Minimum s-t cut problem[edit]

Given a directed graph with two special nodes, the source s (with all edges outgoing) and the sink t (with all edges incoming), we can define an s-t cut as a subset of edges that, when removed from the graph, leave the sink unreachable from the source. For example, if there is no path from the source to the sink in the original graph, then the empty set is a valid s-t cut (as are all other subsets of $E$ ).

If the graph is weighted, then we may ask for a minimum s-t cut, that is, an s-t cut whose total weight (sum of the weights of the edges it comprises) is as small as possible. We will refer to such a graph as a weighted s-t graph and represent it as $(V, E, s, t, w)$ with $w:E \to [0, \infty)$ representing the edge weights. Negative-weight edges are not allowed for simplicity, but it is easy to handle them: it is always better to cut them than not to cut them, so we remove them from the graph immediately.

A common analogy is bombing enemy supply lines. Here, there is a set of one-way roads (edges) and warehouses (vertices) used to transport materials from some factory (the source) to the front lines (the sink). Each road has a certain cost to bomb (its weight), and we want to bomb enough roads to disconnect the factory from the front lines, while minimizing total cost.

For any weighted s-t graph $(V, E, s, t, w)$ , there is a corresponding flow network $(V, s, t, c)$ with the same structure. Here, $c(u, v) = w((u, v))$ if $(u, v) \in E$ , otherwise $c(u, v) = 0$ . In other words, the capacity between two vertices in the flow network is just the weight of the edge between them in the weighted s-t graph, or zero if there is no such edge.

A famous result known as the max-flow min-cut theorem demonstrates the equivalence of the maximum flow and minimum s-t cut problems. The theorem tells us that the value of a max flow in a flow network equals the total weight of a min cut in the corresponding weighted s-t graph. Because of this, there is no need to devise separate algorithms for the max flow and minimum s-t cut problems. Constructing a min cut from a max flow is straightforward and is based on the proof of the theorem. On the other hand, a max flow cannot be straightforwardly constructed from a min cut.

Variations[edit]

One or more edges in a flow network may be uncapacitated. Such an edge has unlimited capacity. We can usually handle such edges by setting their capacity to a very large value, greater than the sum of capacities of all capacitated edges in the graph. An uncapacitated edge in a flow network corresponds to an uncuttable edge in a weighted s-t graph.

Sometimes we may have to deal with a variation of a flow network in which there may be multiple sources or multiple sinks. This can be handled by adding a new "supersource" with an uncapacitated edge to each of the original sources. Likewise, we can add a new "supersink" with an uncapacitated edge from each of the original sinks.

A flow network in which there are multiple edges between a given pair of vertices can be handled by replacing the multiple edges by a single edge whose capacity equals the sum of the capacities of the original edges.

The maximum flow problem is easily solved when there are vertex capacities in addition to edge capacities. A vertex capacity $c(v)$ is the constraint that $\sum_{u \in V} \max(f(u, v), 0) \leq c(v)$ ; in other words, the total amount of incoming positive flow (or, equivalently, outgoing positive flow) cannot exceed the capacity. We can always reduce a network with vertex capacities to a network with only edge capacities and hence solve the problem using any standard max flow algorithm on the result of the reduction. To do so, we split each vertex $v$ into an "incoming vertex" $v_i$ and an "outgoing vertex" $v_o$ . Every edge $(u, v)$ in the original network is mapped to the edge $(u_o, v_i)$ in the new network (i.e., an edge leaving the outgoing vertex of $u$ and entering the incoming vertex of $v$ ) of the same capacity. Furthermore, we add an edge from $v_i$ to $v_o$ whose capacity equals the original vertex capacity $c(v)$ . In such a way, all flow that would have gone through $v$ in the original graph must now enter through $v_i$ and exit through $v_o$ , going through the edge $(v_i, v_o)$ ; a constraint on this edge therefore yields the desired result, effectively a constraint on the original vertex.

We can likewise consider the minimum s-t cut problem in which we are allowed to remove vertices (for a cost) as well as edges. The reduction is analogous: we split each vertex into an incoming vertex and an outgoing vertex, with an edge from the incoming vertex to the outgoing vertex whose weight equals the original vertex cost.

Applications[edit]

TODO

@@ Line 7: / Line 7: @@
 # 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.
-We may describe a flow network mathematically as a tuple <math>(V, E, c)</math> where <math>c:E \to [0, \infty)</math> and <math>\forall e, e \not\rightarrow s \wedge e \not\leftarrow t</math>. Here <math>c(e)</math> is the capacity of the edge <math>e</math>. <math>e \leftarrow v</math> denotes that edge <math>e</math> leaves vertex <math>v</math>, and <math>e \rightarrow v</math> denotes that edge <math>e</math> enters vertex <math>v</math>.
+We may describe a flow network mathematically as a tuple <math>(V, s, t, c)</math> where <math>s, t \in V</math>, <math>c:V \times V \to [0, \infty)</math>, and <math>\forall v, c(v, s) = c(t, v) = 0</math>. Here <math>c(u, v)</math> is the capacity of the edge from <math>u</math> to <math>v</math>. When we talk about an ''edge'' in a flow network, we are talking about an ordered pair of vertices <math>(u, v)</math> for which <math>c(u, v) > 0</math>. That is, we say that an edge exists from <math>u</math> to <math>v</math> if and only if <math>c(u, v) > 0</math>.
 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.
 ==Admissible flows==
-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.
+In order to state the maximum flow problem, we must first define the concept of an ''admissible flow''. We have a flow network, and this flow network has a capacity function that represents, in some sense, the maximum rate at which flow can occur between a given pair of vertices. An admissible flow is an actual ''choice'' of how much flow to send between each pair of vertices. Of course, this cannot exceed the capacity. Furthermore, sending <math>x</math> units of flow from vertex <math>u</math> to vertex <math>v</math> is equivalent to sending <math>-x</math> units of flow from vertex <math>v</math> to vertex <math>u</math>. Finally, flow is not allowed to "accumulate" at a vertex; the amount flowing in must equal the amount flowing out.
-Mathematically, an admissible flow is a function <math>f: E \to [0, \infty)</math> such that <math>\forall v \in V-\{s, t\}, \sum_{e \rightarrow v} f(e) = \sum_{e \leftarrow v} f(e)</math>. Here, <math>f(e)</math> is the flow along edge <math>e</math>.
+Mathematically, an admissible flow is a function <math>f: V \times V \to \mathbb{R}</math> such that:
+# ''Capacity constraint'': <math>\forall u, v \in V \times V, f(u, v) \leq c(u, v)</math>.
+# ''Skew symmetry'': <math>\forall u, v \in V, f(u, v) = -f(v, u)</math>.
+# ''Conservation of flow'': <math>\forall u \in V, \sum_{v \in V} f(u, v) = 0</math>.
-Some authors, instead of requiring that <math>f(e) \geq 0</math>, use the convention that every edge <math>(u, v)</math> must have a back edge <math>(v, u)</math>, and that the flow along an edge equals the negative of the flow along the back edge. In such a case, the balance condition can be expressed as the requirement that the total incoming flow must be zero at each intermediate vertex, or, equivalently, that the total outgoing flow must be zero. Here "incoming flow" means flow along edges that enter the vertex, even if the flow along such edges is negative.
+Note that the conservation constraint is more naturally translated as <math>\forall u \in V, \sum_{v \in V} f(u, v) = \sum_{v \in V} f(v, u)</math> based on our description above ("the amount flowing in must equal the amount flowing out"). However, as a consequence of the skew symmetry constraint, <math>\sum_{v \in V} f(v, u) = \sum_{v \in V} -f(u, v) = -\sum_{v \in V} f(u, v)</math>. If this is to equal <math>\sum_{v \in V} f(u, v)</math>, then this quantity must be identically zero.
+An edge <math>(u, v)</math> and its reverse edge <math>(v, u)</math> may have different capacities. For example, if <math>c(u, v) = 5</math> and <math>c(v, u) = 3</math>, then we can, for example, send 4 units of flow from <math>u</math> to <math>v</math> and -4 units from <math>v</math> to <math>u</math>. (Negative flow always satisfies a capacity constraint.) We cannot send 4 units of flow from <math>v</math> to <math>u</math> and -4 units from <math>u</math> to <math>v</math>, however, because <math>4 > 3 = c(v, u)</math>. If positive flow goes from <math>v</math> to <math>u</math>, we can only send up to 3 units. We also cannot send 5 units from <math>u</math> to <math>v</math> and 3 units from <math>v</math> to <math>u</math>, because this violates skew symmetry.
+In the remainder of this article, ''flow'' will mean ''admissible flow'' when the context is appropriate.
-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.
 ===Analogies===
 * 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.
+* 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. In this analogy, the role of skew symmetry is clearer. In circuit analysis, sending a positive current from one node to another is equivalent to sending the same amount of negative current in the other direction.
+===Residual network===
+Given a flow network <math>(V, s, t, c)</math> and a flow <math>f</math>, we may form the ''residual capacity network'' or simply ''residual network'' <math>(V, s, t, r)</math>. This is a new flow network in which <math>r(u, v) = c(u, v) - f(u, v)</math>. Because <math>c(u, v) - f(u, v) \geq 0</math> for any valid flow, <math>r</math> is a valid capacity function (takes on nonnegative values only). The residual network may contain edges that the original network does not. In particular, if <math>c(u, v) > 0</math> and <math>c(v, u) = 0</math>, and we send flow from <math>u</math> to <math>v</math> in <math>f</math>, that is, <math>f(u, v) > 0</math>, then <math>r(v, u) = c(v, u) - f(v, u) = 0 + f(u, v) > 0</math>. In other words, sending flow in one direction between two vertices can generate a ''back edge'' in the residual network. If a reverse edge already existed, then sending flow along the forward edge causes the capacity of the reverse edge to increase in the residual network.
+The residual network tells us how much capacity is ''left'' in the original flow network after we've already sent some flow through it. The appearance of back edges corresponds to the fact that we are now allowed to send flow in the other direction to cancel out the existing flow. For example, if <math>c(u, v) = 8</math> and <math>c(v, u) = 0</math>, and <math>f(u, v) = 6</math>, then <math>r(u, v) = 2</math> and <math>r(v, u) = 6</math>. We can send further flow of up to 2 units in the <math>u</math> to <math>v</math> direction, or we can send flow from <math>v</math> to  <math>u</math> of up to 6 units. As long as we do not send more than 6 units in the <math>v</math> to <math>u</math> direction, this will just cancel out the existing flow and the total flow from <math>v</math> to <math>u</math> will still be less than or equal to zero, which makes the flow valid for the original network.
 ==Statement of the problem==
@@ Line 28: / Line 39: @@
 '''Proposition''': The total outgoing flow at the source equals the total incoming flow at the sink.
-'''Proof''': <math>\sum_{e \in E} f(e) = \sum_{v \in V} \sum_{e \rightarrow v} f(e) = \sum_{v \in V} \sum_{e \leftarrow v} f(e)</math>. These equalities are obvious because each edge enters exactly one vertex and exits exactly one vertex. Subtracting, we obtain that <math>\sum_{v \in V} \left( \sum_{e \rightarrow v} f(e) - \sum_{e \leftarrow v} f(e) \right) = 0</math>. We can break this sum down as <math>\sum_{e \leftarrow s} f(e) - \sum_{e \rightarrow t} f(e) + \sum_{v \in V-\{s, t\}} \left( \sum_{e \rightarrow v} f(e) - \sum_{e \leftarrow v} f(e) \right)</math>. The third term here is zero due to the balance condition, so we conclude <math>\sum_{e \leftarrow s} f(e) = \sum_{e \rightarrow t} f(e)</math>. We may call this quantity the total flow, <math>F</math>. This is the quantity we wish to maximize.
+'''Proof''': Consider the total outgoing flow at all vertices, <math>\sum_{u \in V} \sum_{v \in V} f(u, v)</math>. This is zero by skew symmetry. Explicitly:
+:<math>\sum_{u \in V} \sum_{v \in V} f(u, v)</math>
+:<math>= \sum_{u \in V} \sum_{v \in V} \frac{1}{2} (f(u, v) + f(u, v))</math>
+:<math>= \sum_{u \in V} \sum_{v \in V} \frac{1}{2} (f(u, v) - f(v, u))</math>
+:<math>= \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v) - \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(v, u)</math>
+:<math>= \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v) - \frac{1}{2} \sum_{u \in V} \sum_{v \in V} f(u, v)</math>
+:<math>= 0</math>
+where, between the third-to-last and second-to-last lines, we have relabelled the dummy variables <math>u</math> and <math>v</math> in the second term and exchanged the order of summation.
+We now rewrite the original sum as <math>\sum_{u \in V-\{s, t\}} \sum_{v \in V} f(u, v) + \sum_{v \in V} f(s, v) + \sum_{v \in V} f(t, v)</math>. The first term is zero, by the conservation constraint. The entire expression also equals zero. Therefore <math>\sum_{v \in V} f(s, v) = -\sum_{v \in V} f(t, v) = \sum_{v \in V} f(v, t)</math>, which is what we wanted. <math>_\blacksquare</math>
+This common value is called the ''value'' of the flow. This is what we wish to maximize in the maximum flow problem.
 ==Algorithms==
@@ Line 34: / Line 56: @@
 ===Ford–Fulkerson method===
-The [[Ford–Fulkerson method]] (q.v.) comprises a set of algorithms that each proceed in a series of steps, gradually building up an admissible flow until it has reached its maximum value. Each step of the algorithm takes the previous step's output, an admissible flow, as input, and produces an admissible flow of greater value, until no further refinement is possible. The input for the first step is the empty flow (<math>\forall e, f(e) = 0</math>), which is always admissible. The refinement is done by finding an ''s''-''t'' path in the flow network that can be "added" to the current admissible flow, called an ''augmenting path''. After performing this addition, the flow network has to be modified with back edges in case we wish to decrease the flow along an edge in a subsequent step of the algorithm.
+The [[Ford–Fulkerson method]] (q.v.) comprises a set of algorithms that each proceed in a series of steps, gradually building up an admissible flow until it has reached its maximum value. Each step of the algorithm takes the previous step's output, an admissible flow, as input, and produces an admissible flow of greater value, until no further refinement is possible. The input for the first step is the empty flow (<math>\forall u, v \in V, f(u, v) = 0</math>), which is always admissible. The refinement is done by finding an ''s''-''t'' path in the flow network that can be "added" to the current admissible flow, called an ''augmenting path''. In subsequent stages, we find an augmenting path in the ''residual'' network rather than the original network. Once an augmenting path can no longer be found in the residual network, the network is saturated with flow and the algorithm terminates.
 There is flexibility in how to choose the augmenting path at each step. A simple approach is to always pick the path with the fewest edges; this gives the [[Edmonds–Karp algorithm]]. A faster and more sophisticated approach involves partitioning the graph into level sets by distance from the source and only considering paths in which each edge proceeds from a level to the next. This is called [[Dinic's algorithm]].
@@ Line 45: / Line 67: @@
 Even more sophisticated approaches were given by King, Rao, and Tarjan (1994) and Orlin (2012). Combining the two approaches gives a lower bound of <math>O(VE)</math> on the general max flow problem, the best known to date.
+==Minimum s-t cut problem==
+Given a directed graph with two special nodes, the source ''s'' (with all edges outgoing) and the sink ''t'' (with all edges incoming), we can define an ''s-t cut'' as a subset of edges that, when removed from the graph, leave the sink unreachable from the source. For example, if there is no path from the source to the sink in the original graph, then the empty set is a valid s-t cut (as are all other subsets of <math>E</math>).
+If the graph is weighted, then we may ask for a '''minimum s-t cut''', that is, an s-t cut whose total weight (sum of the weights of the edges it comprises) is as small as possible. We will refer to such a graph as a ''weighted s-t graph'' and represent it as <math>(V, E, s, t, w)</math> with <math>w:E \to [0, \infty)</math> representing the edge weights. Negative-weight edges are not allowed for simplicity, but it is easy to handle them: it is always better to cut them than not to cut them, so we remove them from the graph immediately.
+A common analogy is bombing enemy supply lines. Here, there is a set of one-way roads (edges) and warehouses (vertices) used to transport materials from some factory (the source) to the front lines (the sink). Each road has a certain cost to bomb (its weight), and we want to bomb enough roads to disconnect the factory from the front lines, while minimizing total cost.
+For any weighted s-t graph <math>(V, E, s, t, w)</math>, there is a corresponding flow network <math>(V, s, t, c)</math> with the same structure. Here, <math>c(u, v) = w((u, v))</math> if <math>(u, v) \in E</math>, otherwise <math>c(u, v) = 0</math>. In other words, the capacity between two vertices in the flow network is just the weight of the edge between them in the weighted s-t graph, or zero if there is no such edge.
+A famous result known as the [[max-flow min-cut theorem]] demonstrates the equivalence of the maximum flow and minimum s-t cut problems. The theorem tells us that the value of a max flow in a flow network equals the total weight of a min cut in the corresponding weighted s-t graph. Because of this, there is no need to devise separate algorithms for the max flow and minimum s-t cut problems. Constructing a min cut from a max flow is straightforward and is based on the proof of the theorem. On the other hand, a max flow cannot be straightforwardly constructed from a min cut.
+==Variations==
+One or more edges in a flow network may be ''uncapacitated''. Such an edge has unlimited capacity. We can usually handle such edges by setting their capacity to a very large value, greater than the sum of capacities of all capacitated edges in the graph. An uncapacitated edge in a flow network corresponds to an uncuttable edge in a weighted s-t graph.
+Sometimes we may have to deal with a variation of a flow network in which there may be multiple sources or multiple sinks. This can be handled by adding a new "supersource" with an uncapacitated edge to each of the original sources. Likewise, we can add a new "supersink" with an uncapacitated edge from each of the original sinks.
+A flow network in which there are multiple edges between a given pair of vertices can be handled by replacing the multiple edges by a single edge whose capacity equals the sum of the capacities of the original edges.
+The maximum flow problem is easily solved when there are ''vertex capacities'' in addition to edge capacities. A vertex capacity <math>c(v)</math> is the constraint that <math>\sum_{u \in V} \max(f(u, v), 0) \leq c(v)</math>; in other words, the total amount of incoming positive flow (or, equivalently, outgoing positive flow) cannot exceed the capacity. We can always reduce a network with vertex capacities to a network with only edge capacities and hence solve the problem using any standard max flow algorithm on the result of the reduction. To do so, we split each vertex <math>v</math> into an "incoming vertex" <math>v_i</math> and an "outgoing vertex" <math>v_o</math>. Every edge <math>(u, v)</math> in the original network is mapped to the edge <math>(u_o, v_i)</math> in the new network (''i.e.'', an edge leaving the outgoing vertex of <math>u</math> and entering the incoming vertex of <math>v</math>) of the same capacity. Furthermore, we add an edge from <math>v_i</math> to <math>v_o</math> whose capacity equals the original vertex capacity <math>c(v)</math>. In such a way, all flow that would have gone through <math>v</math> in the original graph must now enter through <math>v_i</math> and exit through <math>v_o</math>, going through the edge <math>(v_i, v_o)</math>; a constraint on this edge therefore yields the desired result, effectively a constraint on the original vertex.
+We can likewise consider the minimum s-t cut problem in which we are allowed to remove vertices (for a cost) as well as edges. The reduction is analogous: we split each vertex into an incoming vertex and an outgoing vertex, with an edge from the incoming vertex to the outgoing vertex whose weight equals the original vertex cost.
+==Applications==
+TODO

Difference between revisions of "Maximum flow"

Latest revision as of 03:22, 9 September 2013

Contents

The flow network[edit]

Admissible flows[edit]

Analogies[edit]

Residual network[edit]

Statement of the problem[edit]

Algorithms[edit]

Ford–Fulkerson method[edit]

Preflow push algorithms[edit]

Other approaches[edit]

Minimum s-t cut problem[edit]

Variations[edit]

Applications[edit]

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools