Emparejamiento (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 gráfico no dirigido es un conjunto de aristas sin vértices comunes . ^[1] En otras palabras, un subconjunto de aristas es una coincidencia si cada vértice aparece como máximo en una arista de esa coincidencia. 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 ), una M coincidente en G es un conjunto de aristas no adyacentes por pares , ninguna de las cuales es bucles ; es decir, no hay dos aristas que compartan vértices comunes.

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

Una coincidencia máxima es una coincidencia M de un gráfico G que no es un subconjunto de ninguna otra coincidencia. Una M coincidente de un gráfico 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 (rojo) en tres gráficos.

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

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. Una coincidencia es perfecta si |E|=|V|/2. Todo emparejamiento perfecto es máximo y, por tanto, máximo. En alguna literatura se utiliza el término emparejamiento completo . En la figura anterior, sólo la parte (b) muestra una coincidencia perfecta. Una combinación perfecta es también una funda 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 cobertura de borde mínima: . Un gráfico solo puede contener una coincidencia perfecta cuando el gráfico tiene un número par de vértices. ${\displaystyle \nu (G)\leq \rho (G)}$

Una coincidencia casi perfecta es aquella en la que exactamente un vértice no coincide. Claramente, un gráfico sólo puede contener una coincidencia casi perfecta cuando el gráfico 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 una coincidencia casi perfecta, entonces el gráfico se llama factor crítico .

Dada una coincidencia M , un camino alterno es un camino que comienza con un vértice no coincidente ^[3] y cuyas aristas pertenecen alternativamente a la coincidencia y no a la coincidencia. Una ruta aumentada es una ruta alterna que comienza y termina en vértices libres (inigualables). El lema de Berge establece que una coincidencia M es máxima si y sólo si no hay un camino creciente 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 coincidente y el número de cobertura del borde es igual al número de vértices. ^[5] Si hay una coincidencia perfecta, entonces tanto el número coincidente como el número de cubierta de borde son | V | / 2 .

Si A y B son dos coincidencias máximas, entonces | Un | ≤ 2| B | y | B | ≤ 2| Un | . 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 una coincidencia; 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 muestra 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ínima máxima 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: Sea un gráfico en vértices y sean 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áfica y valores propios y ceros, y (b) todas las matrices simétricas sesgadas reales con gráfica tienen como máximo valores propios distintos de cero . ^[6] Tenga en cuenta que el gráfico (simple) de una matriz de orden simétrica real o simétrica sesgada tiene vértices y aristas dadas por las entradas fuera de la diagonal no nulas 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}$

Polinomios coincidentes

Una función generadora del número de k coincidencias de aristas en un gráfico se llama polinomio coincidente. Sea G un gráfico y m _k el número de k coincidencias de aristas. Un polinomio coincidente de G es

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

Otra definición da el polinomio coincidente 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 cómo hacer coincidir polinomios.

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 de cardinalidad máxima . El problema se resuelve mediante el algoritmo 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 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 dual 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 aumentada. Si se utiliza el algoritmo Bellman-Ford para este paso, el tiempo de ejecución del algoritmo húngaro se vuelve , o el costo del borde se puede cambiar con el potencial de lograr el 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 coincidencia de peso máximo se puede resolver a tiempo utilizando el algoritmo de flor de Edmonds . ${\displaystyle O(V^{2}E)}$

Coincidencias máximas

Se puede encontrar una coincidencia máxima con un algoritmo codicioso simple . Una coincidencia máxima también es una coincidencia máxima y, por tanto, es posible encontrar una coincidencia máxima más grande en tiempo polinomial. Sin embargo, no se conoce ningún algoritmo de tiempo polinomial que encuentre una coincidencia máxima mínima , es decir, una coincidencia máxima que contenga el menor número posible de aristas.

Una coincidencia máxima con k aristas es un conjunto de aristas dominantes con k aristas. Por el contrario, si se nos da un conjunto dominante de aristas mínimas con k aristas, podemos construir una coincidencia máxima con k aristas en tiempo polinómico. 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. ^[8] Se sabe que estos dos problemas de optimización son NP-difíciles ; 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 polinómico: simplemente encuentre una coincidencia máxima arbitraria M. ^[10]

problemas de conteo

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áficas bipartitas. ^[11] También es #P-completo contar coincidencias perfectas , incluso en gráficos bipartitos , porque calcular el permanente de una matriz arbitraria 0–1 (otro problema #P-completo) es lo mismo que calcular el número de coincidencias perfectas en el gráfico bipartito que tiene la matriz dada como matriz de biaadyacencia . Sin embargo, existe un esquema de aproximación aleatoria en tiempo totalmente polinomial para contar el número de coincidencias bipartitas. ^[12] Un teorema notable de Kasteleyn establece que el número de coincidencias perfectas en un gráfico plano se puede calcular exactamente en tiempo polinómico mediante el algoritmo FKT .

