Editing Max-flow min-cut theorem (section)

==Application==

===Cederbaum's maximum flow theorem===
{{See also| Cederbaum's maximum flow theorem}}
The maximum flow problem can be formulated as the maximization of the electrical current through a network composed of nonlinear resistive elements.<ref>{{cite journal|last1=Cederbaum|first1=I.|title=On the optimal operation of communication nets|journal=Journal of the Franklin Institute|date=August 1962|volume=274|issue=2 |pages=130–141|doi=10.1016/0016-0032(62)90401-5 }}</ref> In this formulation, the limit of the current {{math|&thinsp;''I''<sub>in</sub> }} between the input terminals of the electrical network as the input voltage {{math|''V''<sub>in</sub>}} approaches <math>\infty</math>, is equal to the weight of the minimum-weight cut set. 

:<math>\lim_{V_{\text{in}} \to \infty} (I_{in})= \min_{X_C}\sum_{(u,v) \in X_C}c_{uv} </math>

===Generalized max-flow min-cut theorem===
In addition to edge capacity, consider there is capacity at each vertex, that is, a mapping <math>c:V\to\R^+</math> denoted by {{math|''c''(''v'')}}, such that the flow {{math|&thinsp;''f''&thinsp;}} has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint

:<math>\forall v \in V \setminus \{s,t\} : \qquad \sum\nolimits_{\{u\in V\mid (u,v)\in E\}} f_{uv} \le c(v).</math>

In other words, the amount of ''flow'' passing through a vertex cannot exceed its capacity. Define an ''s-t cut'' to be the set of vertices and edges such that for any path from ''s'' to ''t'', the path contains a member of the cut. In this case, the ''capacity of the cut'' is the sum of the capacity of each edge and vertex in it.

In this new definition, the '''generalized max-flow min-cut theorem''' states that the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut in the new sense.

===Menger's theorem===
{{See also| Menger's Theorem}}
In the undirected edge-disjoint paths problem, we are given an undirected graph {{math|''G'' {{=}} (''V'', ''E'')}} and two vertices {{mvar|s}} and {{mvar|t}}, and we have to find the maximum number of edge-disjoint s-t paths in {{mvar|G}}.

'''Menger's theorem''' states that the maximum number of edge-disjoint s-t paths in an undirected graph is equal to the minimum number of edges in an s-t cut-set.

===Project selection problem===
[[File:Max-flow min-cut project-selection.svg|thumb|right|A network formulation of the project selection problem with the optimal solution]]
In the project selection problem, there are {{mvar|n}} projects and {{mvar|m}} machines. Each project {{mvar|p<sub>i</sub>}} yields revenue {{math|''r''(''p<sub>i</sub>'')}} and each machine {{mvar|q<sub>j</sub>}} costs {{math|''c''(''q<sub>j</sub>'')}} to purchase. We want to select a subset of the project, and purchase a subset of the machines, to maximize the total profit (revenue of the selected projects minus cost of the purchased machines). We must obey the following constraint: each project specifies a set of machines which must be purchased if the project is selected. (Each machine, once purchased, can be used by any selected project.)

To solve the problem, let {{mvar|P}} be the set of projects ''not'' selected and {{mvar|Q}} be the set of machines purchased, then the problem can be formulated as,

:<math>\max \{g\} = \sum_{i} r(p_i) - \sum_{p_i \in P} r(p_i) - \sum_{q_j \in Q} c(q_j).</math>

Since the first term does not depend on the choice of {{mvar|P}} and {{mvar|Q}}, this maximization problem can be formulated as a minimization problem instead, that is,

:<math>\min \{g'\} = \sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j).</math>

The above minimization problem can then be formulated as a minimum-cut problem by constructing a network, where the source is connected to the projects with capacity {{math|''r''(''p<sub>i</sub>'')}}, and the sink is connected by the machines with capacity {{math|''c''(''q<sub>j</sub>'')}}. An edge {{math|(''p<sub>i</sub>'', ''q<sub>j</sub>'')}} with ''infinite'' capacity is added if project {{mvar|p<sub>i</sub>}} requires machine {{mvar|q<sub>j</sub>}}. The s-t cut-set represents the projects and machines in {{mvar|P}} and {{mvar|Q}} respectively. By the max-flow min-cut theorem, one can solve the problem as a [[maximum flow problem]].

The figure on the right gives a network formulation of the following project selection problem:

{| class="wikitable" style="text-align:center; width:500px;" border="1"
|-
! width="20px" |
! width="100px" |
Project {{math|''r''(''p<sub>i</sub>'')}}
! width="100px" |
Machine {{math|''c''(''q<sub>j</sub>'')}}
!
|-
! 1
| 100 || 200
| align="left" style="padding-left: 1em;" |
Project 1 requires machines 1 and 2.
|-
! 2
| 200 || 100
| align="left" style="padding-left: 1em;" |
Project 2 requires machine 2.
|-
! 3
| 150 || 50
| align="left" style="padding-left: 1em;" |
Project 3 requires machine 3.
|}

The minimum capacity of an s-t cut is 250 and the sum of the revenue of each project is 450; therefore the maximum profit ''g'' is 450 − 250 = 200, by selecting projects {{math|''p''<sub>2</sub>}} and {{math|''p''<sub>3</sub>}}.

The idea here is to 'flow' each project's profits through the 'pipes' of its machines. If we cannot fill the pipe from a machine, the machine's return is less than its cost, and the min cut algorithm will find it cheaper to cut the project's profit edge instead of the machine's cost edge.

===Image segmentation problem===
{{See also|Maximum flow problem}}
[[File:Image segmentation.jpg|thumb|Each black node denotes a pixel.]]
In the image segmentation problem, there are {{mvar|n}} pixels. Each pixel {{mvar|i}} can be assigned a foreground value {{mvar|&thinsp;f<sub>i</sub>}} or a background value {{mvar|b<sub>i</sub>}}. There is a penalty of {{mvar|p<sub>ij</sub>}} if pixels {{mvar|i, j}} are adjacent and have different assignments. The problem is to assign pixels to foreground or background such that the sum of their values minus the penalties is maximum.

Let {{mvar|P}} be the set of pixels assigned to foreground and {{mvar|Q}} be the set of points assigned to background, then the problem can be formulated as,

: <math>\max \{g\} = \sum_{i \in P} f_i + \sum_{i \in Q} b_i - \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}.</math>

This maximization problem can be formulated as a minimization problem instead, that is,

: <math>\min \{g'\} = \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}.</math>

The above minimization problem can be formulated as a minimum-cut problem by constructing a network where the source (orange node) is connected to all the pixels with capacity {{mvar|&thinsp;f<sub>i</sub>}}, and the sink (purple node) is connected by all the pixels with capacity {{mvar|b<sub>i</sub>}}. Two edges ({{mvar|i, j}}) and ({{mvar|j, i}}) with {{mvar|p<sub>ij</sub>}} capacity are added between two adjacent pixels. The s-t cut-set then represents the pixels assigned to the foreground in {{mvar|P}} and pixels assigned to background in {{mvar|Q}}.