Max-flöde, minsta-snitt
Utseende
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.[1]
Linjärprogramformulering
[redigera | redigera wikitext]Max-flöde och minsta-snitt kan formuleras som två linjärprogram som är dualer till varandra[2]:
Max-flöde |
Minsta-snitt | ||
---|---|---|---|
|
| ||
under villkoren |
under villkoren | ||
|
|
|
|
anger flödet mellan och |
anger om nod är kopplad till eller anger om bågen mellan och är avskuren |
Referenser
[redigera | redigera wikitext]- 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