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 un pou és igual a la capacitat mínima que necessitem treure-li a la xarxa per que 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.
Taula de continguts |
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).
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 d'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.
és un 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 capcitat 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 ambdos ò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.
