Emparejamiento de máxima cardinalidadEditar
Un problema fundamental en la optimización combinatoria es encontrar un emparejamiento máximo. Este problema tiene varios algoritmos para diferentes clases de grafos.
En un grafo bipartito no ponderado, el problema de optimización es encontrar un emparejamiento de máxima cardinalidad. El problema se resuelve con 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 bipartitos planares, como se describe en el artículo principal.
Emparejamiento de máximo pesoEditar
En un grafo bipartito ponderado, el problema de optimización es encontrar un emparejamiento de máximo peso; un problema dual es encontrar un emparejamiento de mínimo peso. Este problema suele llamarse emparejamiento bipartito máximo ponderado, o el 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 del camino más corto modificada en el algoritmo del 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 O ( V 2 E ) {\displaystyle O(V^{2}E)}
, o se puede desplazar el coste de la arista con un potencial para conseguir O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)}
tiempo de ejecución con el algoritmo de Dijkstra y el montón de Fibonacci.
En un grafo ponderado no bipartito, el problema de emparejamiento de pesos máximos puede resolverse en tiempo O ( V 2 E ) {\displaystyle O(V^{2}E)}
utilizando el algoritmo blossom de Edmonds.
Emparejamientos máximosEditar
Un emparejamiento máximo se puede encontrar con un simple algoritmo codicioso. Un emparejamiento máximo es también un emparejamiento maximal, y por lo tanto es posible encontrar un emparejamiento maximal más grande en tiempo polinomial. Sin embargo, no se conoce ningún algoritmo de tiempo polinómico para encontrar un emparejamiento maximal mínimo, es decir, un emparejamiento maximal que contenga el menor número posible de aristas.
Un emparejamiento maximal con k aristas es un conjunto dominante de aristas con k aristas. A la inversa, si se nos da un conjunto mínimo dominante de aristas con k aristas, podemos construir un emparejamiento maximal 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 mínimo dominante de aristas. Se sabe que estos dos problemas de optimización son NP-duros; las versiones de decisión de estos problemas son ejemplos clásicos de problemas NP-completos. Ambos problemas se pueden aproximar dentro del factor 2 en tiempo polinómico: basta con encontrar un emparejamiento máximo arbitrario M.
Problemas de recuentoEditar
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. También es #P-completo contar los emparejamientos perfectos, incluso en grafos bipartitos, porque 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 biadjacencia. Sin embargo, existe un esquema de aproximación aleatoria en tiempo polinomial para contar el número de emparejamientos bipartitos. Un notable teorema de Kasteleyn afirma que el número de emparejamientos perfectos en un grafo plano puede calcularse exactamente en tiempo polinómico mediante el algoritmo FKT.
¡El número de emparejamientos perfectos en un grafo completo Kn (con n par) viene dado por el doble factorial (n – 1)!!. El número de emparejamientos en grafos completos, sin restringir que los emparejamientos sean perfectos, viene dado por los números telefónicos.
Encontrar todas las aristas máximamente emparejablesEditar
Uno de los problemas básicos en la teoría de emparejamientos es encontrar en un grafo dado todas las aristas que pueden extenderse a un emparejamiento máximo en el grafo (tales aristas se llaman aristas máximamente emparejables, o aristas permitidas). Los algoritmos para este problema incluyen:
- Para los grafos generales, un algoritmo determinista en tiempo O ( V E ) {\displaystyle O(VE)}
y un algoritmo aleatorio en tiempo O ~ ( V 2,376 ) {\displaystyle {\tilde {O}(V^{2,376})}
.
- Para los grafos bipartitos, si se encuentra un único emparejamiento máximo, un algoritmo determinista se ejecuta en tiempo O ( V + E ) {\displaystyle O(V+E)}
.
Emparejamiento bipartito en líneaEditar
El problema de desarrollar un algoritmo en línea para el emparejamiento fue considerado por primera vez por Richard M. Karp, Umesh Vazirani y Vijay Vazirani en 1990.
En la configuración en línea, los nodos de un lado del grafo bipartito llegan de uno en uno y deben ser emparejados inmediatamente con el otro lado del grafo o descartados. Se trata de una generalización natural del problema del secretario y tiene aplicaciones a 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 aleatorio, alcanza un ratio competitivo de 0,696.