FACTOID # 13: New York has America's lowest percentage of residents who are veterans.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Max flow min cut theorem

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.

Contents


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 s in S and t in T. Hence there are 2 | V | − 2 possible cuts in a graph. The capacity of a cut (S,T) is c(S,T) = sum_{u in S, v in T} c(u,v), the sum of the capacity of all the edges crossing the cut.


The following three conditions are equivalent:

  1. f is a maximum flow in G
  2. The residual network Gf contains no augmenting paths.
  3. | 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.
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 Gf, there is an edge (r,q) with capacity cf(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


 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m