Max-flöde, minsta-snitt

Satsen om max-flöde, minsta-snitt säger att för en given viktad graf är det största möjliga flödet mellan två noder lika med det minsta möjliga snitt som separerar dessa två noder. Satsen är av stor vikt inom optimeringslära och har praktiska tillämpningar inom till exempel bildanalys och datorseende.

Linjärprogramformulering

Max-flöde och minsta-snitt kan formuleras som två linjärprogram som är dualer till varandra:

Max-flöde		Minsta-snitt
maximera $|f|\,$		minimera $\sum_{(i,j)\in E} c_{ij} d_{ij}$
under villkoren		under villkoren
$f_{ij} \le c_{ij}$ $\sum_{ j:\,\,(j,i)\in E} f_{ji} - \sum_{j:\,\, (i,j)\in E} f_{ij} \le 0,$ $f_{ij} \ge 0$	$(i,j) \in E$ $i \in V$	$d_{ij} + x_i - x_j \ge 0$ $x_s = 0 \,$ $x_t = 1 \,$ $d_{ij} \ge 0$	$(i,j) \in E$     $(i,j) \in E$
$f_{ij}$ anger flödet mellan $i$ och $j$		$x_{i}$ anger om nod $i$ är kopplad till $s$ eller $t$ $d_{ij}$ anger om bågen mellan $i$ och $j$ är avskuren

Referenser

• Y. Boykov, O. Veksler and R. Zabih (1998), "Markov Random Fields with Efficient Approximations", International Conference on Computer Vision and Pattern Recognition (CVPR).
• Y. Boykov, O. Veksler and R. Zabih (2001), "Fast approximate energy minimisation via graph cuts", IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 1222–1239.
• Christos H. Papadimitriou, Kenneth Steiglitz (1998). ”6.1 The Max-Flow, Min-Cut Theorem”. Combinatorial Optimization: Algorithms and Complexity. Dover. sid. 120-128. ISBN 0486402584