Algoritmo de compresión de flores

El algoritmo Blossom es un algoritmo en la teoría de grafos para construir las coincidencias más grandes en gráficos. 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 M coincidente tal que cada vértice en V incide como máximo en una arista en M y | m | máximo. Se construye un emparejamiento mejorando iterativamente el emparejamiento vacío inicial a lo largo de rutas de gráficos crecientes. En contraste con la coincidencia bipartita , la nueva idea clave era comprimir un ciclo impar en un gráfico (flor) en un solo vértice y continuar la búsqueda iterativamente sobre el gráfico condensado.

La razón principal por la que el algoritmo de compresión de flores es importante es que proporcionó la primera prueba de que era posible encontrar la coincidencia más grande en tiempo polinomial. Otra razón es que el método conduce a la descripción de un politopo de programación lineal para un politopo coincidente, lo que conduce a un algoritmo de coincidencia de peso mínimo [3] . Como aclaró Alexander Schreiver , la importancia adicional del resultado se deriva del hecho de que este politopo fue el primero cuya prueba integral "no solo se derivó de la unimodularidad total , sino que su descripción fue un gran avance en la combinatoria de poliedros " [4] .

Rutas de aumento

Dado un grafo G =( V , E ) y una M coincidente para G , un vértice v está desnudo (no cubierto por la coincidencia) si no hay una arista en M que incida con v . Un camino en G es un camino alterno si sus aristas alternativamente no pertenecen a M y están contenidas en M. El camino de aumento P es una cadena alterna que comienza y termina con vértices desnudos. Tenga en cuenta que el número de vértices no emparejados en la ruta de aumento es mayor en uno que el número de aristas en la coincidencia y, por lo tanto, el número de aristas en la ruta de aumento es impar. El aumento de emparejamientos a lo largo del camino P es la operación de reemplazar el conjunto M con un nuevo emparejamiento . $M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)$

Por el lema de Berge , una coincidencia de M es máxima si y solo si no hay un camino de aumento de M en G [5] [6] . Por lo tanto, la coincidencia es la más grande o se puede aumentar. Por lo tanto, comenzando con algunas coincidencias, podemos calcular la coincidencia más grande incrementando la coincidencia actual con la ruta aumentada. El algoritmo se puede formalizar de la siguiente manera

ENTRADA: Gráfica G , coincidencia inicial M en G SALIDA: mayor coincidencia M* en G A1 función find_largest_matching ( G , M ) : M* A2 find_increasing_path ( G , M )

{\ estilo de visualización P \ flecha izquierda}

A3 si P no está vacío , entonces A4 devuelve find_greatest_match ( G , incrementa M a lo largo de P ) A5 más A6 volver M A7 finaliza si A8 finaliza la función

Necesitamos describir cómo se pueden construir eficientemente rutas de aumento. Su rutina de búsqueda utiliza flores y contracción.

Flores y constricción

Dado un grafo G =( V , E ) y una M coincidente de un grafo G , entonces la flor B es un ciclo en G que consta de 2k + 1 aristas de las cuales exactamente k pertenecen a M y tiene un vértice v ( base ) tal que hay una cadena alterna de longitud uniforme ( tallo ) desde v hasta un vértice desnudo w .

Encontrar flores:

Miramos a través del gráfico, comenzando desde la parte superior desnuda;
Partiendo de este vértice, lo marcamos como la " o " exterior ;
Etiquete alternativamente los vértices como " i " interior y " o " exterior para que no haya dos vértices adyacentes con la misma etiqueta;
Si terminamos con dos vértices adyacentes etiquetados como " o " exterior , tenemos un ciclo de longitud impar y, por lo tanto, una flor [7] .

Definimos un gráfico comprimido G' como el gráfico obtenido de G al contraer todos los bordes de la flor B , y definimos un emparejamiento comprimido M' como el emparejamiento del gráfico G' correspondiente a M.

G' tiene un camino creciente de M' si y solo si G tiene un camino creciente de M , y entonces cualquier camino P' creciente de M ' en G' puede elevarse a un camino creciente de M en G restaurando la flor B contraído anteriormente, de modo que el segmento del camino P' (si lo hay) que pasa por v B es reemplazado por un segmento adecuado que pasa por B [8] . Con más detalle:

Si P' pasa por un segmento en G' , entonces este segmento se reemplaza por un segmento en G , donde los vértices de la flor u' y w' y el lado de la flor B , de u' a w' se eligen de modo que el queda alternando camino nuevo ( u' desnuda en relación a , ). $u\to v_{B}\to w$ $u\to (u'\to \dots \to w')\to w$ ${\ estilo de visualización (u' \ a \ puntos \ a w')}$ $M\cap B$ $\{w',w\}\in E\setminus M$

