The **max flow min cut theorem** is a statement in optimization theory about maximal flows in flow networks. It states that: In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) â‰¤ f(x) for all x in A (minimization) or such that...
The max flow min cut theorem is a statement in optimization theory about optimal flows in networks. ...
In graph theory, a network flow is an assignment of values to edges of a weighted directed graph (called a flow network in this case), such that: 1. ...
*The maximal amount of a flow is equal to the capacity of a minimal cut.*
## Definition
Suppose *G*(*V*,*E*) is a finite directed graph and every edge (*u*,*v*) has a capacity *c*(*u*,*v*) (a non-negative real number). Further assume two vertices, the source *s* and the sink *t*, have been distinguished. This article just presents the basic definitions. ...
This article just presents the basic definitions. ...
In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite lineâ€”the number line. ...
A **cut** is a split of the nodes into two sets *S* and *T*, such that and . Hence there are 2 ^{| V | − 2} possible cuts in a graph. The capacity of a cut (*S*,*T*) is , the sum of the capacity of all the edges crossing the cut. The following three conditions are equivalent: *f* is a maximum flow in *G* - The residual network
*G*_{f} contains no augmenting paths. - |
*f* | = *c*(*S*,*T*) for some cut (*S*,*T*). If there is an augmenting path, we can send flow along it, and get i greater flow, hence it cannot be maximal, and vice versa. If there is no augmenting path, divide the graph into *S*, the nodes reachable from *s* in the residual network, and *T*, those not reachable. Then *c*(*S*,*T*) must be 0. If it is not, there is an edge (*u*,*v*) with *c*(*u*,*v*) > 0. But then *v* is reachable from *s*, and cannot be in *T*. The max flow min cut theorem is a statement in optimization theory about optimal flows in networks. ...
In graph theory, a network flow is an assignment of values to edges of a weighted directed graph (called a flow network in this case), such that: 1. ...
In graph theory, a network flow is an assignment of values to edges of a weighted directed graph (called a flow network in this case), such that: 1. ...
In graph theory, a network flow is an assignment of values to edges of a weighted directed graph (called a flow network in this case), such that: 1. ...
## Example
A network with maximal flow, and three minimal cuts. Given to the right is a network with nodes *V* = {*s*,*o*,*p*,*q*,*r*,*t*}, and a total flow from the source *s* to the sink *t* of 5, which is maximal in this network. (This is actually the only maximal flow you can assign in this network.) Image File history File links Min_cut. ...
There are three minimal cuts in this network. For the cut *S* = {*s*,*p*},*T* = {*o*,*q*,*r*,*t*}, the capacity accross the cut is *c*(*s*,*o*) + *c*(*p*,*r*) = 3 + 2 = 5. For *S* = {*s*,*o*,*p*},*T* = {*q*,*r*,*t*} it is *c*(*o*,*q*) + *c*(*p*,*r*) = 3 + 2 = 5. For *S* = {*s*,*o*,*p*,*q*,*r*},*T* = {*t*} it is *c*(*q*,*t*) + *c*(*r*,*t*) = 2 + 3 = 5. Notice that *S* = {*s*,*o*,*p*,*r*},*T* = {*q*,*t*} is not a minimal cut, even though both (*o*,*q*) and (*r*,*t*) are saturated in the given flow. This is because in the residual network *G*_{f}, there is an edge (r,q) with capacity *c*_{f}(*r*,*q*) = *c*(*r*,*q*) − *f*(*r*,*q*) = 0 − ( − 1) = 1. In graph theory, a network flow is an assignment of values to edges of a weighted directed graph (called a flow network in this case), such that: 1. ...
## History The theorem was proved by P. Elias, A. Feinstein, and C.E. Shannon in 1956, and independently also by L.R. Ford, Jr. and D.R. Fulkerson in the same year. Determining maximum flows is a special kind of linear programming problem, and the max flow min cut theorem can be seen as a special case of the duality theorem for linear programming. ...
1956 (MCMLVI) was a leap year starting on Sunday of the Gregorian calendar. ...
Lester Randolph Ford, Sr. ...
Delbert Ray Fulkerson (August 14, 1924 - January 10, 1976) was a mathematician who co-developed the Ford-Fulkerson algorithm. ...
In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ...
In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ...
## External links A review of current literature on computing maximum flows
## References - P. Elias, A. Feinstein, and C. E. Shannon. Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117--119, 1956.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
*Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 26: Maximum Flow, pp.643–700. |