Teorema de flux màxim tall mínim

En optimització i teoria de grafs, el teorema de flux màxim tall mínim postula que en una xarxa de flux, la quantitat màxima de flux que pot passar d'una font fins a un pou és igual a la capacitat mínima que necessitem treure-li a la xarxa perquè no pugui passar més flux de la font al pou.

El teorema de flux màxim tall mínim és un cas especial del teorema de dualitat i pot derivar-se en el teorema de Menger i el teorema de König-Egerváry.

Definició matemàtica

Sigui N = ( V , E ) {\displaystyle N=(V,E)} una xarxa (graf dirigit), i s {\displaystyle s} i t {\displaystyle t} la font i el pou d' N {\displaystyle N} respectivament.

La capacitat d'una aresta és c: E→R+, denominada com cuv o c(u,v). Representa la quantitat màxima de flux que pot passar a través d'una aresta.
El flux és f: E→R+, denominat com fuv o f(u,v), i subjecte a les següents dos restriccions:
  1. f u v ≤ c u v {\displaystyle f_{uv}\leq c_{uv}} per cada ( u , v ) ∈ E {\displaystyle (u,v)\in E} (restricció de capacitat).
  2. ∑ u : ( u , v ) ∈ E f u v = ∑ u : ( v , u ) ∈ E f v u {\displaystyle \sum _{u:\,\,(u,v)\in E}f_{uv}=\sum _{u:\,\,(v,u)\in E}f_{vu}} per cada v ∈ V ∖ { s , t } {\displaystyle v\in V\setminus \{s,t\}} (conservació de flux).

El valor del flux és definit per | f | = Σv∈Vfsv-Σv∈Vfvs, on s és la font de N. Representa la quantitat de flux que passa de la font al pou.

El problema de flux màxim pretén maximitzar |f|, és a dir, enviar tant de flux com sigui possible des de s fins t.

Un tall s-t C = ( S , T ) {\displaystyle C=(S,T)} és un tall en que s∈S i t∈T. El conjunt de tall de C és el conjunt {(u,v)∈E | u∈S, v∈T}. Si les arestes del conjunt de tall són eliminades, |f| = 0.

La capacitat d'un tall s-t és definida per c(S,T) = Σ(u,v)∈(S,T) cuv.

El problema del tall mínim pretén minimitzar c(S,T), és a dir, minimitzar la capacitat del tall s-t.

Postulat

El teorema de flux màxim tall mínim postula

El valor màxim d'un flux s-t és igual a la capacitat del tall s-t mínim.

Exemple

Xarxa amb els valor òptims

La figura de la dreta és una xarxa com a valor de flux 7. El vèrtex en blanc i els vèrtexs en gris pertanyen als subconjunts S i T d'un tall s-t, el conjunt de tall del qual conté les arestes discontínues. La capacitat del tall s-t és 7, com també el valor del flux. El teorema de flux màxim tall mínim ens diu que el valor del flux i la capacitat del tall s-t són ambdós òptims en aquesta xarxa.

Història

El teorema de flux màxim tall mínim va ser provat per P. Elias, A. Feinstein i C.E. Shannon el 1956, i independentment per L.R. Ford i D.R. Fulkerson el mateix any.

Vegeu també