Max-flöde, minsta-snitt

Från Wikipedia
Hoppa till: navigering, sök

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

maximera
minimera

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]

Noter[redigera | redigera wikitext]

  1. ^ Boykov 1998,2001
  2. ^ Papadimitriou 1998