En la disciplina matemática de la teoría de grafos , un conjunto de aristas coincidentes o independientes en un grafo no dirigido es un conjunto de aristas sin vértices comunes . Encontrar una coincidencia en un gráfico bipartito puede tratarse como un problema de flujo de red .
Definiciones
Dado un gráfico G = ( V , E ), un M coincidente en G es un conjunto de bordes no adyacentes por pares , ninguno de los cuales son bucles ; es decir, no hay dos aristas que compartan un vértice común.
Un vértice coincide (o satura ) si es un punto final de una de las aristas de la coincidencia. De lo contrario, el vértice no tiene comparación .
Una coincidencia máxima es una coincidencia M de un gráfico G que no es un subconjunto de ninguna otra coincidencia. Un juego M de un gráfico G es máxima si cada borde en G tiene una intersección no vacía con al menos un borde en M . La siguiente figura muestra ejemplos de coincidencias máximas (rojo) en tres gráficos.
Una coincidencia máxima (también conocida como coincidencia de cardinalidad máxima [1] ) es una coincidencia que contiene el mayor número posible de aristas. Puede haber muchas coincidencias máximas. El número coincidente de una gráfica es el tamaño de una coincidencia máxima. Cada coincidencia máxima es máxima, pero no toda coincidencia máxima es una coincidencia máxima. La siguiente figura muestra ejemplos de coincidencias máximas en los mismos tres gráficos.
Una coincidencia perfecta es una coincidencia que coincide con todos los vértices del gráfico. Es decir, una coincidencia es perfecta si cada vértice del gráfico incide en un borde de la coincidencia. Toda combinación perfecta es máxima y, por tanto, máxima. En alguna literatura, se utiliza el término concordancia completa . En la figura anterior, solo la parte (b) muestra una combinación perfecta. Una combinación perfecta también es una cubierta de borde de tamaño mínimo . Por lo tanto, el tamaño de una coincidencia máxima no es mayor que el tamaño de una cubierta de borde mínima: ν (G) ≤ ρ (G) . Un gráfico solo puede contener una coincidencia perfecta cuando el gráfico tiene un número par de vértices.
Una coincidencia casi perfecta es aquella en la que exactamente un vértice no tiene coincidencia . Claramente, un gráfico solo puede contener una coincidencia casi perfecta cuando la gráfica tiene un número impar de vértices, y las coincidencias casi perfectas son coincidencias máximas. En la figura anterior, la parte (c) muestra una coincidencia casi perfecta. Si cada vértice no coincide con alguna coincidencia casi perfecta, entonces la gráfica se llama factor crítico .
Dada una M coincidente , una ruta alterna es una ruta que comienza con un vértice no coincidente [2] y cuyos bordes pertenecen alternativamente a la coincidencia y no a la coincidencia. Una ruta de aumento es una ruta alterna que comienza y termina en vértices libres (no coincidentes). Lema de Berge establece que una coincidencia M es máximo si y sólo si no hay una trayectoria de aumento con respecto a M .
Una coincidencia inducida es una coincidencia que es el conjunto de bordes de un subgrafo inducido . [3]
Propiedades
En cualquier gráfico sin vértices aislados, la suma del número coincidente y el número que cubre el borde es igual al número de vértices. [4] Si hay una coincidencia perfecta, tanto el número coincidente como el número de la cubierta del borde son | V | / 2 .
Si A y B son dos emparejamientos máximos, entonces | A | ≤ 2 | B | y | B | ≤ 2 | A | . Para ver esto, observe que cada borde en B \ A puede ser adyacente como máximo a dos bordes en A \ B porque A es una coincidencia; además, cada borde en A \ B es adyacente a un borde en B \ A por maximalidad de B , por lo tanto
Además deducimos que
En particular, esto muestra que cualquier emparejamiento máximo es una aproximación 2 de un emparejamiento máximo y también una aproximación 2 de un emparejamiento máximo mínimo. Esta desigualdad es estrecha: por ejemplo, si G es una ruta con 3 aristas y 4 vértices, el tamaño de una coincidencia máxima mínima es 1 y el tamaño de una coincidencia máxima es 2.
Hassani Monfared y Mallik dan una caracterización espectral del número coincidente de un gráfico de la siguiente manera: ser un gráfico en vértices, y ser distintos números puramente imaginarios distintos de cero donde. Entonces el número coincidente de es si y solo si (a) hay una matriz simétrica sesgada real con gráfico y valores propios y ceros, y (b) todas las matrices simétricas sesgadas reales con gráfico tener como máximo valores propios distintos de cero . [5] Tenga en cuenta que el gráfico (simple) de una matriz simétrica real o simétrica sesgada de orden posee vértices y aristas dadas por las entradas fuera de la diagonal no cero de .
Polinomios coincidentes
Una función generadora del número de coincidencias de k -edge en un gráfico se denomina polinomio de coincidencia. Sea G una gráfica y m k el número de coincidencias de k -edge. Un polinomio coincidente de G es
Otra definición da el polinomio coincidente como
donde n es el número de vértices en el gráfico. Cada tipo tiene sus usos; para obtener más información, consulte el artículo sobre polinomios coincidentes.
Algoritmos y complejidad computacional
Coincidencia de cardinalidad máxima
Un problema fundamental en la optimización combinatoria es encontrar una coincidencia máxima . Este problema tiene varios algoritmos para diferentes clases de gráficos.
En un gráfico bipartito no ponderado , el problema de optimización es encontrar una coincidencia máxima de cardinalidad . El problema se resuelve mediante el algoritmo de Hopcroft-Karp en el tiempo O ( √ V E ) , y existen algoritmos aleatorios , algoritmos de aproximación y algoritmos más eficientes para clases especiales de gráficos, como los gráficos planos bipartitos , como se describe en el artículo principal. .
Coincidencia de peso máximo
En un gráfico bipartito ponderado , el problema de optimización es encontrar una coincidencia de peso máximo; un problema doble es encontrar una coincidencia de peso mínimo. Este problema a menudo se denomina coincidencia bipartita ponderada máxima o problema de asignación . El algoritmo húngaro resuelve el problema de asignación y fue uno de los inicios de los algoritmos de optimización combinatoria. Utiliza una búsqueda de ruta más corta modificada en el algoritmo de ruta de aumento. Si se utiliza el algoritmo Bellman-Ford para este paso, el tiempo de ejecución del algoritmo húngaro se convierte en, o el costo de la ventaja se puede cambiar con un potencial para lograr tiempo de ejecución con el algoritmo de Dijkstra y el montón de Fibonacci . [6]
En un gráfico ponderado no bipartito , el problema de la correspondencia de peso máximo se puede resolver a tiempoutilizando el algoritmo de flores de Edmonds .
Emparejamientos máximos
Se puede encontrar una coincidencia máxima con un algoritmo codicioso simple . Una coincidencia máxima es también una coincidencia máxima y, por lo tanto, es posible encontrar una coincidencia máxima más grande en el tiempo polinomial. Sin embargo, no se conoce ningún algoritmo de tiempo polinomial para encontrar una coincidencia máxima mínima , es decir, una coincidencia máxima que contiene el menor número posible de aristas.
Una coincidencia máxima con k aristas es un conjunto que domina el borde con k aristas. Por el contrario, si se nos da un conjunto de dominio de aristas mínimo con k aristas, podemos construir una coincidencia máxima con k aristas en tiempo polinomial. Por lo tanto, el problema de encontrar una coincidencia máxima mínima es esencialmente igual al problema de encontrar un conjunto dominante de borde mínimo. [7] Se sabe que estos dos problemas de optimización son NP-hard ; las versiones de decisión de estos problemas son ejemplos clásicos de problemas NP-completos . [8] Ambos problemas se pueden aproximar dentro de factor de 2 en tiempo polinómico: simplemente encontrar un arbitraria máxima coincidencia M . [9]
Contando problemas
El número de coincidencias en un gráfico se conoce como índice de Hosoya del gráfico. Es # P-completo calcular esta cantidad, incluso para gráficos bipartitos. [10] También es # P-completo contar emparejamientos perfectos , incluso en gráficos bipartitos , porque calcular la permanente de una matriz arbitraria 0-1 (otro problema # P-completo) es lo mismo que calcular el número de emparejamientos perfectos en el gráfico bipartito tiene la matriz dada como su matriz de biadjacencia . Sin embargo, existe un esquema de aproximación aleatoria en el tiempo completamente polinomial para contar el número de emparejamientos bipartitos. [11] Un notable teorema de Kasteleyn establece que el número de emparejamientos perfectos en un gráfico plano se puede calcular exactamente en tiempo polinomial mediante el algoritmo FKT .
El número de emparejamientos perfectos en un gráfico completo K n (con n par) viene dado por el factorial doble ( n - 1) !!. [12] El número de coincidencias en gráficos completos, sin restringir las coincidencias a ser perfectas, viene dado por los números de teléfono . [13]
Encontrar todos los bordes que coincidan al máximo
Uno de los problemas básicos en la teoría de emparejamiento es encontrar en un gráfico dado todos los bordes que pueden extenderse a un emparejamiento máximo en el gráfico (tales bordes se denominan bordes de máxima coincidencia o bordes permitidos ). Los algoritmos para este problema incluyen:
- Para gráficos generales, un algoritmo determinista en el tiempo y un algoritmo aleatorio en el tiempo . [14] [15]
- Para gráficos bipartitos, si se encuentra una única coincidencia máxima, un algoritmo determinista se ejecuta en el tiempo . [dieciséis]
Emparejamiento bipartito en línea
El problema de desarrollar un algoritmo en línea para emparejar fue considerado por primera vez por Richard M. Karp , Umesh Vazirani y Vijay Vazirani en 1990. [17]
En la configuración en línea, los nodos de un lado del gráfico bipartito llegan uno a la vez y deben coincidir inmediatamente con el otro lado del gráfico o descartarse. Esta es una generalización natural del problema de la secretaria y tiene aplicaciones en las subastas de anuncios en línea. El mejor algoritmo en línea, para el caso de maximización no ponderada con un modelo de llegada aleatoria, alcanza una relación competitiva de 0,696 . [18]
Caracterizaciones
El teorema de Kőnig establece que, en gráficos bipartitos, la coincidencia máxima es igual en tamaño a la cobertura mínima del vértice . A través de este resultado, los problemas de cobertura de vértice mínima, conjunto independiente máximo y biclicua de vértice máximo se pueden resolver en tiempo polinomial para gráficos bipartitos.
El teorema del matrimonio de Hall proporciona una caracterización de gráficos bipartitos que tienen una coincidencia perfecta y el teorema de Tutte proporciona una caracterización de gráficos arbitrarios.
Aplicaciones
Coincidencia en gráficos generales
- Una estructura Kekulé de un compuesto aromático consiste en una combinación perfecta de su esqueleto de carbono , que muestra la ubicación de los dobles enlaces en la estructura química . Estas estructuras llevan el nombre de Friedrich August Kekulé von Stradonitz , quien demostró que al benceno (en términos teóricos de gráficos, un ciclo de 6 vértices) se le puede dar tal estructura. [19]
- El índice de Hosoya es el número de coincidencias no vacías más uno; se utiliza en investigaciones de química computacional y química matemática para compuestos orgánicos.
Coincidencia en gráficos bipartitos
- El problema de graduación se trata de elegir un conjunto mínimo de clases de los requisitos dados para la graduación.
- El problema del transporte de Hitchcock implica el emparejamiento bipartito como subproblema.
- El problema de isomorfismo de subárbol implica el emparejamiento bipartito como subproblema.
Ver también
- Coincidencia en hipergráficos : una generalización de la coincidencia en gráficos.
- Coincidencia fraccionada .
- Descomposición de Dulmage-Mendelsohn , una partición de los vértices de un grafo bipartito en subconjuntos de modo que cada borde pertenezca a una coincidencia perfecta si y solo si sus extremos pertenecen al mismo subconjunto
- Coloración de bordes , una partición de los bordes de un gráfico en coincidencias
- Preclusión de coincidencia , el número mínimo de bordes a eliminar para evitar que exista una coincidencia perfecta
- Coincidencia de arco iris , una coincidencia en un gráfico bipartito de color de borde sin colores repetidos
- Gráfico de simetría sesgada , un tipo de gráfico que se puede utilizar para modelar búsquedas de rutas alternas para coincidencias
- Emparejamiento estable , un emparejamiento en el que no hay dos elementos que se prefieran entre sí a sus compañeros emparejados
- Conjunto independiente de vértices, un conjunto de vértices (en lugar de bordes) de los cuales no hay dos adyacentes.
- Problema de matrimonio estable (también conocido como problema de emparejamiento estable)
Referencias
- ^ Alan Gibbons, Teoría de gráficos algorítmicos, Cambridge University Press, 1985, Capítulo 5.
- ^ http://diestel-graph-theory.com/basic.html
- ^ Cameron, Kathie (1989), "Emparejamientos inducidos", Número especial para la Primera Conferencia de Montreal sobre Combinatoria y Ciencias de la Computación, 1987, Matemáticas aplicadas discretas , 24 (1-3): 97-102, doi : 10.1016 / 0166-218X ( 92) 90275-F , MR 1011265
- ^ Gallai, Tibor (1959), "Über extreme Punkt- und Kantenmengen", Ann. Univ. Sci. Budapest. Secta Eötvös. Matemáticas. , 2 : 133-138.
- ^ Keivan Hassani Monfared y Sudipta Mallik, Teorema 3.6, Caracterización espectral de emparejamientos en gráficos, Álgebra lineal y sus aplicaciones 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004
- ^ Fredman, Michael L .; Tarjan, Robert Endre (1987), "Montones de Fibonacci y sus usos en algoritmos de optimización de red mejorados", Journal of the ACM , 34 (3): 596–615, doi : 10.1145 / 28869.28874
- ^ Yannakakis, Mihalis; Gavril, Fanica (1980), "Edge dominating sets in graphs" (PDF) , SIAM Journal on Applied Mathematics , 38 (3): 364–372, doi : 10.1137 / 0138030.
- ^ Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 0-7167-1045-5. El conjunto dominante de aristas (versión de decisión) se analiza bajo el problema del conjunto dominante, que es el problema GT2 en el Apéndice A1.1. La correspondencia mínima máxima (versión de decisión) es el problema GT10 en el Apéndice A1.1.
- ^ Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximación , Springer. El conjunto dominante de borde mínimo (versión de optimización) es el problema GT3 en el Apéndice B (página 370). La coincidencia mínima máxima (versión de optimización) es el problema GT10 en el Apéndice B (página 374). Consulte también Conjunto de dominio de borde mínimo y Coincidencia mínima máxima en el compendio web .
- ^ Leslie Valiant , La complejidad de los problemas de enumeración y confiabilidad , SIAM J. Comput., 8 (3), 410–421
- ^ Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V .; Vigoda, Eric (2008). "Acelerar el recocido simulado para los problemas de conteo combinatorio y permanente". Revista SIAM de Computación . 37 (5): 1429–1454. CiteSeerX 10.1.1.80.687 . doi : 10.1137 / 050644033 .
- ^ Callan, David (2009), Una encuesta combinatoria de identidades para el factorial doble , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.
- ^ Tichy, Robert F .; Wagner, Stephan (2005), "Problemas extremos para índices topológicos en química combinatoria" (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi : 10.1089 / cmb.2005.12.1004 , PMID 16201918.
- ^ Rabin, Michael O .; Vazirani, Vijay V. (1989), " Emparejamientos máximos en gráficos generales mediante aleatorización", Journal of Algorithms , 10 (4): 557–567, doi : 10.1016 / 0196-6774 (89) 90005-9
- ^ Cheriyan, Joseph (1997), "Aleatorizado algoritmos para problemas en la teoría de emparejamiento ", SIAM Journal on Computing , 26 (6): 1635–1655, doi : 10.1137 / S0097539793256223
- ^ Tassa, Tamir (2012), "Encontrar todos los bordes con máxima coincidencia en un gráfico bipartito", Ciencias de la computación teóricas , 423 : 50–58, doi : 10.1016 / j.tcs.2011.12.071
- ^ Karp, Richard M .; Vazirani, Umesh V .; Vazirani, Vijay V. (1990). "Un algoritmo óptimo para la coincidencia bipartita en línea" (PDF) . Actas del 22º Simposio Anual de ACM sobre Teoría de la Computación (STOC 1990) . págs. 352–358. doi : 10.1145 / 100216.100262 .
- ^ Mahdian, Mohammad; Yan, Qiqi (2011). "Emparejamiento bipartito en línea con llegadas aleatorias: un enfoque basado en LP fuertemente reveladores de factores". Actas del cuadragésimo tercer simposio anual de ACM sobre teoría de la computación . págs. 597–606. doi : 10.1145 / 1993636.1993716 .
- ^ Ver, por ejemplo, Trinajstić, Nenad ; Klein, Douglas J .; Randić, Milán (1986), "Sobre algunos problemas resueltos y no resueltos de la teoría de grafos químicos", International Journal of Quantum Chemistry , 30 (S20): 699–742, doi : 10.1002 / qua.560300762.
Otras lecturas
- Lovász, László ; Plummer, MD (1986), Teoría de emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2001), Introducción a los algoritmos (segunda ed.), MIT Press y McGraw-Hill, Capítulo 26, págs. 643–700, ISBN 0-262-53196-8CS1 maint: varios nombres: lista de autores ( enlace )
- András Frank (2004). Sobre el método húngaro de Kuhn - Un tributo desde Hungría (PDF) (Informe técnico). Grupo de Investigación Egerváry.
- Michael L. Fredman y Robert E. Tarjan (1987), "Montones de Fibonacci y sus usos en algoritmos de optimización de red mejorados", Journal of the ACM , 34 (3): 595–615, doi : 10.1145 / 28869.28874 .
- SJ Cyvin e Ivan Gutman (1988), Estructuras Kekule en hidrocarburos benzenoides , Springer-Verlag
- Marek Karpinski y Wojciech Rytter (1998), Algoritmos paralelos rápidos para problemas de correspondencia de gráficos , Oxford University Press, ISBN 978-0-19-850162-6
enlaces externos
- Una biblioteca de gráficos con implementación de coincidencia de cardinalidad máxima basada en Hopcroft – Karp y Push – Relabel