Teorema de flux màxim tall mínim

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 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.

Definició matemàtica[modifica | modifica el codi]

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

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

El valor del flux és definit per | f | = Σv∈Vfsvv∈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) é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 | modifica el codi]

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 | modifica el codi]

Fitxer:Max-flow min-cut example.svg
Una xarxa amb el valor del flux igual a la capacitat del tall s-t

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 | modifica el codi]

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é[modifica | modifica el codi]