Algoritmo de flor

En teoría de grafos , el algoritmo de flor es un algoritmo para construir coincidencias máximas en gráficos . El algoritmo fue desarrollado por Jack Edmonds en 1961, ^[1] y publicado en 1965. ^{[2] Dado un}gráfico general $G = (V, E)$ , el algoritmo encuentra una $M$ coincidente tal que cada vértice en $V$ incide como máximo con un borde en $M$ y $| METRO |$ está maximizado. La coincidencia se construye mejorando iterativamente una coincidencia vacía inicial a lo largo de rutas de aumento en el gráfico. A diferencia del emparejamiento bipartito , la nueva idea clave es que un ciclo de longitud impar en el gráfico (floración) se contrae a un solo vértice, y la búsqueda continúa de forma iterativa en el gráfico contraído.

El algoritmo se ejecuta en el tiempo $O (| E || V | 2)$ , donde $| mi |$ es el número de aristas del gráfico 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 principales razones por las que el algoritmo de la flor es importante es que proporcionó la primera prueba de que se puede 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 , produciendo un algoritmo para la coincidencia de peso mínimo . ^[4] Según lo elaborado por Alexander Schrijver , una mayor importancia del resultado proviene del hecho de que este fue el primer politopo cuya prueba de integralidad "no se deriva simplemente de la unimodularidad total , y su descripción fue un gran avance en la combinatoria poliédrica ". ^[5]

Caminos de aumento

Dado $G = (V, E)$ y una $M$ correspondiente de $G$ , un vértice $v$ queda expuesto si ningún borde 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 creciente $P$ es un camino alterno que comienza y termina en dos vértices expuestos distintos. Tenga en cuenta que el número de aristas no coincidentes en una ruta aumentada es mayor en uno que el número de aristas coincidentes y, por lo tanto, el número total de aristas en una ruta aumentada es impar. Un aumento coincidente a lo largo de una ruta de aumento $P$ es la operación de reemplazar $M$ con una nueva coincidencia.

M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)

Según el lema de Berge , la coincidencia $de M$ es máxima si y sólo si no hay una ruta de aumento $de M$ en $G.$ ^[6]^[7] Por lo tanto, la coincidencia es máxima o puede aumentarse. 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 más
A6 regresar MA7 finaliza si
A8 finaliza la función

Todavía tenemos que describir cómo se pueden encontrar caminos aumentantes de manera eficiente. La subrutina para encontrarlos utiliza flores y contracciones.

Flores y contracciones.

Dado $G = (V, E)$ y una $M$ coincidente 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 (el base ) es tal que existe un camino alterno de longitud par (el tallo ) desde $v$ hasta un vértice expuesto $w$ .

Encontrar flores:

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

