PDF de programación - Algoritmos eficientes para el problema Max-Flow

Max-Flow

Jesús, Mager

Algoritmos eficientes para el problema

Max-Flow

Mager, Jesús

1Universidad Autónoma Metropolitana

Unidad Azcapozalco

2015

Introducción
Hay más información aquí

Max-Flow

Jesús, Mager

El presente trabajo es un resumen del libro “Combinatorial
Optimization. Algorithms and Complexity” escrito por
Christos H. Papadimitriou y Kenneth Steiglitz.
Si bien el algoritmo Simplex es muy útil, pues resuelve problemas
de programación lineal generales, no es muy eficiente en su
complejidad, que es explonencial. Para la resolución del problema
max-flow se va a explorar el problema para mejorar esto.
Los resultados para max-flow son también relevantes para otros
problemas de optimización.

Formulación Nodo arco del problema Max-Flow

Max-Flow

Jesús, Mager

Se busca encontrar un flujo factible de un único nodo origen (s) a
un único nodo pozo(t), este flujo es el máximo. Considerese una
red N = (s, t, V , E , b) con v = |V| nodos y m = |E| arcos; y sea
el flujo arc(x, y ) sea denotado por f (x, y ). Entonces el problema
de maximo flujo (max-flow) es la siguiente formulación de
programación lineal, que es pensada como un dual:

máx v

Af + dv = 0
f ≤ b
f ≥ 0

donde d ∈ R n está definido por:

dt =

 -1 si i = s;

1 si i = t;
0 en otro caso;

Max-Flow

Jesús, Mager

A continuación se examinará un algoritmo fundamental de gráfos,
llamado búsqueda. Diferentes variantes del algoritmo de búsqueda
están en el corazón de diversos algoritmos de gráficos.

Búsqueda en Grafos

Max-Flow

Jesús, Mager

2|V|, como por

Un Grafo G = (V , E ) es representado por la lista de adjacencias
A(v ), v ∈ V . Como siempre se asume que |E| ≥ 1
ejemplo que G no tiene nodos aislados.
El algoritmo tiene la idea de que se comienza con un vértice v1 y
lo marca. Posteriormente se repite este proceso con sus vértices de
adjacencia, posterioremente con sus vértices de adjacencia y se
repite el proceso.
En el conjunto Q se mantiene un alista para todos lo vértices que
son posibles para marcar. Esto es, que sean adjacentes y que no se
encuentren marcados.

Algoritmo: Búsqueda en grafos

Max-Flow

Jesús, Mager

Entrada: Un grafo G , representado por su lista de adjacencias, y un nodo v1.
Salida: EL mismo grafo con sus nodos realcionados por caminos desde el
nodo v1 marcado.
Q ← {v1}
while Q = ∅ do

sea v un elemento de Q.
Remover v de Q
Marca v
for all v ∈ A(v ) do

if v no está marcado then

Agragar v a Q

end if

end for
end while

Max-Flow

Jesús, Mager

El algoritmo de búsqueda marca todos los nodos de G conectados
con v1 en tiempo O(|E|).

Max-Flow

Jesús, Mager

Entre los usos que se le da a este algoritmo se encunetra saber si
un grafo es conexo. También es posible usarlo para encontrar
componentes como subgráfos maximalment conexos.
Sin embargo, aún falta definir cómo se toman los elementos de la
list Q. Si se tomara a Q como una cola tomando el elemento v
como el que ha esperado más, esto se convertiría en ua búsqueda
primero a lo ancho (BFS).

Max-Flow

Jesús, Mager

La búsqueda primero a profundidad (DFS) es otra versión de la
búsqueda de grafos donde se utiliza una lista FIFO (Primero en
entrar es el primero en salir). Este algoritmo hace un camino tan
largo como es posible y regresa a hacer una nueva búsqueda
únicamente cuando no se puede avanzar.

Max-Flow

Jesús, Mager

El algoritmo de búsqueda también puede ser aplicado a digrafos.
Se puede respresentar un digrafo mediante D = (V , A) por su lista
de adjacencia: A(v ) como el conjunto de nodos v ∈ V tales que
(v , v) ∈ A. Desde ese punto de vista los grafos son únicamente un
caso especial de los digrafos: aquellos que son simétricos en qye
u ∈ A(v ) si u ∈ A(u). Por lo tanto BFS y DFS también pueden
ser aplicados a digrafos.

Max-Flow

Jesús, Mager

El algoritmo de búsqueda es una plantilla para toda una clase de
algoritmos.
Al variar las piesas del algoritmo en cajas se pueden crear
numersos algoritmos que hacen cosas distintas al mismo grafo. Por
ejemplo, podemos agregar un contador i ← i + 1; orden[v ] ← i en
ves de usar marcas. Entonces obtendremos un algoritmo que
registra el órden en que fué visitado cada nodo.
Como otro ejemplo el algoritmo Ford-Fulkerson de etiquetado para
max-flow, es en realidad una variante sofisticada de búsqueda.

Encontrar un caminos en digrafos

Max-Flow

Jesús, Mager

Supongamos que tenemos un digrafo D y dos conjuntos de nodos,
S, T ⊂ V que son origen y destino respectivamente. Queremos
enconrar un camino en D llevando de cualquier nodo en S a
cualquier nodo en T . También vamos a agegar etiquetas por cada
v , que será más útil a la hora de recuperar el camino, donde
etiqueta[v] es un arreglo con |V| entradas. El algogirtmo se
muestra a continuación.

Algoritmo: Búsqueda de caminos en digrafos

Max-Flow

Jesús, Mager

Entrada: Un Digrafo D = (V , A) y S, T ⊂ V .
Salida: Un camino en D de un nodo S a un nodo en T , si este camino
existe.
for all v ∈ S do
etiqueta[v] ← 0
if v ∈ T then
return (v )

