Un emparejamiento selecciona aristas sin compartir extremos. Este modelo permite asignar personas a tareas, estudiantes a proyectos o recursos a solicitudes sin utilizar dos veces el mismo elemento.
Muchos problemas consisten en formar parejas compatibles: trabajadores con puestos, máquinas con operaciones o participantes con horarios. Un grafo representa las compatibilidades y un emparejamiento representa una selección sin conflictos.
El objetivo más común es encontrar la mayor cantidad de parejas simultáneas, aunque también existen variantes con pesos, preferencias o requisitos de estabilidad.
Un emparejamiento M es un subconjunto de aristas tal que ningún vértice aparece en más de una arista seleccionada.
El tamaño |M| es la cantidad de aristas seleccionadas, equivalente a la cantidad de parejas formadas.
Un vértice está emparejado si alguna arista de M incide en él. En caso contrario está libre o no saturado.
Cada arista del emparejamiento satura exactamente dos vértices. Por eso un emparejamiento de tamaño k contiene 2k vértices emparejados.
Un emparejamiento maximal no admite agregar directamente otra arista. Un emparejamiento máximo posee la mayor cantidad posible de aristas.
Una selección voraz puede quedar bloqueada en un resultado maximal pequeño aunque una reasignación permita formar más parejas.
Un emparejamiento es perfecto cuando cubre todos los vértices. Solo puede existir si la cantidad total de vértices es par.
En un grafo bipartito, ambas particiones deben tener la misma cantidad de vértices para que exista un emparejamiento perfecto, aunque esa condición por sí sola no es suficiente.
Avanza para incorporar cada vértice del conjunto izquierdo. La segunda iteración reasigna A mediante el camino alternante B–1–A–2 y aumenta el tamaño del emparejamiento.
Parejas actuales
Camino aumentante
Acción actual
Celeste indica el emparejamiento actual y verde el camino aumentante utilizado en la última iteración.
Un grafo bipartito divide sus vértices en dos conjuntos L y R, y todas las aristas conectan un vértice de L con uno de R.
Esta estructura representa naturalmente dos tipos de entidades y permite algoritmos de emparejamiento más sencillos que los necesarios en grafos generales.
Un camino alternante intercala aristas que no pertenecen al emparejamiento con aristas que sí pertenecen.
Recorrer una arista emparejada significa considerar la liberación de su pareja actual para buscarle otra opción.
Un camino aumentante es un camino alternante cuyos dos extremos están libres. Comienza y termina con aristas que no pertenecen a M.
Al invertir la pertenencia de todas sus aristas, se eliminan k aristas emparejadas y se agregan k + 1. El tamaño aumenta exactamente en uno.
El teorema de Berge caracteriza completamente la optimalidad:
Por tanto, buscar caminos aumentantes no es solo una estrategia de mejora: su ausencia certifica que el resultado es máximo.
En un grafo bipartito, el algoritmo de Kuhn procesa los vértices de L. Para cada uno ejecuta DFS tratando de encontrar un vértice libre en R o de reasignar recursivamente al ocupante actual.
function aumentar(u, grafo, parejaDerecha, visitado) {
if (visitado.has(u)) return false;
visitado.add(u);
for (const v of grafo[u]) {
if (parejaDerecha[v] === undefined ||
aumentar(parejaDerecha[v], grafo, parejaDerecha, visitado)) {
parejaDerecha[v] = u;
return true;
}
}
return false;
}function emparejamientoMaximo(grafo, izquierda) {
const parejaDerecha = {};
let cantidad = 0;
for (const u of izquierda) {
const visitado = new Set();
if (aumentar(u, grafo, parejaDerecha, visitado)) cantidad++;
}
const parejas = Object.entries(parejaDerecha).map(
([derecha, izquierda]) => ({ izquierda, derecha })
);
return { cantidad, parejas };
}El conjunto de visitados debe reiniciarse para cada nuevo vértice izquierdo, pero se comparte durante toda su búsqueda recursiva.
El emparejamiento bipartito puede convertirse en una red de flujo:
Cada unidad de flujo representa una pareja. Las capacidades unitarias impiden utilizar dos veces un mismo vértice.
Un grafo bipartito posee un emparejamiento que cubre todo L si y solo si cada subconjunto S de L tiene al menos |S| vecinos diferentes.
Si tres solicitantes solo pueden acceder entre todos a dos recursos, es imposible asignar un recurso distinto a cada uno.
Kuhn encuentra un camino aumentante por vez. Hopcroft-Karp usa BFS para organizar el grafo en capas y DFS para encontrar varios caminos aumentantes disjuntos dentro de una misma fase.
| Algoritmo | Idea | Complejidad |
|---|---|---|
| Kuhn | DFS desde cada vértice izquierdo | O(VE) |
| Hopcroft-Karp | Varios caminos mínimos por fase | O(E√V) |
En grafos generales pueden aparecer ciclos impares que complican la búsqueda de caminos aumentantes. El algoritmo de Edmonds contrae temporalmente ciertas estructuras llamadas flores o blossoms.
No debe aplicarse Kuhn directamente a un grafo no bipartito: su recursión depende de que las aristas siempre crucen entre L y R.
Si cada pareja tiene un beneficio o costo, maximizar la cantidad puede no ser suficiente. El emparejamiento de peso máximo busca maximizar la suma de pesos.
El problema de asignación bipartita ponderada puede resolverse con el algoritmo húngaro o mediante flujo de costo mínimo. Es una variante distinta del emparejamiento máximo no ponderado.
Los emparejamientos convierten restricciones de exclusividad en una estructura combinatoria precisa. Los caminos aumentantes permiten revisar asignaciones anteriores hasta obtener una solución máxima.
En el próximo tema estudiaremos coloración de grafos, donde asignaremos categorías a vértices adyacentes sin que entren en conflicto.