Correspondencia (teoría de grafos)

Conjunto de aristas sin vértices comunes

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 . ^[1] En otras palabras, un subconjunto de las aristas es coincidente si cada vértice aparece como máximo en una arista de esa coincidencia. Encontrar una coincidencia en un grafo bipartito puede tratarse como un problema de flujo de red .

Definiciones

Dado un grafo G = ( V ,  E ), una M coincidente en G es un conjunto de aristas no adyacentes por pares, ninguna de las cuales son bucles ; es decir, ninguna de las dos aristas comparte vértices comunes.

Un vértice está emparejado (o saturado ) si es un punto final de una de las aristas en la coincidencia. De lo contrario, el vértice no está emparejado (o no está saturado ).

Una coincidencia máxima es una coincidencia M de un grafo G que no es un subconjunto de ninguna otra coincidencia. Una coincidencia M de un grafo G es máxima si cada arista en G tiene una intersección no vacía con al menos una arista en M . La siguiente figura muestra ejemplos de coincidencias máximas (en rojo) en tres grafos.

Una coincidencia máxima (también conocida como coincidencia de máxima cardinalidad ^[2] ) es una coincidencia que contiene el mayor número posible de aristas. Puede haber muchas coincidencias máximas. El número de coincidencias de un grafo G es el tamaño de una coincidencia máxima. Toda 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 grafos. ${\displaystyle \nu (G)}$

Un emparejamiento perfecto es un emparejamiento que empareja todos los vértices del grafo. Es decir, un emparejamiento es perfecto si cada vértice del grafo incide en una arista del emparejamiento. Un emparejamiento es perfecto si . Todo emparejamiento perfecto es máximo y, por lo tanto, máximo. En alguna literatura, se utiliza el término emparejamiento completo . En la figura anterior, solo la parte (b) muestra un emparejamiento perfecto. Un emparejamiento perfecto también es una cobertura de aristas de tamaño mínimo . Por lo tanto, el tamaño de un emparejamiento máximo no es mayor que el tamaño de una cobertura de aristas mínima: ⁠ ⁠ . Un grafo solo puede contener un emparejamiento perfecto cuando el grafo tiene un número par de vértices. ${\displaystyle |M|=|V|/2}$ ${\displaystyle \nu (G)\leq \rho (G)}$

Una coincidencia casi perfecta es aquella en la que exactamente un vértice no tiene coincidencia. Claramente, un grafo solo puede contener una coincidencia casi perfecta cuando el grafo 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 tiene coincidencias casi perfectas, entonces el grafo se llama factor crítico .

Dado un M coincidente , un camino alterno es un camino que comienza con un vértice no coincidente ^[3] y cuyas aristas pertenecen alternativamente al coincidente y no al coincidente. Un camino de aumento es un camino alterno que comienza y termina en vértices libres (no coincidentes). El lema de Berge establece que un M coincidente es máximo si y solo si no hay un camino de aumento con respecto a M.

Una coincidencia inducida es una coincidencia que es el conjunto de bordes de un subgrafo inducido . ^[4]

Propiedades

En cualquier gráfico sin vértices aislados, la suma del número de coincidencias y el número de cobertura de aristas es igual al número de vértices. ^[5] Si hay una coincidencia perfecta, entonces tanto el número de coincidencias como el número de cobertura de aristas 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 arista en B  \  A puede ser adyacente a, como máximo, dos aristas en A  \  B porque A es un emparejamiento; además, cada arista en A  \  B es adyacente a una arista en B  \  A por maximalidad de B , por lo tanto

${\displaystyle |A\setminus B|\leq 2|B\setminus A|.}$

Además deducimos que

${\displaystyle |A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.}$

En particular, esto demuestra que cualquier coincidencia máxima es una aproximación 2 de una coincidencia máxima y también una aproximación 2 de una coincidencia máxima mínima. Esta desigualdad es estricta: por ejemplo, si G es un camino 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 de coincidencia de un grafo de la siguiente manera: Sea un grafo sobre vértices, y sean números puramente imaginarios distintos de cero donde . Entonces el número de coincidencia de es si y solo si (a) hay una matriz antisimétrica real con grafo y valores propios y ceros, y (b) todas las matrices antisimétricas reales con grafo tienen como máximo valores propios distintos de cero . ^[6] Nótese que el grafo (simple) de una matriz real simétrica o antisimétrica de orden tiene vértices y aristas dadas por las entradas fuera de la diagonal distintas de cero de . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0}$ ${\displaystyle k}$ ${\displaystyle 2k\leq n}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}}$ ${\displaystyle n-2k}$ ${\displaystyle G}$ ${\displaystyle 2k}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle A}$

