Algoritmo Blossom

Algoritmo para encontrar el máximo de coincidencias de gráficos

En teoría de grafos , el algoritmo Blossom es un algoritmo para construir emparejamientos máximos en grafos . El algoritmo fue desarrollado por Jack Edmonds en 1961, ^[1] y publicado en 1965. ^{[2] Dado un}grafo general $G = (V, E)$ , el algoritmo encuentra un emparejamiento $M$ tal que cada vértice en $V$ incida como máximo con una arista en $M$ y $| M |$ se maximice. El emparejamiento se construye mejorando iterativamente un emparejamiento vacío inicial a lo largo de caminos de aumento en el grafo. A diferencia del emparejamiento bipartito , la nueva idea clave es que un ciclo de longitud impar en el grafo (Blossom) se contrae a un solo vértice, y la búsqueda continúa iterativamente en el grafo contraído.

El algoritmo se ejecuta en un tiempo $O (| E || V | 2)$ , donde $| E |$ es el número de aristas del grafo y $| V |$ es su número de vértices . Se puede lograr un mejor tiempo de ejecución para la misma tarea con el algoritmo mucho más complejo de Micali y Vazirani. ^[3] $O(|E|{\sqrt {|V|}})$

Una de las razones principales por las que el algoritmo Blossom es importante es que proporcionó la primera prueba de que se podía encontrar una coincidencia de tamaño máximo utilizando una cantidad polinómica de tiempo de cálculo. Otra razón es que condujo a una descripción poliédrica de programación lineal del politopo coincidente , lo que produjo un algoritmo para la coincidencia de peso mínimo . ^[4] Como lo explicó Alexander Schrijver , una mayor importancia del resultado proviene del hecho de que este fue el primer politopo cuya prueba de integralidad "no se deduce simplemente de la unimodularidad total , y su descripción fue un gran avance en la combinatoria poliédrica ". ^[5]

Ampliando caminos

Dado $G = (V, E) y una$ $M$ coincidente de $G$ , un vértice $v$ está expuesto si ninguna arista de $M$ incide con $v$ . Un camino en $G$ es un camino alterno , si sus aristas están alternativamente no en $M$ y en $M$ (o en $M$ y no en $M$ ). Un camino de aumento $P$ es un camino alterno que comienza y termina en dos vértices expuestos distintos. Nótese que el número de aristas no coincidentes en un camino de aumento es mayor en uno que el número de aristas coincidentes y, por lo tanto, el número total de aristas en un camino de aumento es impar. Un aumento coincidente a lo largo de un camino de aumento $P$ es la operación de reemplazar $M$ con un nuevo camino coincidente

M_{1}=M\omás P=(M\setmenos P)\cup (P\setmenos M)

.

Por el lema de Berge , la coincidencia $M$ es máxima si y solo si no hay ninguna ruta de aumento $M en$ $G.$ ^[6]^[7] Por lo tanto, una coincidencia es máxima o puede ser aumentada. Por lo tanto , a partir de una coincidencia inicial, podemos calcular una coincidencia máxima aumentando la coincidencia actual con rutas de aumento siempre que podamos encontrarlas, y regresar cuando no queden rutas de aumento. Podemos formalizar el algoritmo de la siguiente manera:

 ENTRADA: Gráfico G , coincidencia inicial M en G SALIDA: coincidencia máxima M* en G Función
A1 find_maximum_matching ( G , M ) : M*
A2 P ← find_augmenting_path ( G , M )A3 si  P no está vacío entonces
A4 devuelve  find_maximum_matching ( G , aumenta M a lo largo de P )A5 de lo contrario
A6 regresa MA7 finaliza si
A8 finaliza función

Todavía tenemos que describir cómo se pueden encontrar rutas de aumento de manera eficiente. La subrutina para encontrarlas utiliza flores y contracciones.

Floraciones y contracciones

Dado $G = (V, E) y un$ $M$ correspondiente de $G$ , una flor $B$ es un ciclo en $G$ que consta de $2 k + 1$ aristas de las cuales exactamente $k$ pertenecen a $M$ , y donde uno de los vértices $v$ del ciclo (la base ) es tal que existe un camino alterno de longitud par (el tallo ) desde $v$ hasta un vértice expuesto $w$ .

