Emparejamiento (teoría de grafos)

El teorema de Kőnig establece que, en grafos bipartitos, el emparejamiento máximo tiene el mismo tamaño que la cobertura mínima de vértices . Gracias a este resultado, los problemas de cobertura mínima de vértices, conjunto independiente máximo y biclique máxima de vértices pueden resolverse en tiempo polinomial para grafos bipartitos.

El teorema de matrimonio de Hall proporciona una caracterización de los grafos bipartitos que tienen un emparejamiento perfecto, y el teorema de Tutte sobre emparejamientos perfectos proporciona una caracterización para grafos arbitrarios.

Hassani Monfared y Mallik dan una caracterización espectral del número de coincidencias de un grafo de la siguiente manera: Sea${\displaystyle G}$ser un gráfico en${\displaystyle n}$vértices y${\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0}$ser${\displaystyle k}$números imaginarios puros distintos de cero donde${\displaystyle 2k\leq n}$. Entonces el número correspondiente de${\displaystyle G}$es${\displaystyle k}$si y solo si (a) existe una matriz antisimétrica real${\displaystyle A}$con gráfico${\displaystyle G}$y valores propios${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}}$y${\displaystyle n-2k}$ceros, y (b) todas las matrices antisimétricas reales con gráfica${\displaystyle G}$tener como máximo${\displaystyle 2k}$autovalores distintos de cero . ^{[ 7 ]} Nótese que el gráfico (simple) de una matriz real simétrica o antisimétrica${\displaystyle A}$del orden${\displaystyle n}$tiene${\displaystyle n}$vértices y aristas dados por las entradas fuera de la diagonal no cero de${\displaystyle A}$.

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 la 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 emparejamiento máximo es una aproximación 2 de un emparejamiento máximo y también una aproximación 2 de un emparejamiento máximo mínimo. Esta desigualdad es precisa: por ejemplo, si G es un camino con 3 aristas y 4 vértices, el tamaño de un emparejamiento máximo mínimo es 1 y el de un emparejamiento máximo es 2.

Un problema fundamental en la optimización combinatoria es encontrar el emparejamiento máximo . Este problema cuenta con diversos algoritmos para diferentes clases de grafos.

En un grafo bipartito no ponderado , el problema de optimización consiste en encontrar un emparejamiento de cardinalidad máxima . El problema se resuelve mediante el algoritmo de Hopcroft-Karp en tiempo O ( √VE ) , y existen algoritmos aleatorios más eficientes , algoritmos de aproximación y algoritmos para clases especiales de grafos , como los grafos planares bipartitos , tal como se describe en el artículo principal.

En un grafo bipartito ponderado , el problema de optimización consiste en encontrar un emparejamiento de peso máximo; un problema dual consiste en encontrar un emparejamiento de peso mínimo. Este problema se suele denominar emparejamiento bipartito de peso máximo 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 camino más corto modificada en el algoritmo de camino de aumento. Si se utiliza el algoritmo de Bellman-Ford para este paso, el tiempo de ejecución del algoritmo húngaro se convierte en${\displaystyle O(V^{2}E)}$o el costo del borde se puede trasladar con un potencial para lograr${\displaystyle O(V^{2}\log {V}+VE)}$tiempo de ejecución con el algoritmo de Dijkstra y el montón de Fibonacci . ^{[ 8 ]}

En un grafo ponderado no bipartito , el problema de emparejamiento de peso máximo se puede resolver en tiempo ${\displaystyle O(V^{2}E)}$utilizando el algoritmo de floración de Edmonds .

Se puede encontrar un emparejamiento máximo con un algoritmo voraz simple . Un emparejamiento máximo también es un emparejamiento máximo, y por lo tanto es posible encontrar un emparejamiento máximo más grande en tiempo polinomial. También es posible encontrar un emparejamiento máximo con el uso de algoritmos rápidos de multiplicación de matrices en el tiempo${\displaystyle O({n^{\omega }})}$para${\displaystyle ~2.37\leq \omega <3}$^{[ 9 ]} . Sin embargo, no se conoce ningún algoritmo de tiempo polinomial para encontrar unemparejamiento máximo mínimo, es decir, un emparejamiento máximo que contenga elmenornúmero posible de aristas.

Un emparejamiento máximo con k aristas es un conjunto dominante de aristas con k aristas. Recíprocamente, si se nos da un conjunto dominante de aristas mínimo con k 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 dominante de aristas mínimo. ^{[ 10 ]} Se sabe que ambos problemas de optimización son NP-difíciles ; las versiones de decisión de estos problemas son ejemplos clásicos de problemas NP-completos . ^{[ 11 ]} Ambos problemas pueden aproximarse con un factor ^de 2 en tiempo polinomial: simplemente encontrar un emparejamiento máximo arbitrario M. [ ^{12 ]}

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. ^{[ 13 ]} También es #P-completo contar emparejamientos perfectos , incluso en grafos bipartitos , porque calcular el 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 biadyacencia . Sin embargo, existe un esquema de aproximación aleatoria de tiempo totalmente polinomial para contar el número de emparejamientos bipartitos. ^{[ 14 ]} Un teorema notable de Kasteleyn establece que el número de emparejamientos perfectos en un grafo planar se puede calcular exactamente en tiempo polinomial mediante el algoritmo FKT .

El número de emparejamientos perfectos en un grafo completo K _n (con n par) viene dado por el doble factorial ( n − 1)!!. ^{[ 15 ]} El número de emparejamientos en grafos completos, sin restringir que los emparejamientos sean perfectos, viene dado por los números de teléfono . ^{[ 16 ]}  

El número de emparejamientos perfectos en un grafo también se conoce como el hafniano de su matriz de adyacencia .

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

• Para grafos generales, un algoritmo determinista en tiempo${\displaystyle O(VE)}$y un algoritmo aleatorio en el tiempo${\displaystyle {\tilde {O}}(V^{2.376})}$. ^{[ 17 ] [ 18 ]}
• Para grafos bipartitos, si se encuentra un único emparejamiento máximo, se ejecuta un algoritmo determinista en tiempo${\displaystyle O(V+E)}$. ^{[ 19 ]}

El problema del desarrollo de un algoritmo en línea para emparejamiento fue considerado por primera vez por Richard M. Karp , Umesh Vazirani y Vijay Vazirani en 1990. ^{[ 20 ]}

En el entorno en línea, los nodos de un lado del grafo bipartito ("clientes") llegan de uno en uno y deben emparejarse inmediatamente con el otro lado del grafo ("servidores") o descartarse. Esta es una generalización natural del problema de la secretaria y tiene aplicaciones en subastas de anuncios en línea. Un algoritmo voraz simple es 1/2- competitivo . Para el caso de maximización no ponderada con un modelo de llegada aleatoria, Karp, Vazirani y Vazirani dieron un algoritmo aleatorio que alcanza una razón competitiva de 0,632 . El límite se mejoró posteriormente a 0,696 . ^{[ 21 ]} El problema también se estudió en un modelo donde los clientes pueden cambiar de servidor para mejorar el emparejamiento, y el objetivo es economizar en el número de cambios mientras se logra un emparejamiento máximo. ^{[ 22 ]}

• Una estructura de Kekulé de un compuesto aromático consiste en una correspondencia perfecta de su esqueleto de carbono , que muestra la ubicación 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 asignar dicha estructura. ^{[ 23 ]}
• 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 consiste en encontrar un emparejamiento perfecto de peso mínimo como subproblema.

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