end if

end for
while Q = ∅ do

sea v un elemento de Q.
Remover v de Q
for all v ∈ A(v ) do

if v no está etiquetado then

etiqueta[v] ← v
if v ∈ T then return camino(v)
else

Agregar v a Q

end if

end if

end for

end whilereturn No hay camino S-T en D

Pero: ¿Qué tiene de malo?

Max-Flow

Jesús, Mager

EL algoritmo Ford-Fulkerson para la resolución del problema
Max-Flow usa la técnica de etiquetado. La cuestión surge entonces
en el análisis de su complejidad. Tomando una red
N = (s, t, V , E , b) se nota que cada estado toma O(|A|), pero
dado la complejidad de todo el algoritmo es O(S|A|) donde S es el
número de incrementos llevados a cabo. EL número S tiene que
ser menor que | ˆf | que es el valor del máximo flujo en la red
(asumiendo enteros). ¿Puede S ser tan grande como | ˆf |? La
respuesta es si, si se toman decisiones desafortunadas de
incrementar caminos. Esto puede llevar a una complejidad
exponencial.

Max-Flow

Jesús, Mager

Suponga que queremos implementar una rutina a una red
N = (s, t, V , E , b) con un flujo inicial de cero. No necesitamo
examinar capacidades y flujos en este caso. Poteriormente se
tendrá que todos los arcos serán avanzado y que no hay arcos
hacia atrás. Por lo tanto la tarea de etiquetar la red es muy
parecida al algoritmo pasado. Una vez que se enceuntre un camino
de incremento, aumentamos al flujo y continuamos.

Max-Flow

Jesús, Mager

Etiquetar una red con repecto al flujo f es equivalete a la
búsqueda de camino en una red definida como:
Dado una red N = (s, t, V , A, b) y una flujo factible f de N,
definimos la red N(f ) = (s, t, V , A(f ), ac), donde A(f ) consiste de
los sigueintes arcos:
1. Si (u, v ) ∈ A y f (u, v ) < b(u, v ), entonces (u, v ) ∈ A(f ) y

ac(u, v ) = b(u, v ) − f (u, v ).

2. Si (u, v ) ∈ A y f (u, v ) > 0, entonces (u, v ) ∈ A(f ) y

ac(u, v ) = f (u, v ).

Llamamos a ac(u, v ) la capacidad de incremento de (u, v ) ∈ A(f ).
Si A contiene ambos arcos (v , u) y (u, v ), entonces N(f ) puede
tener múltiples copias de estos arcos. Podemos evitar esto de
diferentes maneras. Podemos remplazar tales arcos (u, v ) en A por
dos arcos (u, w ) y (w , u) de la misma capacidad, donde w es un
nodo nuevo. Debemos asumir por lo tanto que N(f ) no tiene
múltiples nodos.

Max-Flow

Jesús, Mager

Tomando un corte s − t, (W , ¯W ) de N(f ), el valor de este
corte es la suma de las capacidades de incremento de todos
los arcos de N(f ) que van de W a ¯W . Sin embargo, este acro
puede ser tanto uno para adelante o uno para atrás.

En el caso de ser para adelante, ac(u, v ) = b(u, v )− f (u − v );

si es para trás ac(u, v ) = f (u, v ).

Por lo tanto el valor de (W , ¯W ) en N(f ) es el valor de

(W , ¯W ) en N menos el flujo para adelante por el corte, mas
el flujo reverso del corte.

Max-Flow

Jesús, Mager

Poposición: Si | ˆf | es el valor del máximo flujo en N, entonces el
valor del máximo flujo en N(f ) es | ˆf | − |f |.

Max-Flow

Jesús, Mager

Para mejorar el problema del flujo hay que recordar que estamos
interesados únicamente en los pares s − t más cortos en N(f ), por
lo que podemos realizar simplificaciones.

El camino más corto s − t no puede pasar por un vértice en

una capa superior que t.

También podemos descartar cualquer otro vértice en la misma

capa que t excpeto t.

Un camino más corto parte de la capa 0, o sea donde se

encuentra s, por lo que para avanzar deberá ir a la siguiente
capa. De esta manera avanza de capa j a j + 1. Por lo que
también se podrá descartar cualquier acro que vaya de una
capa superior a una inferior, o cualquier arco que junta nodos
de una misma capa.

Max-Flow

Jesús, Mager

Esto resultará en una subred llamada AN(f ) de A(f ), llamada red
auxiliar respecto a f.
Proposición: Una red de capas L = (s, t, U, A, b) es una red con
un conjunto de vértices U igual a la unión disjunta de los
conjuntos U0, . . . , Ud tal que U0 = {s}, Ud = {t} y

(Uj−1 × Uj ).

L ⊂ d

j=1

Max-Flow

Jesús, Mager

AN(f ) puede construirse mientras se lleva acabao una búsqueda
primero a lo ancho sobre N(f ) dejano únicamente nodos que nos
llevas a nuevos nodos, y únicamente nodos que sean inferiores que
t. Por lo tanto, crear una red auxiliar puede ser creada en
O(|A(f )|) = O(|A|).
Esto nos ayudará a encontrar fásilmente el camino más corto de
incremento con respecto al flujo actual y más aún, mejorar el
algoritmo de etiquetado: llevar acabo tantos incrementos en el
mismo estado como se posible.

Max-Flow

Jesús, Mager

Definición: Sea N = (s, t, V , A, b) una red de capas, un camino
de incremento en N con respecto a cierto flujo g es llamado para
adelante si no utiliza arcos hacia atrás. Un flujo g en N es llamado
maximal si no existe un camino de incrementeo ahcia adlenate con
respecto a g .
Ba