El número de coincidencias perfectas en un gráfico completo K _n (con n par) viene dado por el factorial doble ( n  − 1)!!. ^[13] Los números de coincidencias en gráficos completos, sin obligar a que las coincidencias sean perfectas, vienen dados por los números de teléfono . ^[14]

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

Encontrar todos los bordes máximamente coincidentes

Uno de los problemas básicos en la teoría de coincidencias es encontrar en un gráfico dado todas las aristas que pueden extenderse hasta una coincidencia máxima en el gráfico (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})}$
• Para gráficos bipartitos, si se encuentra una coincidencia máxima única, 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 comparación fue considerado por primera vez por Richard M. Karp , Umesh Vazirani y Vijay Vazirani en 1990. ^[18]

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 . ^[19]

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 de vértices . A través de este resultado, los problemas de cobertura de vértice mínimo, conjunto independiente máximo y biclique 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

Emparejamiento en gráficos generales.

• La estructura Kekulé de un compuesto aromático consiste en una perfecta coincidencia de su esqueleto carbonado , mostrando 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 de teoría de grafos, un ciclo de 6 vértices) se le puede dar tal 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 combinación perfecta de peso mínimo como subproblema.

Emparejamiento en gráficos bipartitos

• El problema de graduación consiste en elegir un conjunto mínimo de clases a partir de los requisitos establecidos para la graduación.
• El problema del transporte de Hitchcock implica el emparejamiento bipartito como subproblema.
• El problema de isomorfismo de subárbol implica la coincidencia bipartita como subproblema.

Ver también

• Coincidencia en hipergráficos : una generalización de la coincidencia en gráficos.
• Coincidencia fraccionaria .
• 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 coincidencia perfecta si y sólo 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 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 sesgado-simétrico , 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 socios emparejados.
• Conjunto de vértices independiente , un conjunto de vértices (en lugar de aristas) de los cuales no hay dos adyacentes entre sí
• Problema de matrimonio estable (también conocido como problema de pareja 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 las aristas son independientes.
2. Alan Gibbons, Teoría algorítmica de grafos, Cambridge University Press, 1985, capítulo 5.
3. "Vista previa".
4. Cameron, Kathie (1989), "Emparejamientos inducidos", Número especial de la Primera Conferencia de Montreal sobre Combinatoria e Informática, 1987, Matemáticas aplicadas discretas , 24 (1–3): 97–102, doi : 10.1016/0166-218X( 92)90275-F , SEÑOR  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 coincidencias en gráficos, Álgebra lineal y sus aplicaciones 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004, https://doi.org/10.1016/j.laa.2016.02.004 //arxiv.org/abs/1602.03590
7. Fredman, Michael L.; Tarjan, Robert Endre (1987), "Montones de Fibonacci y sus usos en algoritmos de optimización de redes mejorados", Journal of the ACM , 34 (3): 596–615, doi : 10.1145/28869.28874 , S2CID  7904683
8. Yannakakis, Mihalis; Gavril, Fanica (1980), "Conjuntos dominantes de bordes en gráficos" (PDF) , Revista SIAM de Matemáticas Aplicadas , 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 integridad NP , WH Freeman, ISBN 0-7167-1045-5. El conjunto dominante de borde (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 del 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 , 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 dominante de borde mínimo y Coincidencia máxima mínima 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), "Coincidencias máximas 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. Algoritmos aleatorios para problemas de teoría de coincidencias", 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 de máxima coincidencia en un gráfico bipartito", Ciencias de la Computación Teórica , 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 ACM sobre Teoría de la Computación (STOC 1990) . págs. 352–358. doi :10.1145/100216.100262.
19. Mahdiano, Mahoma; 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 la ACM sobre teoría de la informática . págs. 597–606. doi : 10.1145/1993636.1993716 .
20. Véase, por ejemplo, Trinajstić, Nenad ; Klein, Douglas J.; Randić, Milán (1986), "Sobre algunos problemas resueltos y no resueltos de la teoría química de grafos", Revista Internacional de Química Cuántica , 30 (S20): 699–742, doi :10.1002/qua.560300762.

Otras lecturas

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, señor  0859549
2. 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-8{{citation}}: Mantenimiento CS1: 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 de optimización de redes mejorados", Journal of the ACM , 34 (3): 595–615, doi : 10.1145/28869.28874 , S2CID  7904683.
5. SJ Cyvin e Ivan Gutman (1988), Estructuras Kekule en hidrocarburos bencenoideos , Springer-Verlag
6. Marek Karpinski y Wojciech Rytter (1998), Algoritmos paralelos rápidos para problemas de coincidencia 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