Si P' tiene un destino v B , entonces el segmento de camino en G' es reemplazado por un segmento de camino en G , donde los vértices de la flor u' y v' y el lado de la flor B , de u' a v' , son elegido para que el camino sea alternado ( v' desnudo, ). $u\to v_{B}$ $u\to (u'\to \dots \to v')$ ${\ estilo de visualización (u' \ a \ puntos \ a v')}$ $\{u',u\}\in E\setminus M$

Luego, la flor se puede comprimir y la búsqueda puede continuar sobre los gráficos comprimidos. Esta compresión es el corazón del algoritmo de Edmonds.

Encontrar una ruta de aumento

La búsqueda de ruta de aumento utiliza una estructura de datos adicional, que es un bosque F , cuyos árboles individuales corresponden a partes del gráfico G . De hecho, el bosque F es el mismo que se utiliza para encontrar las coincidencias más grandes en grafos bipartitos (sin necesidad de contraer flores). En cada iteración, el algoritmo (1) encuentra una ruta de aumento, o (2) encuentra una flor y recurre a un gráfico comprimido, o (3) concluye que no hay una ruta de aumento. La estructura adicional se construye utilizando un procedimiento incremental, que se analiza a continuación [8] .

El procedimiento de construcción examina los vértices v y las aristas e del gráfico G y actualiza gradualmente F en consecuencia. Si v está en un árbol forestal T , usamos root(v) para denotar la raíz de T. Si tanto u como v se encuentran en el mismo árbol T en F , denotamos por distancia (u, v) la longitud del único camino de u a v en el árbol T.

ENTRADA: Grafique G , haciendo coincidir M con G SALIDA: Aumentando la ruta P a G o la ruta vacía si no se encuentra tal ruta B01 función find_increment_path ( G , M ): P B02 bosque vacío

{\ estilo de visualización F \ flecha izquierda}

B03 hacer todos los vértices y aristas sin etiquetar en G , etiquetar todas las aristas M B05 para cada vértice desnudo v hacer B06 crear un árbol a partir de un vértice { v } y agregar el árbol a F B07 final para B08 mientras haya un vértice v sin etiquetar en F con una distancia uniforme ( v, root(v)) haz B09 mientras haya una arista sin etiquetar e ={ v , w } haz B10 si w no está en F entonces // w está en la coincidencia, así que agrega la arista // cubriendo e y w en F B11 se empareja con el vértice w en M B12 agregue los bordes { v , w } y { w , x } al árbol para v B13 else B14 si distancia (w, root ( w )) es raro entonces

{\ estilo de visualización x \ flecha izquierda}

// hacer nada. B15 else B16 if root(v) ≠ root(w) then // Reportar la ruta de aumento en F .

{\displaystyle \taza \{e\))

Vía B17 ( )

{\ estilo de visualización P \ flecha izquierda}