Encontrando flores:

Recorrer el gráfico comenzando desde un vértice expuesto.
A partir de ese vértice, etiquételo como vértice externo $o$ .
Alterne el etiquetado entre los vértices que son internos $i$ y externos $o$ de modo que no haya dos vértices adyacentes que tengan la misma etiqueta.
Si terminamos con dos vértices adyacentes etiquetados como $o$ externo, entonces tenemos un ciclo de longitud impar y, por lo tanto, una floración.

Defina el grafo contraído $G'$ como el grafo obtenido a partir de $G$ al contraer cada arista de $B$ , y defina el grafo contraído coincidente $M'$ como el coincidente de $G'$ correspondiente a $M$ .

$G'$ tiene un camino de aumento $M'$ si y solo si $G$ tiene un camino de aumento $M'$ , y cualquier camino de aumento $M'$ $P'$ en $G'$ puede elevarse a un camino de aumento $M en$ $G$ deshaciendo la contracción por $B$ de modo que el segmento de $P'$ (si lo hay) que pasa por $v B$ se reemplaza por un segmento apropiado que pasa por $B.$ ^[8] En más detalle:

si $P'$ atraviesa un segmento $u \to v B \to w$ en $G'$ , entonces este segmento se reemplaza con el segmento $u \to (u' \to \dots \to w') \to w$ en $G$ , donde los vértices de flor $u'$ y $w'$ y el lado de $B$ , $(u' \to \dots \to w')$ , que van de $u'$ a $w'$ se eligen para asegurar que el nuevo camino aún sea alterno ( $u'$ está expuesto con respecto a , ). $M\cap B$ $\{w',w\}\en E\setminus M$

si $P'$ tiene un punto final $v B$ , entonces el segmento de ruta $u \to v B$ en $G'$ se reemplaza con el segmento $u \to (u' \to \dots \to v')$ en $G$ , donde los vértices de flor $u'$ y $v'$ y el lado de $B$ , $(u' \to \dots \to v')$ , que van de $u'$ a $v'$ se eligen para asegurar que la ruta sea alterna ( $v'$ está expuesto, ). $\{u',u\}\en E\setminus M$

De esta manera, las flores se pueden contraer y se pueden realizar búsquedas en los grafos contraídos. Esta reducción es el núcleo del algoritmo de Edmonds.

Encontrar un camino de ampliación

La búsqueda de una ruta de aumento utiliza una estructura de datos auxiliar que consiste en un bosque $F$ cuyos árboles individuales corresponden a porciones específicas del grafo $G.$ De hecho, el bosque $F$ es el mismo que se utilizaría para encontrar las máximas coincidencias en grafos bipartitos (sin necesidad de flores que se encogen). En cada iteración, el algoritmo (1) encuentra una ruta de aumento, (2) encuentra una flor y recurre al grafo contraído correspondiente, o (3) concluye que no hay rutas de aumento. La estructura auxiliar se construye mediante un procedimiento incremental que se analiza a continuación. ^[8]

El procedimiento de construcción considera los vértices $v$ y las aristas $e$ en $G$ y actualiza $F$ de forma incremental según corresponda. Si $v$ está en un árbol $T$ del bosque, denotamos root(v)la raíz de $T.$ Si tanto $u$ como $v$ están en el mismo árbol T $en$ F $,$ denotamos distance(u,v)la longitud de la ruta única de $u$ a $v$ en $T.$

 ENTRADA: Gráfico G , haciendo coincidir M en G SALIDA: ruta de ampliación P en G o ruta vacía si no se encuentra ningunaFunción
