Editing Max-flow min-cut theorem (section)

===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}}.