Algoritme de Emparejamiento de Edmonds

El Algoritme del Blossom o Algoritme de Emparejamiento de Edmonds és un algoritme de teoria de grafos per a construir emparejamientos màxims en grafos. L'algoritme va ser desenrollat per Jack Edmonds en 1961, i publicat en 1965. El emparejamiento màxim és construït iterativamente millorant el emparejamiento actual per mig de camins m-increments mentres a lo manco existixca un. L'idea essencial de l'algoritme és que un cicle de llongitut impar (blossom) és contret en un sol vèrtiç per a despuix continuar la busca de camins m-increments en el grafo resultant. L'idea de contraure els cicles de llongitut impar es deu a que si no es fera el mateix algoritme de busca de camins m-increments en entrar en un d'estos cicles i eixir poguera reportar falsos positius.

L'importància de l'algoritme va radicar que va donar la primera prova de que un emparejamiento màxim pot ser trobat en temps polinomial.

Definicions

Es mantenen els noms de les definicions en anglés per a major enteniment en la lliteratura. Si es fera una traducció lliteral llavors 'blossom' seria capoll, 'stem' seria brot i 'flower' seria flor. Edmonds realisa una analogia entre l'estructura de les flors i les estructures utilisades per l'algoritme.

Vèrtiç saturat

Un vèrtiç es diu saturat per un emparejamiento, quan ell és extrem d'alguna aresta de l'emparejamiento.

Blossom

Un blossom $B$ sobre un emparejamiento $M$ en un grafo $G=(V,E)$, és un cicle de llongitut impar que complix que $M\cap E(B)$ és un emparejamiento màxim en $B$. (Observe's $M\cap E(B)$ deixa un i només un vèrtiç $b$ sense estar emparellat).

Stem

Un stem sobre un emparejamiento $M$ un grafo $G=(V,E)$ és un vèrtiç no saturat per $M$ o un camí m-alternatiu en un extrem no saturat i l'atre sí.

Flower

Es definix com flower a un blossom i un stem interceptats en solament un dels extrems del stem (vèrtiç $b$ no saturat del blossom).

Constracción d'un blossom en un grafo

Siga $B$ un blossom d'una flower $F$ sobre un emparejamiento $M$ en un grafo $G$ es definix com a contracció de $B$ en el grafo $G$, al grafo $G^{\prime }$ que resulta de substituir a $B$ per un vèrtiç fictici $b$, el qual és adjacent a tots els vèrtiços $v_i$ adjacents als vèrtiços de $B$ i es denota com $G/B$.

Contracció d'un blossom donat un emparejamiento

Siga $B$ un blossom d'una flower $F$ sobre un emparejamiento $M$ en un grafo $G$ es definix com a contracció de $B$ en el emparejamiento $M$, al emparejamiento $M^{\prime }=\{(a,b)\in M\vee (a,b)\in ̸B\vee (v\in B\wedge b\in ̸B)\}$ ($v$ seria el vèrtiç fictici del blossom). Es denote $M/B$.

Teorema

Siga $B$ un blossom d'una flower $F$ sobre un emparejamiento $M$ en un grafo $G$ llavors: $M$ és un emparejamiento màxim en $G$ si i solament si $M/B$ és un emparejamiento en $G/B$.

Descontracción

La part de la demostració més interessant de l'algoritme és provar que si $G/B(G^{\prime })$ té un camí m-incremente $p^{\prime }=(v_0\dots v_t)$ llavors $G$ té un camí m-incremente $p$ semblant a $p^{\prime }$.

Per a la demostració se separen varis casos:

1. El camí m-incremente en $G^{\prime }$ no conté cap vèrtiç fictici, llavors el grafo $G$ conté el mateix camine m-incremente sense modificació.
2. El camí m-incremente en $G^{\prime }$ conté a un vèrtiç fictici (sense pèrdua de generalitat), este a la seua volta es subdivide en dos casos:

1. 1. El vèrtiç fictici no es troba en un extrem del camine m-incremente $p^{\prime }$, llavors en $G$ trobarem el següent camine m-incremente $(v_0\to \dots \to w\to w^{\prime }\to \dots \to u^{\prime }\to u\to \dots \to v_t)$ , el camí m – alternatiu $(w^{\prime }\to \dots \to u^{\prime })$ existix com a conseqüència de la definició de blossom. Supongam que no existixca, açò seria si en algun moment no es pot alternar entre emparellat-no emparellat, l'única forma possible que ocórrega açò en un emparejamiento correcte és emparellat – no emparellat – no emparellat, açò per la definició de blossom no pot ocórrer ya que l'únic vèrtiç que pugues no estar emparellat en un dins del blossom és $u^{\prime }$, sino no es compliria que $M\cap E(B)$ siga un emparejamiento màxim en $B$. L'atre problema que poguera ocórrer és que en eixir del blossom per l'aresta $w^{\prime }-w$ trobem triat un camí que seleccionava com a aresta anterior a $w^{\prime }-w$ una que no pertany al emparejamiento, qüestió que no crearia un camí m-incremente, açò es resol triant l'atre camí possible de $u^{\prime }-w^{\prime }$ del blossom (existixen dos degut a que el blossom és un cicle).

1. 1. El vèrtiç fictici es troba en un extrem del camine m-incremente $p^{\prime }$, a on $v_t=v$, llavors en $G$ trobarem el següent camine m-incremente $v_0\to \dots \to u\to u^{\prime }\to \dots \to v^{\prime }$, el camí m – alternatiu $(u^{\prime }\to \dots \to v^{\prime })$ existix com a conseqüència de la definició de blossom (Vore el cas anterior). (Observació: este blossom no pot tindre cap vèrtiç emparellat en un exterior al blossom per lo tant queda un i solament un no saturat pel emparejamiento).