B01 find_augmenting_path ( G , M ) : P
B02 F ← bosque vacíoB03 desmarcar todos los vértices y aristas en G , marcar todas las aristas de M
B05 para cada vértice expuesto v  hacer
B06 crear un árbol singleton { v } y agregar el árbol a F
B07 fin para
B08 mientras haya un vértice sin marcar v en F con distancia(v, raíz(v)) par hacer
B09 mientras exista una arista sin marcar e = { v , w } hacer
B10 si  w no está en F  entonces // w coincide, por lo que agrega la arista coincidente de e y w a F
B11 x ← vértice coincidente con w en M
B12 agregar aristas { v , w } y { w , x } al árbol de v
B13 de lo contrario
B14 si  distancia(w, raíz(w)) es impar entonces //No hacer nada.B15 de lo contrario
B16 si  raíz(v) ≠ raíz(w)  entonces // Informar una ruta de aumento en F { e }. $\taza$ B17 P ← ruta ( raíz ( v ) → ... → v ) → ( w → ... → raíz ( w ))B18 devuelve  P
B19 de lo contrario // Contrae una flor en G y busca la ruta en el gráfico contraído.B20 B ← flor formada por e y aristas en el camino v → w en T
B21 G', M' ← contraen G y M por B
B22 P' ← find_augmenting_path ( G' , M' )B23 P ← elevar P' a G
B24 regresar  P
B25 fin si
B26 fin si
B27 fin si
B28 marcar arista e
B29 fin mientras
B30 marcar vértice v
B31 fin mientras
B32 regresar camino vacíoFunción final
B33

Ejemplos

Las siguientes cuatro figuras ilustran la ejecución del algoritmo. Las líneas discontinuas indican los bordes que actualmente no están presentes en el bosque. Primero, el algoritmo procesa un borde fuera del bosque que provoca la expansión del bosque actual (líneas B10 – B12).

A continuación, detecta una flor y contrae el gráfico (líneas B20 – B21).

Finalmente, ubica una ruta de aumento $P'$ en el grafo contraído (línea B22) y la eleva al grafo original (línea B23). Nótese que la capacidad del algoritmo para contraer los brotes es crucial aquí; el algoritmo no puede encontrar $P$ en el grafo original directamente porque solo se consideran los bordes fuera del bosque entre vértices a distancias iguales de las raíces en la línea B17 del algoritmo.

Análisis

El bosque $F$ construido por la find_augmenting_path()función es un bosque alterno. ^[9]

un árbol T en G es un árbol alterno con respecto a M , si
- $T$ contiene exactamente un vértice expuesto $r$ llamado raíz del árbol
- cada vértice a una distancia impar de la raíz tiene exactamente dos aristas incidentes en $T$ , y
- todos los caminos desde $r$ hasta las hojas en $T$ tienen longitudes pares, sus aristas impares no están en $M$ y sus aristas pares están en $M.$
un bosque F en G es un bosque alterno con respecto a M , si
- Sus componentes conectados son árboles alternos, y
- Cada vértice expuesto en $G$ es una raíz de un árbol alterno en $F.$

Cada iteración del bucle que comienza en la línea B09 agrega un árbol $T$ en $F$ (línea B10) o encuentra un camino de aumento (línea B17) o encuentra una flor (línea B20). Es fácil ver que el tiempo de ejecución es . $O(|E||V|^{2})$

Emparejamiento bipartito

Cuando $G$ es bipartito , no hay ciclos impares en $G.$ En ese caso, nunca se encontrarán flores y uno puede simplemente eliminar las líneas B20 – B24 del algoritmo. El algoritmo, por lo tanto, se reduce al algoritmo estándar para construir emparejamientos de cardinalidad máxima en grafos bipartitos ^[7] donde buscamos repetidamente un camino de aumento mediante un simple recorrido del grafo: este es, por ejemplo, el caso del algoritmo Ford–Fulkerson .

Coincidencia ponderada

El problema de emparejamiento se puede generalizar asignando pesos a las aristas en $G$ y pidiendo un conjunto $M$ que produzca un emparejamiento de peso total máximo (mínimo): este es el problema de emparejamiento de peso máximo . Este problema se puede resolver mediante un algoritmo combinatorio que utiliza el algoritmo de Edmonds no ponderado como subrutina. ^[6] Kolmogorov proporciona una implementación eficiente de esto en C++. ^[10]

Referencias

