Combinación perfecta

En la teoría de grafos, una coincidencia perfecta en un gráfico es una combinación que cubre todos los vértices del gráfico. Más formalmente, dado un gráfico G = (V, E), una combinación 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 un borde en M.

Una combinación 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 coincidencia completa.

Toda coincidencia perfecta es una coincidencia de máxima cardinalidad, pero lo contrario no es cierto. Por ejemplo, considere los siguientes gráficos:

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 un emparejamiento de cardinalidad máxima (de tamaño 2) que no es perfecto, ya que algunos vértices no están emparejados.

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

Una combinación perfecta solo 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 solo 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 correspondencia casi perfecta. Si, para cada vértice en un gráfico, hay una coincidencia casi perfecta que omite solo ese vértice, el gráfico también se denomina factor crítico.

Caracterizaciones

El teorema del matrimonio de Hall proporciona una caracterización de grafos bipartitos que tienen una coincidencia perfecta.

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

Una coincidencia perfecta es un subgrafo regular de 1 que se expande, también conocido como 1 factor. En general, un subgrafo regular de expansión k es un factor k.

A espectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows: Vamos G{displaystyle G. ser un gráfico en n{displaystyle n} vértices y lambda _{2}>ldots >lambda _{frac {n}{2}}>0}" xmlns="http://www.w3.org/1998/Math/MathML">λ λ 1■λ λ 2■...... ■λ λ n2■0{displaystyle lambda ¿Por qué? {n}{2} {0}}lambda _{2}>ldots >lambda _{frac {n}{2}}>0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/526adf4348fde4e0ed6c4101af52e084cd56b9f5" style="vertical-align: -1.838ex; width:24.323ex; height:3.676ex;"/> Ser n2{fnMicroc} {n}{2}} distintos números no cero puramente imaginarios. Entonces... G{displaystyle G. tiene una combinación perfecta si y sólo si hay una matriz simétrica de skew real A{displaystyle A} con gráfico G{displaystyle G. y eigenvalues ± ± λ λ 1,± ± λ λ 2,...... ,± ± λ λ n2{displaystyle pm lambda _{1},pm lambda _{2},ldotspm lambda _{frac {n}{2}}. Tenga en cuenta que el gráfico (simple) de una matriz simétrica o simétrica real A{displaystyle A} de orden n{displaystyle n} tiene n{displaystyle n} vértices y bordes dados por los no cero fuera de las entradas diagonales de A{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 máxima de cardinalidad.

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 su matriz de biadyacencia.

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 a través del algoritmo FKT.

El número de combinaciones perfectas en un gráfico completo K_n (con n incluso) se da por el doble factorial: ()n− − 1)!!{displaystyle (n-1)}

Politopo a juego perfecto

El politopo de coincidencia perfecta de un grafo es un politopo en R^|E| en el que cada esquina es un vector de incidencia de un grafo perfecto. pareo.