En teoría de grafos , una coincidencia perfecta en un gráfico es una coincidencia que cubre todos los vértices del gráfico. Más formalmente, dado un gráfico G = ( V , E ) , una coincidencia perfecta en G es un subconjunto M del conjunto de aristas E , tal que cada vértice en el conjunto de vértices V es adyacente exactamente a una arista en M.
Una coincidencia perfecta también se denomina 1 factor ; consulte Factorización de gráficos para obtener una explicación de este término. En alguna literatura se utiliza el término emparejamiento completo .
Cada coincidencia perfecta es una coincidencia de máxima cardinalidad , pero lo contrario 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 combinación perfecta es también una funda de borde de tamaño mínimo . Si hay una coincidencia perfecta, entonces tanto el número coincidente como el número de cubierta de borde son iguales | V | / 2 .
Una coincidencia perfecta sólo puede ocurrir 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 coincide. Esto sólo puede ocurrir cuando el gráfico 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 gráfico, hay una coincidencia casi perfecta que omite solo ese vértice, el gráfico también se denomina factor crítico .
El teorema del matrimonio de Hall proporciona una caracterización de gráficos bipartitos que tienen una coincidencia perfecta.
El teorema de Tutte proporciona una caracterización de gráficas arbitrarias.
Una coincidencia perfecta es un subgrafo de 1 regular , también conocido como 1 factor . En general, un subgrafo k -regular que se extiende es un factor k .
Hassani Monfared y Mallik dan una caracterización espectral para que un gráfico tenga una coincidencia perfecta de la siguiente manera: Sea un gráfico en vértices pares y sean números puramente imaginarios distintos de cero . Entonces tiene una coincidencia perfecta si y solo si hay una matriz sesgada-simétrica real con gráfico y valores propios . [2] 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 distintas de cero de .
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 coincidencias perfectas, incluso en gráficos bipartitos , es #P-completo . Esto se debe a que 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 .
Un teorema notable de Kasteleyn establece que el número de coincidencias perfectas en un gráfico plano se puede calcular exactamente en tiempo polinomial 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 : [3]
Un gráfico con bordes coloreados 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]
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.
