Combinación perfecta

Coincidencia que cubre cada nodo del gráfico

En teoría de grafos , una correspondencia perfecta en un grafo es una correspondencia que cubre cada vértice del grafo. Más formalmente, dado un grafo G = ( V , E ) , una correspondencia perfecta en G es un subconjunto M del conjunto de aristas E , de modo que cada vértice en el conjunto de vértices V es adyacente a exactamente una arista en M .

Una coincidencia perfecta también se denomina factor 1 ; consulte Factorización de gráficos para obtener una explicación de este término. En algunas publicaciones, se utiliza el término coincidencia completa .

Toda correspondencia perfecta es una correspondencia de máxima cardinalidad , pero lo opuesto no es cierto. Por ejemplo, considere los siguientes gráficos: ^[1]

En el gráfico (b) hay una coincidencia perfecta (de tamaño 3) ya que los 6 vértices coinciden; en los gráficos (a) y (c) hay una coincidencia de cardinalidad máxima (de tamaño 2) que no es perfecta, ya que algunos vértices no coinciden.

Una coincidencia perfecta es también una cubierta de borde de tamaño mínimo . Si hay una coincidencia perfecta, entonces tanto el número de coincidencias como el número de cubierta de borde son iguales | V | / 2 .

Una coincidencia perfecta solo puede ocurrir cuando el grafo tiene un número par de vértices. Una coincidencia casi perfecta es aquella en la que exactamente un vértice no coincide. Esto solo puede ocurrir cuando el grafo tiene un número impar de vértices, y dicha coincidencia debe ser máxima. En la figura anterior, la parte (c) muestra una coincidencia casi perfecta. Si, para cada vértice de un grafo, hay una coincidencia casi perfecta que omite solo ese vértice, el grafo también se llama factor crítico .

Caracterizaciones

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

El teorema de Tutte proporciona una caracterización para gráficos arbitrarios.

Una correspondencia perfecta es un subgrafo 1-regular que abarca, también conocido como 1-factor . En general, un subgrafo k -regular que abarca es un k -factor .

Hassani Monfared y Mallik dan una caracterización espectral para que un grafo tenga una correspondencia perfecta de la siguiente manera: Sea un grafo en vértices pares y sean números puramente imaginarios distintos de cero . Entonces tiene una correspondencia perfecta si y solo si hay una matriz antisimétrica real con grafo y valores propios . ^[2] 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 _{\frac {n}{2}}>0}$ ${\displaystyle {\frac {n}{2}}}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{\frac {n}{2}}}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle A}$

Cálculo

Decidir si un gráfico admite una coincidencia perfecta se puede hacer en tiempo polinomial , utilizando cualquier algoritmo para encontrar una coincidencia de cardinalidad máxima .

Sin embargo, contar el número de emparejamientos perfectos, incluso en grafos bipartitos , es #P-completo . Esto se debe a que 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 .

Un notable teorema de Kasteleyn establece que el número de coincidencias perfectas en un gráfico plano 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 (con n par) viene dado por el factorial doble : ^[3] ${\displaystyle (n-1)!!}$

Conexión con la coloración de gráficos

Un grafo con aristas coloreadas puede inducir una cantidad de coloraciones de vértices (no necesariamente adecuadas) igual a la cantidad de coincidencias perfectas, ya que cada vértice se cubre exactamente una vez en cada coincidencia. Esta propiedad ha sido investigada en física cuántica ^[4] y teoría de la complejidad computacional . ^[5]

Politopo de combinación perfecta

El politopo de coincidencia perfecta de un gráfico es un politopo en R ^|E| en el que cada esquina es un vector de incidencia de una coincidencia perfecta.

Véase también

• Combinación sin envidia
• Coincidencia de máxima cardinalidad
• Coincidencia perfecta en hipergrafos de alto grado
• Teoremas de tipo Hall para hipergrafos
• El problema único de correspondencia perfecta ^{[6] [7] [8]}

Referencias

1. Alan Gibbons, Teoría de grafos algorítmicos, Cambridge University Press, 1985, Capítulo 5.
2. 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
3. Callan, David (2009), Un estudio combinatorio de identidades para el factorial doble , arXiv : 0906.1317 , Bibcode :2009arXiv0906.1317C.
4. Mario Krenn, Xuemei Gu, Anton Zeilinger , Experimentos cuánticos y gráficos: Estados multipartidarios como superposiciones coherentes de emparejamientos perfectos, Phys. Rev. Lett. 119, 240403 – Publicado el 15 de diciembre de 2017
5. Moshe Y. Vardi , Zhiwei Zhang, Solución de problemas de emparejamiento perfecto de inspiración cuántica mediante restricciones booleanas híbridas basadas en el teorema de Tutte, arXiv:2301.09833 [cs.AI], IJCAI'23
6. Wang, Xiumei; Shang, Weiping; Yuan, Jinjiang (1 de septiembre de 2015). "Sobre gráficos con una correspondencia perfecta única". Gráficos y combinatoria . 31 (5): 1765–1777. doi :10.1007/s00373-014-1463-8. ISSN  1435-5914.
7. Hoang, Thanh Minh; Mahajan, Meena ; Thierauf, Thomas (2006). Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). "Sobre el problema de emparejamiento perfecto único bipartito". Autómatas, lenguajes y programación . Berlín, Heidelberg: Springer: 453–464. doi :10.1007/11786986_40. ISBN: 978-0-822-2-82 ... 978-3-540-35905-0.
8. Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V. (1985). Maheshwari, SN (ed.). "Algoritmos NC para gráficos de comparabilidad, gráficos de intervalos y pruebas de correspondencia perfecta única". Fundamentos de tecnología de software y ciencia informática teórica . Berlín, Heidelberg: Springer: 496–503. doi :10.1007/3-540-16042-6_28. ISBN 978-3-540-39722-9.