Defina el gráfico contraído $G'$ como el gráfico obtenido de $G$ al contraer cada borde de $B$ , y defina la coincidencia contraída $M'$ como la coincidencia de $G'$ correspondiente a $M.$

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

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 florecen los vértices $u'$ y $w'$ y el lado de $B$ , $(u' \to \dots \to w')$ , que va de $u'$ a $w',$ se elige para garantizar que el nuevo camino siga alternando ( $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 trayectoria $u \to v B$ en $G'$ se reemplaza con el segmento $u \to (u' \to \dots \to v')$ en $G$ , donde florecen los vértices $u'$ y $v'$ y el lado de $B$ , $(u' \to \dots \to v')$ , que van de $u'$ a $v',$ se eligen para garantizar que el camino sea alterno ( $v'$ está expuesto, ). $\{u',u\}\en E\setminus M$

De este modo, se pueden contraer flores y realizar búsquedas en los gráficos contratados. Esta reducción está en el centro del algoritmo de Edmonds.

Encontrar un camino creciente

La búsqueda de una ruta aumentada utiliza una estructura de datos auxiliar que consiste en un bosque $F$ cuyos árboles individuales corresponden a porciones específicas del gráfico $G.$ De hecho, el bosque $F$ es el mismo que se usaría para encontrar coincidencias máximas en gráficos bipartitos (sin necesidad de encoger flores). En cada iteración, el algoritmo (1) encuentra una ruta de aumento, (2) encuentra una flor y recurre al gráfico 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$ incrementalmente según corresponda. Si $v$ está en un árbol $T$ del bosque, denotamos la root(v)raíz de $T.$ Si tanto $u$ como $v$ están en el mismo árbol $T$ en $F$ , denotamos distance(u,v)la longitud del camino único de $u$ a $v$ en $T$ .

 ENTRADA: Grafica G , haciendo coincidir M en G SALIDA: aumentando la ruta 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 desmarca todos los vértices y aristas en G , marca todas las aristas de M
B05 para cada vértice v expuesto. B06
crea un árbol singleton { v } y agrega el árbol a F
B07 finaliza para
B08 mientras haya un vértice v sin marcar en F con distancia (v, root(v)) incluso haga
B09 mientras exista un borde sin marcar e = { v , w } haga
B10 si  w no está en F  entonces // w coincide, así que agregue el borde coincidente de e y w a F
B11 x ← vértice coincidente con w en M
B12 agregue los bordes { v , w } y { w , x } al árbol de v
B13 de lo contrario
B14 si  la distancia (w, raíz (w)) es impar , entonces // Hacer nada.B15 else
B16 si  root(v) ≠ root(w)  entonces // Informar una ruta de aumento en F { e }. $\taza$ B17 P ← ruta ( raíz ( v ) → ... → v ) → ( w → ... → raíz ( w ))B18 return  P
B19 else // Contrae una flor en G y busca el camino en el gráfico contraído.B20 B ← flor formada por e y aristas en el camino v → w en T
B21 G', M' ← contrato G y M por B
B22 P' ← find_augmenting_path ( G' , M' )B23 P ← levantar P' a G
B24 regresar  P
B25 terminar si
B26 terminar si
B27 terminar si
B28 marcar el borde e
B29 terminar mientras
B30 marcar el vértice v
B31 terminar 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 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, localiza una ruta de aumento $P'$ en el gráfico contraído (línea B22) y la eleva al gráfico original (línea B23). Tenga en cuenta que la capacidad del algoritmo para contraer flores es crucial aquí; el algoritmo no puede encontrar $P$ directamente en el gráfico original porque en la línea B17 del algoritmo solo se consideran los bordes fuera del bosque entre los vértices a distancias iguales de las raíces.

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 se suma a un árbol $T$ en $F$ (línea B10) o 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 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 simplemente se pueden eliminar las líneas B20 – B24 del algoritmo. Por lo tanto, el algoritmo se reduce al algoritmo estándar para construir coincidencias de cardinalidad máxima en gráficos bipartitos ^[7] donde buscamos repetidamente una ruta de aumento mediante un simple recorrido del gráfico: este es, por ejemplo, el caso del algoritmo Ford-Fulkerson .

Emparejamiento ponderado

El problema de coincidencia se puede generalizar asignando pesos a las aristas en $G$ y solicitando un conjunto $M$ que produzca una coincidencia de peso total máximo (mínimo): este es el problema de coincidencia de peso máximo . Este problema puede resolverse mediante un algoritmo combinatorio que utiliza el algoritmo de Edmonds no ponderado como subrutina. ^[6] Kolmogorov proporciona una implementación eficiente en C++ de esto. ^[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". Poder. J. Matemáticas . 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 coincidencia máxima en gráficos generales" . XXI Simposio Anual sobre Fundamentos de la Informática. IEEE Computer Society Press, Nueva York. págs. 17-27.
^ Edmonds, Jack (1965). "Máxima coincidencia 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, Alejandro (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 coincidencia no bipartito de Edmonds", Notas del curso. UC Berkeley (PDF) , archivado desde el original (PDF) el 30 de diciembre de 2008
^ ab Tarjan, Robert, "Notas incompletas sobre el increíble algoritmo de flor que se encoge para la coincidencia general" de Edmonds, 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 coincidencia perfecta de costo mínimo", Computación de programación matemática , 1 (1): 43–67, doi :10.1007/s12532-009-0002-8