Coincidencia de polinomios

Una función generadora del número de k aristas coincidentes en un grafo se denomina polinomio coincidente. Sea G un grafo y m _k el número de k aristas coincidentes. Un polinomio coincidente de G es

${\displaystyle \sum _{k\geq 0}m_{k}x^{k}.}$

Otra definición da el polinomio correspondiente como

${\displaystyle \sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},}$

donde n es el número de vértices del gráfico. Cada tipo tiene sus usos; para obtener más información, consulte el artículo sobre la correspondencia de polinomios.

Algoritmos y complejidad computacional

Coincidencia de máxima cardinalidad

Un problema fundamental en la optimización combinatoria es encontrar un emparejamiento máximo . Este problema tiene varios algoritmos para diferentes clases de grafos.

En un grafo bipartito no ponderado , el problema de optimización consiste en encontrar una correspondencia de cardinalidad máxima . El problema se resuelve mediante el algoritmo de Hopcroft-Karp en tiempo O ( √ V E ) , y existen algoritmos aleatorios más eficientes , algoritmos de aproximación y algoritmos para clases especiales de grafos, como los grafos bipartitos planares , 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 correspondencia de peso máximo; un problema dual es encontrar una correspondencia de peso mínimo. Este problema a menudo se llama correspondencia 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 aumentada. 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 del borde se puede cambiar con un potencial para lograr un tiempo de ejecución con el algoritmo de Dijkstra y el montón de Fibonacci . ^[7] ${\displaystyle O(V^{2}E)}$ ${\displaystyle O(V^{2}\log {V}+VE)}$

En un gráfico ponderado no bipartito , el problema de la correspondencia de pesos máxima se puede resolver en el tiempo utilizando el algoritmo Blossom de Edmonds . ${\displaystyle O(V^{2}E)}$

Coincidencias máximas

Se puede encontrar una correspondencia máxima con un algoritmo voraz simple . Una correspondencia máxima también es una correspondencia máxima y, por lo tanto, es posible encontrar una correspondencia máxima más grande en tiempo polinomial. Sin embargo, no se conoce ningún algoritmo en tiempo polinomial para encontrar una correspondencia máxima mínima , es decir, una correspondencia máxima que contenga la menor cantidad posible de aristas.

Un emparejamiento máximo con k aristas es un conjunto con k aristas que domina las aristas . Por el contrario, si se nos da un conjunto mínimo con k aristas que domina las aristas, podemos construir un emparejamiento máximo con k aristas en tiempo polinomial. Por lo tanto, el problema de encontrar un emparejamiento máximo mínimo es esencialmente igual al problema de encontrar un conjunto mínimo que domina las aristas. ^[8] 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 . ^[9] Ambos problemas se pueden aproximar dentro del factor 2 en tiempo polinomial: simplemente encuentre un emparejamiento máximo arbitrario M . ^[10]

Problemas de conteo

El número de emparejamientos en un grafo se conoce como el índice de Hosoya del grafo. Es #P-completo calcular esta cantidad, incluso para grafos bipartitos. ^[11] También es #P-completo contar emparejamientos perfectos , incluso en grafos 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 grafo bipartito que tiene la matriz dada como su matriz de biyacencia . Sin embargo, existe un esquema de aproximación aleatorizado en tiempo completamente polinomial para contar el número de emparejamientos bipartitos. ^[12] Un notable teorema de Kasteleyn establece que el número de emparejamientos perfectos en un grafo planar se puede calcular exactamente en tiempo polinomial a través del algoritmo FKT .

El número de emparejamientos perfectos en un grafo completo K _n (siendo n par) está dado por el factorial doble ( n  − 1)!!. ^[13] Los números de emparejamientos en grafos completos, sin restringir que los emparejamientos sean perfectos, están dados por los números de teléfono . ^[14]

El número de coincidencias perfectas en un gráfico también se conoce como el hafniano de su matriz de adyacencia .

Encontrar todos los bordes que coincidan al máximo

Uno de los problemas básicos de la teoría de emparejamiento es encontrar en un grafo dado todas las aristas que se pueden extender hasta una coincidencia máxima en el grafo (dichas aristas se denominan aristas de máxima coincidencia o aristas permitidas ). Los algoritmos para este problema incluyen:

