Visa källa för Max-flöde, minsta-snitt

Satsen om '''max-flöde, minsta-snitt''' säger att för en given viktad [[Graf (grafteori)|graf]] är det största möjliga flödet mellan två noder lika med det minsta möjliga [[Snitt (grafteori)|snitt]] som separerar dessa två noder. Satsen är av stor vikt inom [[optimeringslära]] och har praktiska [[tillämpninga]]r inom till exempel [[bildanalys]] och [[datorseende]].<ref>Boykov 1998,2001</ref>

==Linjärprogramformulering==
Max-flöde och minsta-snitt kan formuleras som två [[linjärprogram]] som är [[dual (optimering)|dualer]] till varandra<ref>Papadimitriou 1998</ref>:

{| border="0" rules="" cellspacing="0" cellpadding="0"
! colspan="2" style="border: 1px solid darkgrey;"|
Max-flöde 
! colspan="2" style="border-top: 1px solid darkgrey; border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey;"|
Minsta-snitt 
|-
| colspan="2" valign="top" align="left" style="border-right: 1px solid darkgrey; border-left: 1px solid darkgrey; padding-right: 1em;"|
:maximera  <math>|f|\,</math>
| colspan="2" valign="top" align="left" style="border-right: 1px solid darkgrey; padding-right: 1em;"|
:minimera  <math>\sum_{(i,j)\in E} c_{ij} d_{ij} </math>
|-
| colspan="2" style="border-left: 1px solid black;" style="border-right: 1px solid darkgrey; border-left: 1px solid darkgrey; padding-left: 1em;"|
under villkoren
| colspan="2" style="border-left: 1px solid black;" style="border-right: 1px solid darkgrey; padding-left: 1em;"|
under villkoren
|-
| width="180px" valign="top" align="right" style="border-bottom: 1px solid darkgrey; border-left: 1px solid darkgrey;"|
: <math>f_{ij} \le c_{ij}</math>
:<math>\sum_{ j:\,\,(j,i)\in E} f_{ji} - \sum_{j:\,\, (i,j)\in E} f_{ij} \le 0,</math>

:<math>f_{ij} \ge 0</math>
| width="80px" valign="top" align="right" style="border-right: 1px solid darkgrey; border-bottom: 1px solid darkgrey; padding-right: 1em;"|
: <math>(i,j) \in E</math>
: <math>i \in V</math>
| width="180px" valign="top" align="right" style="border-bottom: 1px solid darkgrey;"|
:<math>d_{ij} + x_i - x_j \ge 0</math>
: <math>x_s = 0 \,</math>
: <math>x_t = 1 \,</math>
: <math>d_{ij} \ge 0</math> 
| width="80px" valign="top" align="right" style="border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey; padding-right: 1em;"|
: <math>(i,j) \in E</math>
: &nbsp;
: &nbsp;
: <math>(i,j) \in E</math>
|-
|  colspan="2" style="border: 1px solid darkgrey; padding-left: 1em;"|
<math>f_{ij}</math> anger flödet mellan <math>i</math> och <math>j</math>
| colspan="2" style="border-top: 1px solid darkgrey; border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey; padding-left: 1em;"|
<math>x_{i}</math> anger om nod <math>i</math> är kopplad till <math>s</math> eller <math>t</math>

<math>d_{ij}</math> anger om bågen mellan <math>i</math> och <math>j</math> är avskuren
|}

==Referenser==
*Y. Boykov, O. Veksler and R. Zabih (1998),  "[http://www.cs.cornell.edu/~rdz/Papers/BVZ-cvpr98.pdf Markov Random Fields with Efficient Approximations]", ''International Conference on Computer Vision and Pattern Recognition (CVPR)''.
*Y. Boykov, O. Veksler and R. Zabih (2001), "[http://www.cs.cornell.edu/~rdz/Papers/BVZ-pami01-final.pdf Fast approximate energy minimisation via graph cuts]", ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', '''29''', 1222–1239.
* {{Bokref |författare = Christos H. Papadimitriou, Kenneth Steiglitz |titel = Combinatorial Optimization: Algorithms and Complexity |kapitel = 6.1 The Max-Flow, Min-Cut Theorem |år = 1998 |utgivare = Dover |isbn = 0486402584 |sid = 120-128}}

==Noter==
<references />

[[Kategori:Grafteori]]
[[Kategori:Kombinatorik]]