title: Algoritmo de Emparejamiento de Edmonds
text: # 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, 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.
  
  # Algoritmo de Emparejamiento de Edmonds
  ## 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.
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Definiciones
  ### Vértice saturado
  
  Un vértice se dice saturado por un emparejamiento, cuando él es extremo de alguna arista del emparejamiento.
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Definiciones
  ### Blossom
  
  Un blossom $B$ sobre un emparejamiento $M$ en un grafo $G=(V,E)$, es un ciclo de longitud impar que cumple que $M\cap E(B)$ es un emparejamiento máximo en $B$. (Obsérvese $M\cap E(B)$ deja uno y sólo un vértice $b$ sin estar emparejado).
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Definiciones
  ### Stem
  
  Un stem sobre un emparejamiento $M$ un grafo $G=(V,E)$ es un vértice no saturado por $M$ o un camino m-alternativo con un extremo no saturado y el otro sí.
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Definiciones
  ### Flower
  
  Se define como flower a un blossom y un stem interceptados en solo uno de los extremos del stem (vértice $b$ no saturado del blossom).
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Definiciones
  ### Constracción de un blossom en un grafo
  
  Sea $B$ un blossom de una flower $F$ sobre un emparejamiento $M$ en un grafo $G$ se define como contracción de $B$ en el grafo $G$, al grafo $G'$ que resulta de sustituir a $B$ por un vértice ficticio $b$, el cual es adyacente a todos los vértices $v_{i}$ adyacentes a los vértices de $B$ y se denota como $G/B$.
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Definiciones
  ### Contracción de un blossom dado un emparejamiento
  
  Sea $B$ un blossom de una flower $F$ sobre un emparejamiento $M$ en un grafo $G$ se define como contracción de $B$ en el emparejamiento $M$, al emparejamiento $M'=\{(a,b)\in M\vee (a,b)\not \in B\vee (v\in B\wedge b\not \in B)\}$ ($v$ sería el vértice ficticio del blossom). Se denote $M/B$.
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Teorema
  
  Sea $B$ un blossom de una flower $F$ sobre un emparejamiento $M$ en un grafo $G$ entonces: $M$ es un emparejamiento máximo en $G$ si y solo si $M/B$ es un emparejamiento en $G/B$.
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Teorema
  ### Descontracción
  
  La parte de la demostración más interesante del algoritmo es probar que si $G/B(G')$ tiene un camino m-incremento $p'=(v_{0}\,\ldots \,v_{t})$ entonces $G$ tiene un camino m-incremento $p$ semejante a $p'$.
  Para la demostración se separan varios casos:
  * El camino m-incremento en $G'$ no contiene ningún vértice ficticio, entonces el grafo $G$ contiene el mismo camino m-incremento sin modificación.
  * El camino m-incremento en $G'$ contiene a un vértice ficticio (sin pérdida de generalidad), este a su vez se subdivide en dos casos:
  ** El vértice ficticio no se encuentra en un extremo del camino m-incremento $p'$, entonces en $G$ encontraremos el siguiente camino m-incremento $(v_{0}\rightarrow \ldots \rightarrow w\rightarrow w'\rightarrow \ldots \rightarrow u'\rightarrow u\rightarrow \ldots \rightarrow v_{t})$ , el camino m – alternativo $(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 $u'$, sino no se cumpliría que $M\cap E(B)$ sea un emparejamiento máximo en $B$. El otro problema que pudiera ocurrir es que al salir del blossom por la arista $w'-w$ hallamos escogido un camino que seleccionaba como arista anterior a $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 $u'-w'$ del blossom (existen dos debido a que el blossom es un ciclo).
  ** El vértice ficticio se encuentra en un extremo del camino m-incremento $p'$, donde $v_{t}=v$, entonces en $G$ encontraremos el siguiente camino m-incremento $v_{0}\rightarrow \ldots \rightarrow u\rightarrow u'\rightarrow \ldots \rightarrow v'$, el camino m – alternativo $(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 de Emparejamiento de Edmonds
  ## 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.
  
  # Algoritmo de Emparejamiento de Edmonds
  ## Algoritmo
  ### 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 $O(|V|)$ blossoms obtenemos un costo de $O(|V|^{4})$.