• Para gráficos generales, un algoritmo determinista en el tiempo y un algoritmo aleatorio en el tiempo . ^{[15] [16]} ${\displaystyle O(VE)}$ ${\displaystyle {\tilde {O}}(V^{2.376})}$
• En el caso de gráficos bipartitos, si se encuentra una única coincidencia máxima, se ejecuta un algoritmo determinista en el tiempo . ^[17] ${\displaystyle O(V+E)}$

Emparejamiento bipartito en línea

El problema de desarrollar un algoritmo en línea para la correspondencia fue considerado por primera vez por Richard M. Karp , Umesh Vazirani y Vijay Vazirani en 1990. ^[18]

En el entorno en línea, los nodos de un lado del gráfico bipartito llegan de a uno por vez y deben ser emparejados inmediatamente con el otro lado del gráfico o descartados. 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 . ^[19]

Caracterizaciones

El teorema de König establece que, en grafos bipartitos, la correspondencia máxima es igual en tamaño a la cobertura mínima de vértices . Mediante este resultado, los problemas de cobertura mínima de vértices, conjunto independiente máximo y biclique máximo de vértices pueden resolverse en tiempo polinomial para grafos bipartitos.

El teorema del matrimonio de Hall proporciona una caracterización de los gráficos bipartitos que tienen un emparejamiento perfecto y el teorema de Tutte proporciona una caracterización de los gráficos arbitrarios.

Aplicaciones

Correspondencia en gráficos generales

• La estructura de Kekulé de un compuesto aromático consiste en una correspondencia perfecta de su esqueleto de carbono , que muestra las ubicaciones de los enlaces dobles en la estructura química . Estas estructuras reciben su nombre de Friedrich August Kekulé von Stradonitz , quien demostró que al benceno (en términos de teoría de grafos, un ciclo de 6 vértices) se le puede dar dicha estructura. ^[20]
• 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.
• El problema del cartero chino implica encontrar una correspondencia perfecta de peso mínimo como subproblema.

Correspondencia en gráficos bipartitos

• El problema de graduación consiste en elegir un conjunto mínimo de clases a partir de unos requisitos dados para graduarse.
• El problema de transporte de Hitchcock implica el emparejamiento bipartito como subproblema.
• El problema de isomorfismo de subárboles implica la correspondencia bipartita como subproblema.

Véase también

• Coincidencia en hipergrafos : una generalización de la coincidencia en gráficos.
• Coincidencia fraccional .
• Descomposición de Dulmage-Mendelsohn , una partición de los vértices de un gráfico bipartito en subconjuntos de modo que cada arista pertenece a una correspondencia perfecta si y solo si sus puntos finales 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 que se deben eliminar para evitar que exista una coincidencia perfecta
• Coincidencia de arcoíris , una coincidencia en un gráfico bipartito con colores de borde sin colores repetidos
• Gráfico antisimétrico , un tipo de gráfico que se puede utilizar para modelar búsquedas de rutas alternas para encontrar coincidencias
• Emparejamiento estable , un emparejamiento en el que no hay dos elementos que se prefieran entre sí antes que a sus socios emparejados.
• Conjunto de vértices independientes , un conjunto de vértices (en lugar de aristas) de los cuales ninguno de los dos es adyacente entre sí.
• Problema del matrimonio estable (también conocido como problema de emparejamiento estable)

Referencias

