INVESTIGACION DE OPERACIONES

22 – Laboratorio de Matem´ticas : Teor´ de Grafos
a
ıa

1.5

1.5 Redes. Flujo m´ximo
a

Redes. Flujo m´ximo
a

Otro de los grandes problemas de optimizaci´n se da en la b´squeda del flujo m´ximo en las redes de
o
u
a
distribuci´n.
o
Definici´n 33.- Llamaremos red a un digrafo simple con dos v´rtices especiales, un minimal (la fuente)
o
e
s y un maximal (el pozo) t, y que tieneasignada una capacidad no negativa cij a cada arco (vi , vj ) del
digrafo.
Un flujo f , es una asignaci´n de un valor fij a cada arco (vi , vj ) del digrafo. Escribiremos f+ (v)
o
para denotar el flujo total saliente de un v´rtice v ; y f− (v) para denotar el flujo total entrante. Es decir
e
f+ (vi ) = fik , la suma de los flujos de los arcos salientes de vi y f− (vi ) = fki , la suma de losflujos
k

k

de los arcos entrantes. El flujo debe cumplir dos condiciones (en ocasiones se distingue denomin´ndolo
a
flujo factible o v´lido):
a
• el flujo en cada arco debe ser no negativo y no exceder la capacidad del arco, 0 ≤ fij ≤ cij
• en cada v´rtice v = s y v = t, distinto de la fuente y el pozo, debe cumplirse que f− (v) = f+ (v)
e
(“Conservaci´n del flujo” o “Ley de Kirchhoff”)
oNaturalmente es obvio que f− (s) = 0 = f+ (t). Y es sencillo comprobar que
Lema 34.- Para cualquier flujo (factible) en una red se cumple que f+ (s) = f− (t)
Demostraci´n:
o
En efecto, por ser un digrafo (todo arco sale de un v´rtice y llega a otro) se tiene
e
v∈V

f− (v) =

v∈V

f+ (v),

y como por la ley de Kirchhoff, f− (v) = f+ (v) para todo v que no sea s ni t, la igualdad se reducea
f− (s) + f− (t) = f+ (s) + f+ (t), pero como f− (s) = f+ (t) = 0, se tiene que f+ (s) = f− (t).
A ese valor com´n del flujo saliente en s y del flujo entrante en t se le llama valor del flujo, es decir,
u
val(f ) = f+ (s) = f− (t).
Reconoceremos m´s f´cilmente ahora que los flujos en redes son de aplicaci´n en multitud de campos,
a a
o
en redes de flujo el´ctrico, distribuci´n de agua, tr´ficoen carreteras, redes de transmisi´n de datos,
e
o
a
o
distribuci´n de mercancias del productor al consumidor, etc.
o
El objetivo de la optimizaci´n es por tanto maximizar el valor del flujo en la red. Y la manera de hacerlo
o
es buscar caminos desde el nodo fuente al pozo en los que sea posible aumentar el flujo.

1.5.1

Recorridos aumentadores

Antes de nada, intentemos explicarc´mo puede aumentarse el flujo, ejemplificando sobre los dibujos
o
siguientes. Sobre cada arco indicamos su capacidad y el flujo actual entre par´ntesis y para indiciar los
e
datos, suponemos s = v0 y t = v5 .
Supongamos que tenemos un camino de s a t, un camino legal siguiendo las direcciones de las
flechas, tal que en cada arco del camino el flujo existente no ocupa toda la capacidad del arco, quehay margen en cada arco para aumentar el flujo (como s = v0 →v1 →v2 →v5 = t en el dibujo, con
c01 − f01 = 2 − 1 = 1 > 0, c12 − f12 = 3 − 1 = 2 > 0 y c25 − f25 = 2 − 0 = 2 > 0). Entonces, si sumamos
el m´
ınimo de los m´rgenes m al flujo de cada arco del camino, el nuevo flujo f as´ construido es v´lido y
a
ı
a
tiene mayor valor, val(f ) = val(f ) + m > val(f ) (en nuestro ejemplo 1 = m´ın{1, 2, 2}, y f01 = 1 + 1,
f12 = 1 + 1, f25 = 0 + 1, con val(f ) = val(f ) + m = 1 + 1).
m12 = 1

f

vs (1)3 E s
v2
m25 = 2
1
B
¨
(1)2 ¨¨
 rr (0) 2
rr
 
¨¨
r s
(1)1  
j
r t
¨
s s
rr
B
¨
 
¨¨
rr
¨
(0)1 r s  
j 
r©
E s ¨ (1) 1
¨
v3 (1)1 v4
m01 = 1

Prof: Jos´ Antonio Abia Vian
e

vs (1+1) 3 E s
v2
1
¨
B
(1+1) 2 ¨¨
 rr (0+1) 2
rr
 
¨¨
r s
(1) 1  
j
rt
s
s ¨
rr
B
¨
 
¨¨
rr
¨
(0)1 r s  
r 
j©
E s ¨ (1)1
¨
v3 (1)1 v4

f

I.T.I. en Electricidad

23 – Laboratorio de Matem´ticas : Teor´ de Grafos
a
ıa

1.5 Redes. Flujo m´ximo
a

El camino de s a t que hemos tomado ser´ por tanto un camino aumentador del flujo. Pero puede
a
ocurrir que no dispongamos de estos caminos y sin embargo el flujo pueda aumentarse. Con el...