PDF de programación - Algoritmos de emparejamiento

Max-Flow

Jesús, Mager

Algoritmos de emparejamiento

Mager, Jesús

1Universidad Autónoma Metropolitana

Unidad Azcapozalco

2015

Introducción

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.
Un emparejamiento en un grafo es un conjunto de aristas que no
comparten un mismo nodo. Buscaremos la mejor combinación
para tener el máximo número de emparejamientos posible.
También podemos agregar pesos a las aristas, donde el reto sería
encontrar el conjunto de aristas que contengan el peso mayor.
Estos algoritmos pueden ser consideras instancias del concepto
camino de incremento usado en Max-Flow. Se tratarán los grafos
bipartitos primero por ser más sencillos para su resolución.

Conceptos

Max-Flow

Jesús, Mager

Un emparejamiento M es un subconjunto de G = (V , E ) con

la propiedad de que ningún par de aristas comparten algún
nodo.

Un emparejamiento máximo es el que más se acerque a |V|/2.
Dado G , el problema del emparejamiento es encontrar un

emparejamiento máximo M sobre G .

Cuando la cardinalidad de un emparejamiento es |V|/2, el
emparejamiento mas grande posible en un grafo de |V| nodos,
decimos que el emparejamiento es completo o perfecto.
Los arcos en M serán llamados arcos emparejados; los

restantes nodos libres.

Si un camino contiene nodos libres entonces será llamado un

camino alternativo.

Los vértices que se encuentran en caminos alternativos

comenzando con un vértice expuesto y tienen un rango impar
en este camino son llamados exteriores; que tienen un rango
par se llaman interiores.

Max-Flow

Jesús, Mager

Con esto, planteamos:
Lema: Sea P un conjunto de arcos en un camino de incremento
p = [u1, u2, . . . , u2k ] en un grafo G con respecto al

emparejamiento M. Entonces M = M P es una cardinalidad de
emparejamiento |M| + I . (El operador S T denota la diferencia
simétrica de S y T , definida como S T = (S − T ) ∪ (T − S) )

Teorema: Un M de emparejamiento en un grafo G es máximo, si
y sólo si, no existe un camino de incremento en G respecto a M.
Por esto, será posible plantear que dado un emparejamiento, se
puede buscar caminos de aumento, hasta que ya no exista alguno
nuevo, con lo que se resolverá el problema.

Algoritmo de emparejamiento bipartita

Max-Flow

Jesús, Mager

Entrada: Un grafo bipartita B = (V , U, E ).
Salida: El máximo emparejamiento de B representado como un arreglo
mate.
for all v ∈ V ∪ U do

Inizializando

Construimos el grafo auxiliar

mate[v ] ← 0
end for
for all v ∈ V do

exposed[v ] ← 0

end for
A ← ∅
for all

[v , u] ∈ E do
if mate[u] = 0 then
exposed[v ] ← u
else if mate[u] = then
A ← A ∪ (v , mate[u])

end if
Q ← ∅
for all v ∈ V do

if mate[v ] = 0 then

Q ← Q ∪ {v}, label[v ] ← 0

end if

end for
Continua en la siguente página.

end for

Algoritmo de emparejamiento bipartita
(Continuación)

Max-Flow

Jesús, Mager

while Q = ∅ do

Sea v un nodo de Q
remueve v de Q
if exposed[v ] = 0 then

else

augment(v), goto estado
for all dovs /∈ label tal que (v , v) ∈ A:

label[v] ← v , Q ← Q ∪ {v}

end for

end if
end while
function augment(v)
if label[v ] = 0 then

else

mate[v ] ← exposed[v ], mate[exposed[v ]] ← v
exposed[label[v ]] ← mate[v ]
mate[v ] ← exposed[v ]
mate[exposed[v ]] ← v
augment(label[v])

end if

end function

Max-Flow

Jesús, Mager

Cada incremento también incrementa la cardinalidad del
emparejamiento en uno, por lo que podemos tener a lo mucho
mín(|V|,|U|) estados. La complejidad de cada estado es de
O(|E|). La contrucción del grafo auxiliar y el calculo del arreglo
expuesto requiern O(|E|), ya que |E| arcos deben de considerarse.
Por lo que el algoritmo resuele correctamente el problema del
emparejamiento sobre un grafo bipartito B = (V , U, E ) en
O(mín(|V|,|U|)˙|E|)).