^ Edmonds, Jack (1991), "Un vistazo al cielo", en JK Lenstra; AHG Rinnooy Kan; A. Schrijver (eds.), Historia de la programación matemática --- Una colección de reminiscencias personales , CWI, Ámsterdam y Holanda Septentrional, Ámsterdam, págs. 32–54
^ Edmonds, Jack (1965). "Caminos, árboles y flores". Can. J. Math . 17 : 449–467. doi : 10.4153/CJM-1965-045-4 .
^ Micali, Silvio; Vazirani, Vijay (1980). Un algoritmo O(V ^1/2 E) para encontrar la máxima correspondencia en grafos generales . 21.° Simposio Anual sobre Fundamentos de la Ciencia de la Computación. IEEE Computer Society Press, Nueva York. pp. 17–27.
^ Edmonds, Jack (1965). "Máxima correspondencia y un poliedro con 0,1 vértices". Revista de investigación de la Oficina Nacional de Normas, sección B. 69 : 125–130. doi : 10.6028/jres.069B.013 .
^ Schrijver, Alexander (2003). Optimización combinatoria: poliedros y eficiencia. Algoritmos y combinatoria. Berlín Heidelberg: Springer-Verlag. ISBN 9783540443896.
^ ab Lovász, László ; Plummer, Michael (1986). Teoría del emparejamiento . Akadémiai Kiadó. ISBN 963-05-4168-8.
^ ab Karp, Richard, "Algoritmo de emparejamiento no bipartito de Edmonds", Notas del curso. UC Berkeley (PDF) , archivado desde el original (PDF) el 2008-12-30
^ ab Tarjan, Robert, "Notas esquemáticas sobre el increíble algoritmo de Edmonds Shrinking Blossom para la correspondencia general", Notas del curso, Departamento de Ciencias de la Computación, Universidad de Princeton (PDF)
^ Kenyon, Claire; Lovász, László , "Matemáticas discretas algorítmicas", Informe técnico CS-TR-251-90, Departamento de Ciencias de la Computación, Universidad de Princeton
^ Kolmogorov, Vladimir (2009), "Blossom V: Una nueva implementación de un algoritmo de emparejamiento perfecto de costo mínimo", Mathematical Programming Computation , 1 (1): 43–67, doi :10.1007/s12532-009-0002-8

[glimpse-1] Edmonds, Jack (1991), "Un vistazo al cielo", en JK Lenstra; AHG Rinnooy Kan; A. Schrijver (eds.), Historia de la programación matemática --- Una colección de reminiscencias personales , CWI, Ámsterdam y Holanda Septentrional, Ámsterdam, págs. 32–54

[algorithm-2] Edmonds, Jack (1965). "Caminos, árboles y flores". Can. J. Math . 17 : 449–467. doi : 10.4153/CJM-1965-045-4 .

[micali-3] Micali, Silvio; Vazirani, Vijay (1980). Un algoritmo O(V ^1/2 E) para encontrar la máxima correspondencia en grafos generales . 21.° Simposio Anual sobre Fundamentos de la Ciencia de la Computación. IEEE Computer Society Press, Nueva York. pp. 17–27.

[weighted-4] Edmonds, Jack (1965). "Máxima correspondencia y un poliedro con 0,1 vértices". Revista de investigación de la Oficina Nacional de Normas, sección B. 69 : 125–130. doi : 10.6028/jres.069B.013 .

[5] Schrijver, Alexander (2003). Optimización combinatoria: poliedros y eficiencia. Algoritmos y combinatoria. Berlín Heidelberg: Springer-Verlag. ISBN 9783540443896.

[matching_book-6] Lovász, László ; Plummer, Michael (1986). Teoría del emparejamiento . Akadémiai Kiadó. ISBN 963-05-4168-8.

[karp_notes-7] Karp, Richard, "Algoritmo de emparejamiento no bipartito de Edmonds", Notas del curso. UC Berkeley (PDF) , archivado desde el original (PDF) el 2008-12-30

[tarjan_notes-8] Tarjan, Robert, "Notas esquemáticas sobre el increíble algoritmo de Edmonds Shrinking Blossom para la correspondencia general", Notas del curso, Departamento de Ciencias de la Computación, Universidad de Princeton (PDF)

[kenyon_report-9] Kenyon, Claire; Lovász, László , "Matemáticas discretas algorítmicas", Informe técnico CS-TR-251-90, Departamento de Ciencias de la Computación, Universidad de Princeton

[blossom5-10] Kolmogorov, Vladimir (2009), "Blossom V: Una nueva implementación de un algoritmo de emparejamiento perfecto de costo mínimo", Mathematical Programming Computation , 1 (1): 43–67, doi :10.1007/s12532-009-0002-8