Matemáticas - Teoría de grafos

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,¹ y publicado en 1965.² 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}$.

Constracció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})}$.

ancestro común más bajo (ACB) es un concepto dentro de la Teoría de grafos y Ciencias de la computación. Sea T un árbol con raíz y n nodos. El ancestro común más bajo entre dos nodos v y w se define como el nodo más bajo en T que tiene a v y w como descendientes (donde se permite a un nodo ser descendiente de él mismo).

El ACB de v y w en T es el ancestro compartido de v y w que está localizado más lejos de la raíz. El cómputo del ancestro común más bajo puede ser útil, por ejemplo, como parte de un procedimiento para determinar la distancia entre pares de nodos en un árbol: la distancia de v a w puede ser calculada como la distancia desde la raíz hasta v, sumada con la distancia desde la raíz hasta w, menos dos veces la distancia desde la raíz hasta su ancestro común más bajo.

En una estructura de datos árbol donde cada nodo referencia a su padre, el ancestro común más bajo puede ser determinado de forma muy simple encontrando la primera intersección de los caminos desde v and w hasta la raíz. En general, el tiempo computacional requerido por este algoritmo es O(h) donde h es la altura del árbol (longitud del camino más largo desde una hoja hasta la raíz). Sin embargo, existen muchos algoritmos para procesar árboles con los que el ancestro común más bajo puede ser encontrado de forma más rápida.

Se puede buscar en tiempo constante por pregunta después de un preprocesamiento en tiempo lineal.

Sin preprocesamiento se puede mejorar el tiempo de cómputo del algoritmo ingenuo hasta O(log h) almacenando los caminos a través del árbol usando skew-binary random access lists, premitiendo aún al árbol ser extendido en tiempo constante (Edward Kmett (2012)).

Historia

El problema del ancestro común más bajo fue definido por Alfred Aho, Jonh Hopcroft y Jeffry Ullman en 1973, pero Harel Dov y Robert Tarjan fueron los primeros en desarrollar una estructura de datos óptima y eficiente para encontrar el ancestro común más bajo. Su algoritmo procesa cualquier árbol en tiempo lineal, usando unadescomposición de caminos fuerte, así las preguntas subsiguientes por el ancestro común más bajo pueden ser respondidas en tiempo constante por pregunta. Sin embargo, su estructura de datos es compleja y difícil de implementar. Tarjan también encontró un simple, pero menos eficiente algoritmo, basado en la estructura de datos conjuntos disjuntos.

En 1988 Baruch Schieber y Uzi Vishkin simplificaron la estructura de datos de Harel y Tarjan, consiguiendo una estructura implementable con el mismo preprocesamiento asintótico y rangos de tiempo por pregunta. Su simplificación está basada en el principio que, en dos tipos especiales de árboles, los ancestros comunes más bajos son fáciles de determinar: si el árbol es un camino, entonces el ancestro común más bajo puede ser computado simplemente del mínimo entre los niveles de los dos nodos por los que se está preguntando, mientras que si el árbol es un árbol binario completo, los nodos pueden ser indexados de forma tal que el ancestro común más bajo se reduce a una simple operación binaria entre índices. La estructura de Schieber y Vishkin descompone cualquier árbol en una colección de caminos, tal que las conexiones entre los caminos tienen la estructura de árbol binario, y combina ambas de estas dos simples técnicas de indexado.

En 1993 Omer Berkman y Uzi Vishkin descubrieron una forma completamente nueva para responder preguntas sobre el ancestro común más bajo, logrando de nuevo preprocesamiento en tiempo lineal con preguntas en tiempo constante. Su método funciona formando un ciclo de euler de un grafo formado por el árbol de entrada doblando cada arista, usando este camino para escribir una secuencia de números de niveles de los nodos en el orden en que el camino los visita; la pregunta sobre el ancestro común más bajo puede entonces ser transformada en una pregunta que busque el valor mínimo dentro de algún subintervalo de esta secuencia de números. Ellos entonces manipularon este problema mínimo valor en un rango combinando dos técnicas, una técnica basada en precomputar las preguntas en intervalos largos que tienen tamaño potencias de dos, y la otra basada en una tabla para buscar en intervalos pequeños. Este método fue presentado más tarde en una forma simplificada por Michael Bender y Martin Farach-Colton en el 2000. Como fue previamente observado por Gabow, Bentley y Tarjan en 1984, el problema del mínimo en un rango puede ser transformado hacia atrás en el problema del ancestro común más bajo usando la técnica de árboles cartesianos.

Otras simplificaciones fueron hechas por Alstrup, Gavoille, Kaplan y Rauhe en 2004 y Fischer y Heun en 2006.