Teorema Del Flujo Maximo

3.8.2 Teorema del Flujo Máximo

Una vez que hemos modelado una situación específica con una red de transporte, es importante poder analizar su alcance, esto es, el flujo máximo que puede soportar.

En el caso concreto de las bombas de agua nos interesa saber cuál es la cantidad máxima que es posible suministrar con este sistema de bombeo. Para esto veremos un algoritmo que nos ayudará a determinar este valor tan importante.

Definición 1. Sea R una red de transporte con fuente F, sumidero S, con pesos w(i,j) y con flujo f. Sea n0, n1, … , nk un camino de F = n0 a S = nk, donde las aristas pertenecen a R pero sin considerarlo como un grafo dirigido. Una arista (ni, ni+1) en el camino:

Si está en R decimos que está orientada en forma propia y si no está en R decimos que no está orientada en forma propia.

Dos aristas consecutivas pueden tener las siguientes orientaciones:

Teorema: Sea C: n0, n1, … , nk un camino de F = n0 a S = nk en una red R. Sea f un flujo en R con valores f(i,j). Para las aristas orientadas en forma propia tenemos W(i,j) < f(i,j) y para las no orientadas en forma propia f(i,j) > 0.

Definimos f + (i,j) como:

f(i,j) para las aristas que no están en el camino. f(i,j) + M si la arista está orientada en forma propia. f(i,j) – M si la arista no está orientada en forma propia.

M = min { W(i,j) – f(i,j) si (i,j) está orientada en forma propia y si f(i,j) no está orientada en forma propia }

Entonces f+ es un flujo que f precisa en el valor M.

!!! Algoritmo del Flujo Máximo:

Sea R una red de transporte con fuente F y sumidero S y con pesos w(i,j) para cada arista (i,j). Sean n0, n1, … , nk los nodos de la red.

[I] Inicio: f(i,j) = 0, N = { }

[E] Eliminar etiquetas: pred(ni) = NULL, val(ni) = NULL para todos los nodos ni.

[Fuente] Etiquetar la fuente: pred(F) = #, val(F) = ∞, N = { F }

[Fin] Si N = { } el algoritmo termina y f es un flujo máximo.

[Main] Mientras val(S) = NULL

	[N] Elegimos un nodo u en N, N = N – ū.
	[A] Para toda arista (u,v) con val(v) = NULL
	si f(u,v) < W(u,v) : pred(v) = u y val(v) = min {val(u), W(u,v) – f(i,j)}
	si f(u,vj) > 0 : pred(v) = u y val(v) = min{ val(u), f(i,j) }
	hacemos N = N  ∪ {v}

[C] Encontramos un camino n0, n1, … , nk de F a S.

	Sea S = n0, ni + 1 = pred(ni) para todo nodo ni ≠ F

[AC] Actualizar el flujo en el camino. Para cara (ni, ni-1)

	Si la arista está orientada en forma propia f(ni, ni-1) = f(ni, ni-1) + val(S)
	Si la arista no está orientada en forma propia f(ni, ni-1) = f(ni, ni-1) – val(S)
	Quitamos el predecesor de S, pred(S) = NULL
	Regresar a [Fin]

BIBLIOGRAFIA:

I.) Matematicas para computadora de Luis Alberto Lomeli Beherendt

---------------------------------------------------------------------------------------------------