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.
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.
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.
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.
El teorema de flux màxim tall mínim postula
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.
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.