Algoritmo de Emparejamiento de Edmonds

El Algoritmo del Blossom o Algoritmo de Emparejamiento de Edmonds es un algoritmo de teoría de grafos para construir emparejamientos máximos en grafos. El algoritmo fue desarrollado por Jack Edmonds en 1961,^[1]​ y publicado en 1965.^[2]​ El emparejamiento máximo es construido iterativamente mejorando el emparejamiento actual a través de caminos m-incrementos mientras al menos exista uno. La idea esencial del algoritmo es que un ciclo de longitud impar (blossom) es contraído en un solo vértice para luego continuar la búsqueda de caminos m-incrementos en el grafo resultante. La idea de contraer los ciclos de longitud impar se debe a que si no se hiciera el mismo algoritmo de búsqueda de caminos m-incrementos al entrar en uno de estos ciclos y salir pudiera reportar falsos positivos.

La importancia del algoritmo radicó en que dio la primera prueba de que un emparejamiento máximo puede ser encontrado en tiempo polinomial.

Definiciones

Se mantienen los nombres de las definiciones en inglés para mayor entendimiento con la literatura. Si se hiciera una traducción literal entonces 'blossom' sería capullo, 'stem' sería tallo y 'flower' sería flor. Edmonds realiza una analogía entre la estructura de las flores y las estructuras utilizadas por el algoritmo.

Vértice saturado

Un vértice se dice saturado por un emparejamiento, cuando él es extremo de alguna arista del emparejamiento.

Blossom

Un blossom ${\displaystyle B}$  sobre un emparejamiento ${\displaystyle M}$  en un grafo ${\displaystyle G=(V,E)}$ , es un ciclo de longitud impar que cumple que ${\displaystyle M\cap E(B)}$  es un emparejamiento máximo en ${\displaystyle B}$ . (Obsérvese ${\displaystyle M\cap E(B)}$  deja uno y sólo un vértice ${\displaystyle b}$  sin estar emparejado).

Stem

Un stem sobre un emparejamiento ${\displaystyle M}$  un grafo ${\displaystyle G=(V,E)}$  es un vértice no saturado por ${\displaystyle M}$  o un camino m-alternativo con un extremo no saturado y el otro sí.

Flower

Se define como flower a un blossom y un stem interceptados en solo uno de los extremos del stem (vértice ${\displaystyle b}$  no saturado del blossom).

Constracción de un blossom en un grafo