1. "is_matching". Documentación de NetworkX 2.8.2 . Consultado el 31 de mayo de 2022 . Cada nodo incide como máximo en un borde de la coincidencia. Se dice que los bordes son independientes.
2. Alan Gibbons, Teoría de grafos algorítmicos, Cambridge University Press, 1985, Capítulo 5.
3. "Vista previa".
4. Cameron, Kathie (1989), "Induced matchings", Número especial para la Primera Conferencia de Montreal sobre Combinatoria y Ciencias de la Computación, 1987, Discrete Applied Mathematics , 24 (1–3): 97–102, doi : 10.1016/0166-218X(92)90275-F , MR  1011265
5. Gallai, Tibor (1959), "Über extreme Punkt- und Kantenmengen", Ann. Univ. Ciencia. Budapest. Secta Eötvös. Matemáticas. , 2 : 133-138.
6. 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, https://arxiv.org/abs/1602.03590
7. Fredman, Michael L.; Tarjan, Robert Endre (1987), "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes", Journal of the ACM , 34 (3): 596–615, doi : 10.1145/28869.28874 , S2CID  7904683
8. Yannakakis, Mihalis; Gavril, Fanica (1980), "Conjuntos con aristas dominantes en grafos" (PDF) , SIAM Journal on Applied Mathematics , 38 (3): 364–372, doi :10.1137/0138030.
9. Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, ISBN 0-7167-1045-5El conjunto dominante de aristas (versión de decisión) se analiza en el problema del conjunto dominante, que es el problema GT2 en el Apéndice A1.1. La coincidencia mínima máxima (versión de decisión) es el problema GT10 en el Apéndice A1.1.
10. 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 aproximabilidad , SpringerEl conjunto mínimo de aristas dominantes (versión optimizada) es el problema GT3 del Apéndice B (página 370). La coincidencia mínima máxima (versión optimizada) es el problema GT10 del Apéndice B (página 374). Véase también Conjunto mínimo de aristas dominantes y Coincidencia mínima máxima en el compendio web.
11. Leslie Valiant , La complejidad de los problemas de enumeración y confiabilidad , SIAM J. Comput., 8(3), 410–421
12. Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V .; Vigoda, Eric (2008). "Aceleración del recocido simulado para problemas de conteo permanente y combinatorio". Revista SIAM de Computación . 37 (5): 1429-1454. CiteSeerX 10.1.1.80.687 . doi : 10.1137/050644033. S2CID  755231. 
13. Callan, David (2009), Un estudio combinatorio de identidades para el factorial doble , arXiv : 0906.1317 , Bibcode :2009arXiv0906.1317C.
14. 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.
15. Rabin, Michael O.; Vazirani, Vijay V. (1989), "Máximos emparejamientos en gráficos generales mediante aleatorización", Journal of Algorithms , 10 (4): 557–567, CiteSeerX 10.1.1.228.1996 , doi :10.1016/0196-6774(89)90005-9 
16. Cheriyan, Joseph (1997), "Algoritmos aleatorios para problemas en la teoría de emparejamiento", SIAM Journal on Computing , 26 (6): 1635–1655, doi :10.1137/S0097539793256223 ${\displaystyle {\widetilde {O}}(M(|V|))}$
17. Tassa, Tamir (2012), "Encontrar todos los bordes con máxima compatibilidad en un gráfico bipartito", Theoretical Computer Science , 423 : 50–58, doi : 10.1016/j.tcs.2011.12.071
18. Karp, Richard M. ; Vazirani, Umesh V. ; Vazirani, Vijay V. (1990). "Un algoritmo óptimo para el emparejamiento bipartito en línea" (PDF) . Actas del 22.º Simposio Anual de la ACM sobre Teoría de la Computación (STOC 1990) . págs. 352–358. doi :10.1145/100216.100262. ISBN 0-89791-361-2.
19. Mahdian, Mohammad; Yan, Qiqi (2011). "Emparejamiento bipartito en línea con llegadas aleatorias: un enfoque basado en LP con fuerte capacidad de revelación de factores". Actas del cuadragésimo tercer simposio anual de la ACM sobre teoría de la computación . págs. 597–606. doi : 10.1145/1993636.1993716 .
20. Véase, por ejemplo, Trinajstić, Nenad ; Klein, Douglas J.; Randić, Milan (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.

Lectura adicional

1. Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr.  0859549
2. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2001), Introducción a los algoritmos (segunda edición), MIT Press y McGraw–Hill, Capítulo 26, págs. 643–700, ISBN 0-262-53196-8{{citation}}: CS1 maint: varios nombres: lista de autores ( enlace )
3. András Frank (2004). Sobre el método húngaro de Kuhn: un homenaje desde Hungría (PDF) (Reporte técnico). Grupo de Investigación Egerváry.
4. Michael L. Fredman y Robert E. Tarjan (1987), "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes", Journal of the ACM , 34 (3): 595–615, doi : 10.1145/28869.28874 , S2CID  7904683.
5. SJ Cyvin & Ivan Gutman (1988), Estructuras de Kekule en hidrocarburos bencenoides , Springer-Verlag
6. Marek Karpinski y Wojciech Rytter (1998), Algoritmos paralelos rápidos para problemas de correspondencia de grafos , Oxford University Press, ISBN 978-0-19-850162-6

Enlaces externos

• Una biblioteca de gráficos con implementación de correspondencia de cardinalidad máxima basada en Hopcroft–Karp y Push–Relabel