Mostra la font per a Teorema de flux màxim tall mínim

En [[Optimització matemàtica|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 [[Programació lineal#Dualitat|teorema de dualitat]] i pot derivar-se en el [[d:Q928813|teorema de Menger]] i el [[d:Q897769|teorema de König-Egerváry]].

== Definició matemàtica ==
Sigui <math>N = (V, E)</math> una xarxa (graf dirigit), i <math>s</math> i <math>t</math> la font i el pou d'<math>N</math> respectivament.

:La '''capacitat''' d'una aresta és ''c'': ''E''→''R''<sup>+</sup>, denominada com ''c''<sub>uv</sub> 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''<sup>+</sup>, denominat com ''f''<sub>uv</sub> o ''f''(''u'',''v''), i subjecte a les següents dos restriccions:
:# <math>f_{uv} \le c_{uv}</math> per cada <math>(u,v)\in E</math> (restricció de capacitat).
:# <math>\sum_{u:\,\,(u,v)\in E} f_{uv} = \sum_{u:\,\,(v,u)\in E} f_{vu}</math> per cada <math>v \in V\setminus\{s,t\}</math> (conservació de flux).

El '''valor del flux''' és definit per | ''f'' | = Σ<sub>v∈V</sub>''f''<sub>sv</sub>-Σ<sub>v∈V</sub>''f''<sub>vs</sub>, 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''' <math>C=(S,T)</math> és un [[Tall (graf)|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'') = Σ<sub>(u,v)∈(S,T)</sub> ''c''<sub>uv</sub>.

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 ==
[[Fitxer:Max-flow min-cut example.svg|miniatura|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é ==
* [[Tall (graf)]]
* [[Problema del flux màxim]]
* [[Algorisme de Ford-Fulkerson]]


{{ORDENA:Teorema De Flux Maxim Tall Minim}}
[[Categoria:Investigació operativa]]
[[Categoria:Teoremes matemàtics|Flux maxim tall minim]]