Redes

Redes. Flujo máximo
Otro de los grandes problemas de optimización se da en la búsqueda del flujo máximo en las redes de distribución.
Llamaremos red a un dígrafo simple con dos vértices especiales, un minimal (la fuente) s y un maximal (el pozo) t, y que tiene asignada una capacidad no negativa cij a cada arco (vi; vj) del dígrafo.
Un flujo f, es una asignación de un valor fij a cada arco (vi;vj) del dígrafo. Escribiremos f+(v) para denotar el flujo total saliente de un vértice v ; y f¡(v) para denotar el flujo total entrante.
Es decir f+ (vi) =
P
k
fik, la suma de los flujos de los arcos salientes de vi y f¡(vi) =
P
k
fki , la suma de los flujos de los arcos entrantes. El flujo debe cumplir dos condiciones (en ocasiones se distingue denominándolo flujo factible o valido):
²el flujo en cada arco debe ser no negativo y no exceder la capacidad del arco, 0 · fij · cij
² en cada vértice v 6= s y v 6= t , distinto de la fuente y el pozo, debe cumplirse que f¡(v) = f+(v)
(\Conservación del flujo" o \Ley de Kirchhoff®")
Naturalmente 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:
En efecto, por ser un dígrafo (todo arco sale de un vértice y llega a otro) se tiene
P
v2V
f¡(v) =
P
v2V
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 reduce a
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 sele llama valor del flujo, es decir,
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,
en redes de flujo eléctrico, distribución de agua, tráfico en carreteras, redes de transmisión de datos,
distribución de mercancías del productor al consumidor, etc.
El objetivo de la optimización es por tanto maximizar el valor delflujo en la red. Y la manera de hacerlo
es buscar caminos desde el nodo fuente al pozo en los que sea posible aumentar el flujo.


Recorridos aumentadores.
Si P es un recorrido aumentador con margen mínimo m, entonces incrementando el flujo en
m en los arcos hacia adelante de P y reduciendo el flujo en m en los arcos hacia atrás de P se obtiene un flujo valido con val(f0) = val(f) + m.Demostración:
P es un recorrido de s a t , como s es minimal y t maximal, el arco de s al primer vértice y el arco del ultimo vértice a t son hacia adelante, por lo que para el nuevo flujo se suma en ambos m (+). En los vértices intermedios solo pueden darse 4 situaciones (como en el dibujo):
(i) vi esta entre dos arcos hacia adelante, en ambos se suma m (+ y +);
(ii) vj esta entre un arco haciaadelante y otro hacia atrás, en el primero se suma m y en el segundo se resta m (+ y ¡);
(iii) vk esta entre un arco hacia atrás y otro hacia adelante, se resta m y se suma m (¡ y +);
(iv) vs esta entre dos arcos hacia atrás, en ambos se resta m (¡ y ¡).
i) el arco anterior a vi incrementa su flujo en m, luego f0¡

1.5.3 Algoritmo de Ford-Fulkerson o del Flujo máximo
Si bien el teoremadel Flujo máximo y corte mínimo es el mas conocido y admirado, no es útil para la obtención de un flujo máximo (en una red de n nodos tendríamos que chequear 2n¡2 conjuntos de corte y eso solo para conocer el valor del flujo máximo). El algoritmo se basa en el Teorema 40 anterior, se van buscando recorridos aumentadores del flujo hasta que no sea posible encontrar más.
Para la búsqueda delrecorrido aumentador, se usan dos procesos que conviene explicar, el etiquetado de un vértice y la exploración de un vértice. Explorar un vértice es buscar los vértices conectados con el mediante un arco, saliente o entrante, y son estos vértices encontrados en la exploración los que son etiquetados; solo se etiquetan si no lo estaban ya y si tienen margen para aumentar el flujo. En el etiquetado, debe...