Max-Flow

Jesús, Mager

El resultado de O(mín(|V|,|U|)˙|E|)) se puede mejorar. Se puede
recudir el problema de del emparejamiento bipartito a un problema
de max-flow para redes sencillas. Para el grafo bipartita
B = (V , U, E ) definimos la siguente red N(B) = (s, t, W , A),
donde s y t son dos nodos nuevos, W es la unión entre {s, t}, V y
U, y A, es un conjunto de arcos consistentes de tres categorías:

Los arcos (s, v ) para todo v ∈ V
Los arcos (u, t) para todo u ∈ U
Los arcos (v , u) para todo v ∈ V y v ∈ V tal que [v , u] ∈ E .

Apareamiento no bipartito: blossoms

Max-Flow

Jesús, Mager

Lema: La cardinalidad del máximo apareamiento de un grafo
bipartita B equivale al valor del máximo flujo s − t
Teorema: Podemos resolver el porblmea del emparejameiento
bipartita en O(|V|1/2|E|).

Max-Flow

Jesús, Mager

Teorema: Suponga que mientras se busca po run camino de
incremento desde un no do expuesto en un grafo G con respecto
al apareamiento M, descubrimos un blossom en b. Entonces,
existe un camino alternativo desde u a cualquier nodo en b,
terminando en un arco apareado.
Teorema: Suponga que, mientras se busca por un camino de
incremento desde un nodo u de un grafo G con respecto al
emparejamiento M, se descubre un blossom b. Entonces ixiste un
camino de aumento desde u ∈ G con respecto a M hay uno de u
(vb si u está en la base de b) en G /b con respecto a M/b.

Max-Flow

Jesús, Mager

El algoritmo para la solución del problema de apareamiento no
bipartita es de O(|V|4). Se utiliza el algoritmo del caso bipartita,
junto a los métodos necesarios para enfrentarse a los blossoms. Se
va a usar el digrafo auxiliar como en el primer algoritmo y se va a
realizar un vértice expuesto a la vez.
Teorema: Suponga que un grafo G no existe un camino de
incremento desde un vértice expuesto u con respecto al
apareamiento M. Sea p un camino de aumento que termina en
otros nodos expustas v y w . Entonces no existe un camino de

incremento desde u respecto a M P tampoco.

Crolario: Si en algún estado no existe un camino de aumento
desde un nodo u, entonces nunca habrá caminos de aumento
desde u.
Por lo tanto, si la búsqueda falla en encontrar un camino de
incremento desde el nodo u, u nunca volverá a ser considerado
como un potencial punto de partida. Se mantendrá esto en un
registro llamado considered[u] ← 1

Algoritmo no bipartita de emparejamiento

Max-Flow

Jesús, Mager

Entrada: Un grafo G = (V , E )
Salida: Un emparejamiento máximo de G en terminos del arreglo mate.
for all v ∈ V do

mate[v ] ← 0, considered[v ] ← 0

end for
estado:
while ∃v ∈ V con considered[u] = 0 y mate[u] = 0 do

considered[] ← 1, A ← ∅
for all v ∈ V do

exposed[v ] ← 0
for all [v , w ] ∈ E do

if mate[w ] = 0 y w = u then
exposed[v ] ← w
else if mate[w ] = v then
A ← A ∪ (v , mate[w ])

end if

end for
for all v ∈ V do
seen[v ] ← 0

end for
Q ← u, label[u] ← 0
Continúa...

end for
end while

Algoritmo no bipartita de emparejamiento.
Continuación...

Max-Flow

Jesús, Mager

while Q = ∅ do

Sea v un nodo de Q
Remueve v de Q
for all los nodos no etiquetados w ∈ V tales que (v , w ) ∈ A do

Q ← Q ∪ w , label[w ] ← v
seen[mate[w ]] ← 1
if exposed[w ] = 0 then

augment(w)
goto estado

end if
if seen[w ] = 1 then

blossom(w)

end if

end for
end while

Teorema: El algoritmo encuentra correctamente el
emparejamiento máximo en un grafo G = (V , E ) en O(|V|4)