Max Flow Min Cut Theorem

Information about Max Flow Min Cut Theorem

The max-flow min-cut theorem is a statement in optimization theory about maximum flows in flow networks. It derives from Menger's theorem. It states that:

The maximum amount of flow is equal to the capacity of a minimal cut.

In layman terms, the theorem states that the maximum flow in a network is dictated by its bottleneck. Between any two nodes, the quantity of material flowing from one to the other cannot be greater than the weakest set of links somewhere between the two nodes.

Definition

Suppose $\text{[math]}$ is a finite directed graph and every edge $\text{[math]}$ has a capacity $\text{[math]}$ (a non-negative real number). Further assume two vertices, the source $\text{[math]}$ and the sink $\text{[math]}$ , have been distinguished.

Main article: Cut (graph theory)

A cut is a split of the nodes into two sets $\text{[math]}$ and $\text{[math]}$ , such that $\text{[math]}$ is in $\text{[math]}$ and $\text{[math]}$ is in $\text{[math]}$ . Hence there are

$\text{[math]}$

possible cuts in a graph. The capacity of a cut $\text{[math]}$ is

$\text{[math]}$ ,

the sum of the capacity of all the edges crossing the cut, from the region $\text{[math]}$ to the region $\text{[math]}$ .

The following three conditions are equivalent:

$\text{[math]}$ is a maximum flow in $\text{[math]}$
The residual network $\text{[math]}$ contains no augmenting paths.
$\text{[math]}$ for some cut $\text{[math]}$ .

Proof Sketch: If there is an augmenting path, we can send flow along it, and get a greater flow, hence it cannot be maximal, and vice versa. If there is no augmenting path, divide the graph into $\text{[math]}$ , the nodes reachable from $\text{[math]}$ in the residual network, and $\text{[math]}$ , those not reachable. Then $\text{[math]}$ must be 0. If it is not, there is an edge $\text{[math]}$ with $\text{[math]}$ . But then $\text{[math]}$ is reachable from $\text{[math]}$ , and cannot be in $\text{[math]}$ .

In particular this proves that $\text{[math]}$ , because a minimal cut is smaller or equal to the cut corresponding to our $\text{[math]}$ .

Then we have $\text{[math]}$ . If we have a flow $\text{[math]}$ for a given graph $\text{[math]}$ , removing an edge $\text{[math]}$ of capacity $\text{[math]}$ changes $\text{[math]}$ in at least $\text{[math]}$ , because no more than a capacity of $\text{[math]}$ can be used by the flow $\text{[math]}$ . But if we remove all edges cut by a given minimal cut $\text{[math]}$ , we get a flow $\text{[math]}$ , whatever the flow $\text{[math]}$ we have at first. So $\text{[math]}$ for any flow $\text{[math]}$ , in particular if $\text{[math]}$ is a max flow. Which shows $\text{[math]}$ .

Example

A network with maximal flow, and three minimal cuts.

Given to the right is a network with nodes $\text{[math]}$ , and a total flow from the source $\text{[math]}$ to the sink $\text{[math]}$ of 5, which is maximal in this network. (Incidentally, this is the only maximal flow you can assign to this network.)

There are three minimal cuts in this network:

Cut	Capacity
$\text{[math]}$	$\text{[math]}$
$\text{[math]}$	$\text{[math]}$
$\text{[math]}$	$\text{[math]}$

Notice that $\text{[math]}$ is not a minimal cut, even though both $\text{[math]}$ and $\text{[math]}$ are saturated in the given flow. This is because in the residual network $\text{[math]}$ , there is an edge (r,q) with capacity $\text{[math]}$ .

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.

External links

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 0-262-03293-7. Chapter 26: Maximum Flow, pp.643–700.

In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set.
..... Click the link for more information.

maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum ^[1]. Sometimes it is defined as finding the value of such a flow.
..... Click the link for more information.

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge may not exceed the capacity of the edge.
..... Click the link for more information.

In the mathematical discipline of graph theory and related areas, Menger's theorem is a basic result about connectivity in finite undirected graphs. It was proved for edge-connectivity and for vertex-connectivity by Karl Menger in 1927.
..... Click the link for more information.

In graph theory, a cut is a partition of the vertices of a graph into two sets. More formally, let G(V, E) denote a graph. A cut is a partition of the vertices V into two sets S and T.
..... Click the link for more information.

In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2.4871773339…. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as π and
..... Click the link for more information.

Claude Shannon

Claude Shannon
Born 30 March 1916
Petoskey, Michigan
Died 24 January 2001 (aged 86)
..... Click the link for more information.

19th century - 20th century - 21st century
1920s 1930s 1940s - 1950s - 1960s 1970s 1980s
1953 1954 1955 - 1956 - 1957 1958 1959

Year 1956 (MCMLVI
..... Click the link for more information.

Lester Randolph Ford, Sr. (October 29, 1886 ? - March 7 1975 ?) was an American mathematician, editor of the American Mathematical Monthly from 1942 to 1946, and President of the Mathematical Association of America from 1947 to 1948.
..... Click the link for more information.

Delbert Ray Fulkerson (August 14, 1924 - January 10, 1976) was a mathematician who co-developed the Ford-Fulkerson algorithm, one of the most used algorithms to compute maximal flows in networks.

Fulkerson received his Ph.D. at the University of Wisconsin-Madison in 1951.
..... Click the link for more information.

In mathematics, linear programming (LP) problems involve the optimization of a linear objective function, subject to linear equality and inequality constraints.

Put very informally, LP is about trying to get the best outcome (e.g.
..... Click the link for more information.

In linear programming, the primary problem and the dual problem are complementary. A solution to either one determines a solution to both.

Background

Linear programming problems are optimization problems in which the objective function and the constraints are all
..... Click the link for more information.

The Ford-Fulkerson algorithm (named for L. R. Ford, Jr. and D. R. Fulkerson) computes the maximum flow in a flow network. It was published in 1956. The name Ford-Fulkerson is often also used for the Edmonds-Karp algorithm, which is a specialisation of Ford-Fulkerson.
..... Click the link for more information.

In computer science and graph theory the Karger's algorithm is a Monte Carlo method to compute the minimum cut of a connected graph.

Algorithm

The idea of the algorithm is based on the concept of contraction of an edge in a graph.
..... Click the link for more information.

Claude Shannon

Claude Shannon
Born 30 March 1916
Petoskey, Michigan
Died 24 January 2001 (aged 86)
..... Click the link for more information.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. He is a Full Professor of computer science at Dartmouth College.
..... Click the link for more information.

Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language.
..... Click the link for more information.

..... Click the link for more information.

Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in
..... Click the link for more information.

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities.
..... Click the link for more information.

This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.

Herod_Archelaus

iPedia Free Information Center