Un acoplamiento es un conjunto de crestas de dos a dos independientes: no comparten picos.
Acoplamiento perfecto: Cada parte superior del gráfico está exactamente en una parada del acoplamiento
Un gráfico perfecto tiene un número par de picos (el recíproco no es cierto)
Un acoplamiento perfecto es un acoplamiento de tamaño máximo (imposible de ampliar, no se puede emparejar más), el recíproco no es cierto.
Ejemplo de uso: En una empresa de logística, los empleados tienen uno o más permisos que les permiten conducir un determinado tipo de vehículo. El problema se puede representar en un gráfico con los empleados y vehículos de la empresa como su parte superior. Para resolver el problema, entonces tienes que encontrar un emparejamiento de tamaño máximo.
Algoritmo gluttonoso para encontrar el acoplamiento máximo:
Paso 1: Una parada se selecciona al azar y se almacena en una copia del gráfico (izquierda)
Paso 2: Se eliminan las paradas de parada que son incidentales en ambas cumbres y otra parada se selecciona aleatoriamente
Paso 3: Las paradas de parada que son incidentales en ambos picos se eliminan, lo que resulta en el acoplamiento máximo
