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 |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[redigera | redigera wikitext]

Noter[redigera | redigera wikitext]

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