El algoritmo de la flor es un algoritmo en teoría de grafos 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 coincidencia M tal que cada vértice en V incide como máximo un borde en M y | M | se maximiza. La coincidencia se construye mejorando iterativamente una coincidencia vacía inicial a lo largo de rutas de aumento en el gráfico. a diferencia decoincidencia bipartita , la nueva idea clave es que un ciclo de longitud impar en el gráfico (flor) se contrae a un solo vértice, con la búsqueda continuando iterativamente en el gráfico contraído.
El algoritmo corre a tiempo , dónde es el número de aristas del gráfico yes su número de vértices . Un mejor tiempo de ejecución depara la misma tarea se puede lograr con el algoritmo mucho más complejo de Micali y Vazirani. [3]
Una de las principales razones por las que el algoritmo de la flor es importante es que dio la primera prueba de que se podía encontrar una coincidencia de tamaño máximo utilizando una cantidad polinomial 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 , el significado adicional del resultado proviene del hecho de que este fue el primer politopo cuya prueba de integralidad "no se sigue simplemente de la unimodularidad total , y su descripción fue un gran avance en la combinatoria poliédrica ". [5]
Aumento de caminos
Dado G = ( V , E ) y un M de G coincidente , un vértice v está expuesto si ningún borde de M incide con v . Una ruta en G es una ruta alterna , si sus bordes alternativamente no están en M y en M (o en M y no en M ). Una ruta de aumento P es una ruta alterna que comienza y termina en dos vértices expuestos distintos. Tenga en cuenta que el número de bordes no coincidentes en un camino de aumento es mayor en uno que el número de bordes emparejados y, por lo tanto, el número total de bordes en un camino de aumento es impar. Un aumento de coincidencia a lo largo de una ruta de aumento P es la operación de reemplazar M con una nueva coincidencia.
Por el lema de Berge , igualando M es máximo si y sólo si no hay M camino -augmenting en G . [6] [7] Por lo tanto, una coincidencia es máxima o se puede aumentar. 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 siempre que 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 A1 función 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 si no A6 regresa MA7 finaliza si A8 finaliza la función
Todavía tenemos que describir cómo se pueden encontrar rutas de aumento de manera eficiente. La subrutina para encontrarlos usa flores y contracciones.
Flores y contracciones
Dado G = ( V , E ) y un M de G coincidente , una flor B es un ciclo en G que consta de 2k + 1 aristas de las cuales k pertenecen exactamente a M , y donde uno de los vértices v del ciclo (la base ) es tal que existe una trayectoria alterna de longitud uniforme (la raíz ) desde v hasta un vértice expuesto w .
Encontrar flores:
- Recorra el gráfico a partir de un vértice expuesto.
- A partir de ese vértice, etiquételo como un vértice externo " o " .
- Alterne el etiquetado entre los vértices que son la " i " interior y la " o " exterior de modo que no haya dos vértices adyacentes que tengan la misma etiqueta.
- Si terminamos con dos vértices adyacentes etiquetados como " o " externos, entonces tenemos un ciclo de longitud impar y, por lo tanto, una flor.
Definir el gráfico contraído G ' como la gráfica obtenida a partir de G por la contratación de cada borde de B , y definir el juego contraído M' como la coincidencia de G' corresponde a M .
G ' tiene un camino de aumento M' si y solo si G tiene un camino de aumento M , y que 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 manera que el segmento de P' (si los hay) que atraviesa a través de v B se sustituye por un desplazamiento de segmento adecuado a través de B . [8] Más detalladamente:
- si 'P atraviesa a través de un segmento u → v B → w en G' , a continuación, este segmento se sustituye con el segmento u → (u '→ ... → w') → w en G , donde flor vértices u' y w ' y el lado de B , (u' → ... → w ') , que van de u' a w ', se eligen para garantizar que la nueva ruta aún esté alternando ( u' está expuesta con respecto a, ).
- si P ' tiene un punto final v B , entonces el segmento de trayectoria u → v B en G' se reemplaza con el segmento u → (u '→ ... → v') en G , donde los vértices de flor u ' y v' y el lado de B , (u '→ ... → v') , que van de u ' a v' se eligen para garantizar que la ruta sea alterna ( v ' está expuesta,).
De esta forma se pueden contraer flores y realizar la búsqueda en los gráficos contratados. Esta reducción está en el corazón del algoritmo de Edmonds.
Encontrar un camino de aumento
La búsqueda de una trayectoria de aumento utiliza una estructura de datos auxiliar que consiste en un bosque F cuyos árboles individuales corresponden a porciones específicas de la gráfica 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 flores que se encogen). 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 vy las aristas e en G y actualiza gradualmente F según corresponda. Si v está en un árbol T del bosque, dejamos que la raíz (v) denota la raíz de T . Si ambos u y v son en el mismo árbol T en F , dejamos que la distancia (u, v) denota la longitud de la trayectoria única de u a v en T .
ENTRADA: Gráfico G , coincidencia de M en G SALIDA: aumento de 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 desmarque todos los vértices y aristas en G , marque todas las aristas de M
B05 para cada vértice expuesto v ¿
B06 cree un árbol singleton { v } y agregue el árbol a F
B07 final para
B08 mientras hay un vértice v sin marcar v en F con distancia? (v, raíz (v)) incluso hacer
B09 , mientras que existe un borde sin marcar e = { v , w } hacer
B10 si w no está en F entonces // w se corresponde, por lo que añadir e y w' s emparejado borde a F
B11 x ← vértice emparejado con w en M
B12 agregue las aristas { v , w } y { w , x } al árbol de v
B13 si no
B14 si la distancia (w, root (w)) es impar entonces // Hacer nada.B15 else
B16 si root (v) ≠ root (w) entonces // Reporta una ruta de aumento en F{ e }.B17 P ← ruta ( raíz ( v ) → ... → v ) → ( w → ... → raíz ( w ))B18 return P
B19 else // Contrae una flor en G y busque la ruta en el gráfico contraído.B20 B ← flor formada por e y aristas en la trayectoria v → w en T
B21 G ', M' ← contraer G y M por B
B22 P ' ← encontrar_camino_aumentado ( G' , M ' )B23 P ← levantar P ' a G
B24 volver P
B25 final si
B26 final si
B27 final si
B28 marcar borde e
B29 final mientras
B30 marcar vértice v
B31 final mientras
B32 devolver camino vacíoFunción final
B33
Ejemplos de
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 causa 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 trayectoria de aumento P ′ en el gráfico contraído (línea B22) y lo 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 en el gráfico original directamente porque solo los bordes fuera del bosque entre vértices a distancias pares de las raíces se consideran en la línea B17 del algoritmo.
Análisis
El bosque F construido por la función find_augmenting_path () 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 de r a las hojas en T tienen longitudes incluso, sus bordes extraños no están en M y sus bordes están incluso 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 expuesta en G es una raíz de un árbol alterna 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.
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 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 recorrido de gráfico simple: este es, por ejemplo, el caso del algoritmo de Ford-Fulkerson .
Coincidencia ponderada
El problema de emparejamiento se puede generalizar asignando pesos a los bordes en G y solicitando un conjunto M que produzca un emparejamiento del peso total máximo (mínimo): este es el problema de emparejamiento 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 C ++ eficiente de esto. [10]
Referencias
- ^ Edmonds, Jack (1991), "Un vistazo al cielo", en JK Lenstra; AHG Rinnooy Kan; A. Schrijver (eds.), History of Mathematical Programming --- A Collection of Personal Reminiscences , CWI, Amsterdam y North-Holland, Amsterdam, págs. 32-54
- ^ Edmonds, Jack (1965). "Caminos, árboles y flores". Lata. 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 coincidencia en gráficos generales . 21º 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 Normalización 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.
- ^ a b Lovász, László ; Plummer, Michael (1986). Teoría de emparejamiento . Akadémiai Kiadó. ISBN 963-05-4168-8.
- ^ a b Karp, Richard, "Algoritmo de emparejamiento no bipartito de Edmonds", Notas del curso. UC Berkeley (PDF) , archivado desde el original (PDF) el 30 de diciembre de 2008
- ^ a b Tarjan, Robert, "Notas incompletas sobre el increíble algoritmo de contracción de flores de Edmonds para emparejamiento 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 coincidencia perfecta de costo mínimo" , Computación de programación matemática , 1 (1): 43–67, doi : 10.1007 / s12532-009-0002-8