Sea ${\displaystyle B}$  un blossom de una flower ${\displaystyle F}$  sobre un emparejamiento ${\displaystyle M}$  en un grafo ${\displaystyle G}$  se define como contracción de ${\displaystyle B}$  en el grafo ${\displaystyle G}$ , al grafo ${\displaystyle G'}$  que resulta de sustituir a ${\displaystyle B}$  por un vértice ficticio ${\displaystyle b}$ , el cual es adyacente a todos los vértices ${\displaystyle v_{i}}$  adyacentes a los vértices de ${\displaystyle B}$  y se denota como ${\displaystyle G/B}$ .

Contracción de un blossom dado un emparejamiento

Sea ${\displaystyle B}$  un blossom de una flower ${\displaystyle F}$  sobre un emparejamiento ${\displaystyle M}$  en un grafo ${\displaystyle G}$  se define como contracción de ${\displaystyle B}$  en el emparejamiento ${\displaystyle M}$ , al emparejamiento ${\displaystyle M'=\{(a,b)\in M\vee (a,b)\not \in B\vee (v\in B\wedge b\not \in B)\}}$  (${\displaystyle v}$  sería el vértice ficticio del blossom). Se denote ${\displaystyle M/B}$ .

Teorema

Sea ${\displaystyle B}$  un blossom de una flower ${\displaystyle F}$  sobre un emparejamiento ${\displaystyle M}$  en un grafo ${\displaystyle G}$  entonces: ${\displaystyle M}$  es un emparejamiento máximo en ${\displaystyle G}$  si y solo si ${\displaystyle M/B}$  es un emparejamiento en ${\displaystyle G/B}$ .

Descontracción

La parte de la demostración más interesante del algoritmo es probar que si ${\displaystyle G/B(G')}$  tiene un camino m-incremento ${\displaystyle p'=(v_{0}\,\ldots \,v_{t})}$  entonces ${\displaystyle G}$  tiene un camino m-incremento ${\displaystyle p}$  semejante a ${\displaystyle p'}$ .

Para la demostración se separan varios casos:

1. El camino m-incremento en ${\displaystyle G'}$  no contiene ningún vértice ficticio, entonces el grafo ${\displaystyle G}$  contiene el mismo camino m-incremento sin modificación.
2. El camino m-incremento en ${\displaystyle G'}$  contiene a un vértice ficticio (sin pérdida de generalidad), este a su vez se subdivide en dos casos:
   1. El vértice ficticio no se encuentra en un extremo del camino m-incremento ${\displaystyle p'}$ , entonces en ${\displaystyle G}$  encontraremos el siguiente camino m-incremento ${\displaystyle (v_{0}\rightarrow \ldots \rightarrow w\rightarrow w'\rightarrow \ldots \rightarrow u'\rightarrow u\rightarrow \ldots \rightarrow v_{t})}$  , el camino m – alternativo ${\displaystyle (w'\rightarrow \ldots \rightarrow u')}$  existe como consecuencia de la definición de blossom. Supongamos que no exista, esto sería si en algún momento no se puede alternar entre emparejado-no emparejado, la única forma posible que ocurra esto en un emparejamiento correcto es emparejado – no emparejado – no emparejado, esto por la definición de blossom no puede ocurrir ya que el único vértice que puede no estar emparejado con uno dentro del blossom es ${\displaystyle u'}$ , sino no se cumpliría que ${\displaystyle M\cap E(B)}$  sea un emparejamiento máximo en ${\displaystyle B}$ . El otro problema que pudiera ocurrir es que al salir del blossom por la arista ${\displaystyle w'-w}$  hallamos escogido un camino que seleccionaba como arista anterior a ${\displaystyle w'-w}$  una que no pertenece al emparejamiento, cuestión que no crearía un camino m-incremento, esto se resuelve escogiendo el otro camino posible de ${\displaystyle u'-w'}$  del blossom (existen dos debido a que el blossom es un ciclo).

1. 1. El vértice ficticio se encuentra en un extremo del camino m-incremento ${\displaystyle p'}$ , donde ${\displaystyle v_{t}=v}$ , entonces en ${\displaystyle G}$  encontraremos el siguiente camino m-incremento ${\displaystyle v_{0}\rightarrow \ldots \rightarrow u\rightarrow u'\rightarrow \ldots \rightarrow v'}$ , el camino m – alternativo ${\displaystyle (u'\rightarrow \ldots \rightarrow v')}$  existe como consecuencia de la definición de blossom (Ver el caso anterior). (Observación: este blossom no puede tener ningún vértice emparejado con uno exterior al blossom por lo tanto queda uno y solo uno no saturado por el emparejamiento).

Algoritmo

El algoritmo para encontrar caminos m-incrementos utiliza una estructura de datos llamada bosque, cuyos árboles individuales corresponden a partes específicas del grafo. En cada iteración del algoritmo ocurre algunas de las siguientes opciones (1) encuentra un camino m-incremento, (2) encuentra un blossom, lo comprime y comienza la búsqueda en el grafo resultante o (3) concluye al no encontrar caminos m-incrementos.

01 Path FindAugmentingPath (Graph G, Match M) { 02 Forest F = new Forest(); // Crea un bosque vacío 03 Queue vertices = new Queue(); // Cola de procesado de vértices 04 for each (v∈V no saturado por M){ 05 F.NewTree(new Tree(v)); // Se agrega nuevo árbol con raíz v al bosque 06 vertices.enqueue(v); 07 } 08 Vertex v = vertices.dequeue(); 09 while (v != NULL ){ // distancia a la raíz par 10 Queue adjacents = new Queue(); // Cola de procesado de adyacentes. 11 for each ({v,w}∈E && {v,w}∉M} 12 adjacents.enqueue(w); 13 w = adjacents.dequeue(); 14 while (w != NULL) 15 if (w∉F){ // Si w está emparejado 16 F[root(v)].AddEdges({v,w}, {w,x}); // x emparejado con w en M 17 vertices.enqueue(x); 18 } 19 else 20 if (distance(w, root(w)) % 2 = 0){ // distancia par a su raíz 21 if (root(v) ≠ root(w)) // camino m-incremento. 22 return new Path(root(v),…, v, w, …root(w)); 23 else {// encontramos un blossom 24 Blossom B = DetectBlossom({v,w}); 25 Graph G’ = G/B; 26 Match M’ = M/B; 27 Path P’, P; 28 P’ = FindAugmentingPath(G’, M’); 29 if (P’ != NULL) 30 P = FixContractedPath(G,B,P’); 31 return P; 32 } 33 w = adjacents.dequeue(); 34 } 35 } 36 vertices.dequeue(); 37 } 38 return NULL; 39 } 

Coste computacional

El ciclo de la línea 04 agrega los vértices no saturados para un costo O(|V|), el ciclo de la línea 14 se ejecuta |E| veces y por cada iteración suponiendo que se encuentra un blossom este se contrae en O(|V|) y se llama recursivamente al mismo algoritmo, partiendo de que pueden haber a lo sumo ${\displaystyle O(|V|)}$  blossoms obtenemos un costo de ${\displaystyle O(|V|^{4})}$ .

Referencias

1. Edmonds, Jack (1991), «A glimpse of heaven», en J.K. Lenstra, A.H.G. Rinnooy Kan, A. Schrijver, ed., ed., History of Mathematical Programming --- A Collection of Personal Reminiscences, CWI, Amsterdam and North-Holland, Amsterdam, pp. 32-54 .
2. Edmonds, Jack (1965). «Paths, trees, and flowers». Canad. J. Math. 17: 449-467. doi:10.4153/CJM-1965-045-4.