root(v)\to \dots \to v)\to (w\to \dots \to root(w)

B18 return P B19 else // Contrae la flor a G y busca un camino en el gráfico comprimido. B20 la flor formada por e y los bordes del camino en T B21 encoger G y M al encoger la flor B B22 find_increasing_path B23 elevar P' a G B24 devolver P B25 terminar si B26 terminar si B27 terminar si B28 marcar el borde e B29 end while B30 marca el vértice v B31 end while B32 devuelve camino vacío

{\ estilo de visualización B \ flecha izquierda}

v\a w

{\ estilo de visualización G', M' \ flecha izquierda}

P'\flecha izquierda

{\ estilo de visualización (G', M')}

{\ estilo de visualización P \ flecha izquierda}

Función final B33

Ejemplos

Las siguientes cuatro figuras ilustran la ejecución del algoritmo. Las líneas punteadas muestran bordes que actualmente no están presentes en el bosque. Primero, el algoritmo procesa un borde que no pertenece al bosque, lo que conduce a la expansión del bosque actual (líneas B10 - B12).

Luego se quita la flor y se comprime el gráfico (líneas B20 - B21).

Finalmente, el algoritmo encuentra un camino de aumento P′ en el gráfico comprimido (línea B22) y lo eleva en el gráfico original (línea B23). Tenga en cuenta que la capacidad del algoritmo de contracción de flores es decisiva aquí. El algoritmo no puede encontrar P en el gráfico original directamente, ya que en la línea B17 del algoritmo solo se consideran los bordes que no son de bosque entre los vértices a una distancia uniforme de la raíz.

Análisis

El bosque F construido por find_increasing_path() es un bosque rayado [9] .

un árbol T en G es un árbol alterno con respecto a M si
- T contiene exactamente un vértice desnudo r , llamado raíz del árbol
- cualquier 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 pertenecen a M , pero sus aristas pares sí pertenecen a M.
un bosque F en G es un bosque rayado con respecto a M si
- sus componentes conectados son árboles alternos y
- cualquier vértice desnudo en G es una raíz en un árbol alterno en F .

Cada iteración del bucle, a partir de la línea B09, agrega un nodo al árbol T en F (línea B10), encuentra una ruta de aumento (línea B17) o encuentra una flor (línea B20). Es fácil ver que el tiempo de ejecución del algoritmo es . Micali y Vazirani [10] mostraron un algoritmo que construye la coincidencia más grande en el tiempo . $O(|E||V|^{2})$ $O(|E||V|^{1/2})$

Coincidencia bipartita

El algoritmo se reduce al algoritmo estándar para emparejar gráficos bipartitos [6] si G es bipartito . Dado que no hay ciclos impares en G en este caso , nunca se encontrarán las flores y simplemente puede eliminar las líneas B20 - B24 del algoritmo.

Coincidencia ponderada

El problema de emparejamiento se puede generalizar asignando pesos a los bordes del gráfico G. En este caso, la pregunta se hace sobre el conjunto M , lo que da una coincidencia con el peso total máximo (mínimo). El problema de coincidencia ponderada se puede resolver con un algoritmo combinatorio que utiliza el algoritmo de Edmonds no ponderado como subrutina [5] . Vladimir Kolmogorov dio una implementación eficiente de este algoritmo en C++ [11] .

Notas

↑ Edmonds, 1961 , págs. 32-54.
↑ Edmonds, 1965 , págs. 449-467.
↑ Edmonds, 1965 , págs. 125-130.
↑ Schrijver, 2003 .
↑ 1 2 Lovász, Plummer, 1986 .
↑ 12 Karpe , 2006 .
↑ Por construcción, " i " marca el comienzo de una arista desde M , por lo que el caso de encuentro de dos vértices adyacentes etiquetados como " i " es imposible.
↑ 12 Tarjan , 2002 .
↑ Kenyon, Lovász, 1990 .
↑ Micali, Vazirani, 1980 , págs. 17-27.
↑ Kolmogorov, 2009 , págs. 43-67.

Literatura

Alejandro Schrijver. Optimización Combinatoria: Poliedros y Eficiencia . - Berlín, Heidelberg: Springer-Verlag, 2003. - (Algoritmos y Combinatoria). — ISBN 9783540443896 .
Jack Edmonds. Un vistazo al cielo // Historia de la programación matemática: una colección de reminiscencias personales / JK Lenstra, AHG Rinnooy Kan, A. Schrijver. - CWI, Ámsterdam y Holanda Septentrional, Ámsterdam, 1961. - pp. 32-54.
Jack Edmonds. Caminos, árboles y flores // Can. J. Matemáticas.. - 1965. - T. 17 . — S. 449–467 . -doi : 10.4153 / CJM-1965-045-4 .
Jack Edmonds. Coincidencia máxima y un poliedro con 0,1 vértices // Revista de Investigación de la Oficina Nacional de Normas Sección B. - 1965. - T. 69 . — S. 125–130 .
László Lovász, Michael D. Plummer. Teoría del emparejamiento. - Akademiai Kiado, 1986. - ISBN 963-05-4168-8 .
Ricardo Karp. notas del curso Universidad de California en Berkeley . - 2006. Archivado el 30 de diciembre de 2008.
Roberto. Notas esquemáticas sobre el increíble algoritmo Shrinking Blossom de Edmonds para el emparejamiento general // Notas del curso-423: Teoría de los algoritmos . — Departamento de Ciencias de la Computación, Universidad de Princeton, 2002.
Claire Kenyon, László Lovász. Matemática discreta algorítmica // Informe técnico CS-TR-251-90, Departamento de informática, Universidad de Princeton. — 1990.
Blossom V: una nueva implementación de un algoritmo de coincidencia perfecta de costo mínimo // Computación de programación matemática. - 2009. - T. 1 , N º 1 . — págs. 43–67 .
Silvio Micali, Vijay Vazirani. Un algoritmo O (V 1/2 E) para encontrar la coincidencia máxima en gráficos generales // 21.er Simposio anual sobre fundamentos de la informática. - IEEE Computer Society Press, Nueva York, 1980. - P. 17-27.