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.Boykov 1998,2001
Linjärprogramformulering Max-flöde och minsta-snitt kan formuleras som två linjärprogram som är dualer till varandraPapadimitriou 1998:
Max-flöde Minsta-snitt maximera minimera under villkorenunder villkoren
anger flödet mellan och anger om nod är kopplad till eller
anger om bågen mellan och ä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.
Noter
Kategori:Grafteori Kategori:Kombinatorik