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
[modifica]Sigui una xarxa (graf dirigit), i i la font i el pou d' 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:
- per cada (restricció de capacitat).
- per cada (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 é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
[modifica]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
[modifica]
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
[modifica]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.