Max-flöde, minsta-snitt

maximera ${\displaystyle |f|\,}$

minimera ${\displaystyle \sum _{(i,j)\in E}c_{ij}d_{ij}}$

under villkoren

under villkoren

${\displaystyle f_{ij}\leq c_{ij}}$

${\displaystyle \sum _{j:\,\,(j,i)\in E}f_{ji}-\sum _{j:\,\,(i,j)\in E}f_{ij}\leq 0,}$

${\displaystyle f_{ij}\geq 0}$

${\displaystyle (i,j)\in E}$

${\displaystyle i\in V}$

${\displaystyle d_{ij}+x_{i}-x_{j}\geq 0}$

${\displaystyle x_{s}=0\,}$

${\displaystyle x_{t}=1\,}$

${\displaystyle d_{ij}\geq 0}$

${\displaystyle (i,j)\in E}$

 

 

${\displaystyle (i,j)\in E}$

${\displaystyle f_{ij}}$ anger flödet mellan ${\displaystyle i}$ och ${\displaystyle j}$

${\displaystyle x_{i}}$ anger om nod ${\displaystyle i}$ är kopplad till ${\displaystyle s}$ eller ${\displaystyle t}$

${\displaystyle d_{ij}}$ anger om bågen mellan ${\displaystyle i}$ och ${\displaystyle j}$ är avskuren