En la teoría de grafos , un acoplamiento o coincidente (Inglés coincidencia ) de un gráfico es un conjunto de aristas del grafo que no tienen vértices comunes.
Es un gráfico simple no dirigido G = ( S , A ) (donde S es el conjunto de vértices y A el conjunto de aristas, que son algunos pares de vértices), un acoplamiento M es un conjunto de dos aristas a dos no adyacentes. Es decir, M es parte del conjunto A de aristas tal que
Un acoplamiento máximo es un acoplamiento que contiene el mayor número posible de bordes. Un gráfico puede tener un máximo de varios acoplamientos. Las siguientes imágenes muestran (en rojo) los acoplamientos máximos.
Un acoplamiento máximo es un acoplamiento M de la gráfica de tal manera que cualquier borde de la gráfica tiene al menos un extremo común con un borde de M . Esto es equivalente a decir en todos los acoplamientos de la gráfica M es máxima en el sentido de inclusión, es decir, que por cada borde tiene de A que no está en M , ya no hay un acoplamiento G . Las siguientes imágenes muestran los acoplamientos máximos.
Una correspondencia perfecta o acoplamiento completo es un acoplamiento M de la gráfica de tal manera que cada vértice del gráfico es incidente a exactamente un borde de M .
Un gráfico, incluso finito, no siempre tiene un acoplamiento perfecto (en particular, un gráfico que tiene un número impar de vértices no puede tener un acoplamiento perfecto). Cualquier acoplamiento perfecto es máximo y cualquier acoplamiento máximo es máximo (pero los recíprocos son falsos).
El teorema de Hall o lema de bodas da una condición necesaria y suficiente para la existencia de una correspondencia perfecta en un gráfico bipartito .
El teorema de König establece igual en un gráfico bipartito , el tamaño de la mínima transversal ( es decir, la cobertura mínima del vértice ) y el tamaño de la máxima coincidencia.
El teorema de Petersen establece que todo gráfico cúbico sin istmo tiene una correspondencia perfecta.
Es posible encontrar un acoplamiento cardinal máximo en tiempo polinomial en cualquier gráfico gracias al algoritmo de Edmonds . El caso especial de los gráficos bipartitos se puede resolver utilizando rutas crecientes o mediante el algoritmo Hopcroft-Karp . También se estudiaron heurísticas más rápidas y simples, con relaciones de aproximación un poco mejores que el 1/2 obtenido para cualquier acoplamiento máximo.
Dado un gráfico bipartito cuyas aristas se valoran, el problema de encontrar un acoplamiento de cardinalidad máxima y peso mínimo (o acoplamiento perfecto de peso mínimo) se denomina problema de asignación . Hay varios algoritmos para este problema, incluido el algoritmo húngaro .
Un acoplamiento se puede utilizar en problemas de asignación de tareas para tener la máxima eficiencia, por ejemplo, cada tarea se asigna a una sola máquina o viceversa . La búsqueda de un acoplamiento máximo en un gráfico bipartito también se denomina problema de asignación .
Los acoplamientos también se pueden utilizar para publicidad online dirigida y para comparar la estructura de las proteínas.
Un acoplamiento también se puede utilizar para resolver o abordar problemas más complejos como el del viajante de comercio con el algoritmo de Christofides .