Última lección del módulo, y cerramos con el problema más humano de todos: emparejar. Cada mañana Rutalia debe asignar repartidores a turnos y pedidos, y no todo el mundo puede con todo: quien va en bicicleta no cubre el Polígono, quien no tiene carné de moto no hace el turno exprés del Centro. En 03-05 dejamos la pista: la asignación es un flujo con capacidades 1. Aquí la desarrollamos con su teoría propia —grafos bipartitos, caminos alternantes y aumentantes—, implementamos el algoritmo clásico de emparejamiento máximo, presentamos el algoritmo húngaro para la versión con costes, y cerramos el círculo con la asignación óptima que en 02-01 resolvíamos con programación lineal. Al terminar, pasaremos revista al arsenal completo de grafos del módulo.

1. Grafos bipartitos y el test de bipartición con BFS
2. Emparejamientos: definiciones y el fracaso del voraz
3. Emparejamiento máximo vía flujo: la reducción explícita
4. Caminos alternantes y aumentantes: el algoritmo directo
5. Emparejamiento con pesos: el algoritmo húngaro y scipy
6. El arsenal de grafos del módulo 3, en una tabla

Un grafo es bipartito si sus vértices pueden dividirse en dos grupos L y R de modo que toda arista cruce de un grupo al otro (ninguna arista interna). El grafo repartidores–turnos es bipartito por construcción: las aristas solo unen personas con turnos compatibles, nunca persona con persona.

Caracterización clave: un grafo es bipartito si y solo si no contiene ciclos de longitud impar. Y el test es un BFS de 03-02 con un extra mínimo — pintar por niveles alternos y vigilar contradicciones:

Dos pruebas ilustrativas:

• La red canónica de Rutalia (03-01) no es bipartita: contiene el triángulo ALM–MER–CEN (ciclo de longitud 3, impar). El test lo detecta en cuanto el BFS intenta pintar el tercer vértice del triángulo.
• El grafo de compatibilidades de esta lección sí lo es, con L = repartidores y R = turnos. En general, el test sirve cuando la bipartición no viene dada (¿puedo dividir estas zonas en "pares/impares" para repartir en días alternos sin que dos zonas vecinas coincidan? — misma pregunta, mismo BFS).

Un emparejamiento (matching) M es un subconjunto de aristas sin vértices en común: nadie aparece en dos parejas. Vocabulario:

• Un vértice es libre si ninguna arista de M lo toca.
• M es máximo (maximum) si ningún emparejamiento tiene más aristas. Ojo con el falso amigo maximal: "no ampliable añadiendo aristas sueltas", que puede ser mucho peor.
• M es perfecto si no deja ningún vértice libre.

Instancia central de la lección — 4 repartidores, 4 turnos, compatibilidades por vehículo y zona (datos ficticios):

Prueba el enfoque voraz (asignar en orden a cada uno el primer turno libre): Ana→Norte, Bruno→Río, Carla→Sur… y Dani se queda sin turno, porque su única opción (Norte) está ocupada. Tres parejas y un emparejamiento maximal pero no máximo: existe uno perfecto. El voraz vuelve a fallar (02-02 nos vacunó), pero esta vez la reparación no exige backtracking exponencial: hay estructura que explotar.

Primera solución: cobrar el adelanto de 03-05. La reducción convierte el emparejamiento en un flujo:

• Fuente s → cada repartidor con capacidad 1.
• Repartidor → turno compatible, capacidad 1, dirigida hacia el turno.
• Cada turno → sumidero t, capacidad 1.

Tres observaciones de peso:

• Las capacidades 1 codifican "cada persona un turno, cada turno una persona"; la integralidad de Ford-Fulkerson (03-05) garantiza parejas enteras, no medias asignaciones.
• El flujo máximo (4) es el tamaño del emparejamiento máximo: hay asignación perfecta, el voraz simplemente no la encontraba.
• Con Edmonds-Karp sobre esta red el coste queda en O(n·m) para grafos bipartitos con capacidades unitarias (cada aumento suma 1 y hay a lo sumo n aumentos). Existe un algoritmo especializado más rápido (Hopcroft-Karp, O(m·√n)); mismo principio, aumentos por lotes.

La reducción funciona, pero merece la pena ver la maquinaria sin el disfraz de flujo, porque tiene nombre propio y teoría elegante. Dado un emparejamiento M:

• Un camino alternante alterna aristas fuera de M y dentro de M.
• Un camino aumentante es un camino alternante que empieza y termina en vértices libres.

Si existe un camino aumentante, se puede mejorar M: se invierten sus aristas (las que estaban fuera entran, las que estaban dentro salen) y el emparejamiento gana exactamente una pareja. En nuestro ejemplo, con el voraz atascado en 3, el camino aumentante es:

Dani (libre) — Norte (arista fuera de M) — Ana (pareja actual de Norte) — Centro (fuera de M, y Centro está libre).

Invertir: Dani–Norte entra, Ana–Norte sale, Ana–Centro entra. Resultado: 4 parejas. El teorema de Berge cierra la teoría: M es máximo si y solo si no existe ningún camino aumentante. Es el análogo exacto del "no hay camino aumentante en la residual" de 03-05 — de hecho, un camino aumentante de matching es un camino aumentante de flujo mirado sin la fuente ni el sumidero.

El algoritmo clásico (algoritmo de Kuhn) busca un camino aumentante desde cada repartidor libre con un DFS que "desaloja" recursivamente:

Cómo leer el DFS, que es el corazón del algoritmo:

• intenta(r, ...) pregunta: ¿puede r quedar emparejado? Recorre sus turnos compatibles; si uno está libre, hecho. Si está ocupado, pregunta recursivamente si el ocupante puede mudarse — eso es, literalmente, recorrer un camino alternante.
• vetados evita ciclos dentro de un mismo intento (cada turno se considera una vez por búsqueda), garantizando O(m) por repartidor: O(n·m) total.
• La cascada de reasignaciones al retornar True es la "inversión del camino aumentante" hecha código: cada nivel de la recursión reescribe una pareja.
• El resultado concreto (quién acaba con qué) puede variar con el orden de exploración; el tamaño del emparejamiento, nunca — Berge lo garantiza.

Importante acotar el terreno: todo lo anterior es para grafos bipartitos. En grafos generales (emparejar repartidores entre sí para rutas en tándem, por ejemplo) los ciclos impares complican los caminos alternantes y hace falta el algoritmo de Blossom de Edmonds — existe, es polinómico, y queda fuera del alcance del curso.

Hasta aquí, compatibilidad binaria: puede o no puede. La realidad de Rutalia es más fina: todos pueden con casi todo, pero a distinto coste (minutos desde la base de cada repartidor a la zona del turno). El problema pasa a ser el problema de asignación: emparejamiento perfecto de coste mínimo.

El algoritmo húngaro lo resuelve en O(n³). A nivel conceptual (suficiente para este curso):

1. Restar a cada fila su mínimo y a cada columna el suyo: los costes se vuelven ≥ 0 con al menos un 0 por fila y columna. Restar una constante a una fila no cambia qué asignación es óptima (todas las asignaciones usan exactamente una celda de esa fila) — solo cambia el valor.
2. Buscar un emparejamiento perfecto usando solo celdas 0: es exactamente un emparejamiento máximo bipartito sin pesos, ¡el algoritmo de la sección anterior!
3. Si no existe, un ajuste de potenciales crea nuevos ceros "bien orientados" y se repite. La teoría que lo justifica es la dualidad de programación lineal — el mismo fundamento del símplex que rozamos en 02-01: la asignación es un PL cuyo óptimo cae siempre en enteros.

En la práctica profesional no se implementa a mano; scipy lo trae listo (es la misma asignación óptima que en 02-01 planteábamos como PL, ahora con algoritmo especializado):

Óptimo: Ana→Centro (3), Bruno→Río (2), Carla→Sur (2), Dani→Norte (3) = 10 minutos de desplazamiento total. En esta instancia cada repartidor consigue su turno individualmente más barato — suerte que no siempre se da: con costes [[1, 2], [1, 5]] ambos quieren la primera columna, y el óptimo global (2 + 1 = 3) obliga al primero a ceder. Esa tensión entre óptimo individual y global es justo lo que el húngaro arbitra, y lo que el voraz "cada uno a su mínimo" no sabe resolver.

Para maximizar compatibilidad en vez de minimizar coste, basta linear_sum_assignment(matriz, maximize=True) (o negar la matriz): mismo algoritmo.

Módulo cerrado. Este es el arsenal completo, con la pregunta de negocio que responde cada pieza:

Y las deudas del curso, saldadas: el heap de 01-04 impulsó Dijkstra y Prim; el union-find de 01-04 sostuvo a Kruskal; la PD de 01-03 reapareció en Floyd-Warshall; el BFS de 03-02 late dentro de Edmonds-Karp y del test de bipartición; y la matriz de tiempos de 03-03 es la que alimentaba el TSP del módulo 2.

• Confundir maximal con máximo: el voraz de Ana/Bruno/Carla produce un emparejamiento maximal (no ampliable con una arista suelta) que deja a Dani en casa. Máximo exige caminos aumentantes; no te fíes de que "ya no puedo añadir nada".
• Aplicar el algoritmo de Kuhn a un grafo no bipartito: los ciclos impares rompen el argumento de los caminos alternantes y el resultado puede ser subóptimo sin aviso. Ejecuta antes es_bipartito; si falla, el problema es de emparejamiento general (Blossom) o de modelado.
• Olvidar el conjunto vetados por intento (o compartirlo entre intentos): sin él, el DFS puede ciclar; compartido entre repartidores, prohíbe reasignaciones legítimas y encoge el resultado.
• Resolver asignación con pesos probando permutaciones: n! otra vez (02-02). Para n = 15 ya es inviable; el húngaro lo hace en O(n³) exacto. Reserva la fuerza bruta para verificar en instancias mínimas.
• Matriz de costes no cuadrada en linear_sum_assignment: scipy la admite (asigna solo min(filas, columnas) parejas), pero interpreta que sobran recursos; si necesitas "turno sin cubrir = penalización", añade columnas ficticias con ese coste explícito. Modela, no dejes que la herramienta decida por ti.
• Consejo: ante cualquier problema de "quién con quién" (personas-tareas, furgonetas-rutas, pedidos-franjas), dibuja el grafo bipartito antes de programar. La mitad de las veces la solución es una reducción directa a lo que ya tienes de 03-05 o de esta lección.

1. Reparto en días alternos. Rutalia quiere dividir las 9 zonas del grafo canónico en dos grupos (reparto lunes/miércoles/viernes frente a martes/jueves/sábado) de forma que ninguna calle una dos zonas del mismo grupo. Usa es_bipartito para demostrar que es imposible, e identifica a mano un ciclo impar que lo certifique. ¿Bastaría eliminar una arista para que fuera posible?
2. La baja de última hora. En la instancia central, Carla causa baja y llega Elia, que solo puede cubrir Centro: compatibilidades Ana:{Norte, Centro}, Bruno:{Norte, Río}, Dani:{Norte}, Elia:{Centro}. ¿Existe asignación perfecta? Ejecuta matching_aumentante, y explica el resultado encontrando a mano el conjunto de repartidores cuyos turnos posibles "no dan de sí" (pista: teorema de Hall — un emparejamiento perfecto exige que todo grupo de k repartidores tenga al menos k turnos posibles en conjunto).
3. Asignación con incompatibilidades y costes. Combina las dos mitades de la lección: sobre la matriz de costes de la sección 5, impón que Dani no puede cubrir Sur ni Centro (vehículo inadecuado). Representa la prohibición con un coste muy grande (p. ej. 999) y resuelve con linear_sum_assignment. ¿Cambia la asignación óptima respecto a la versión sin restricciones?

Ejercicio 1:

Certificado a mano: el triángulo ALM–MER–CEN es un ciclo de longitud 3. Con dos grupos, dos de esos tres vértices caerían juntos y la calle entre ellos violaría la regla. Eliminar una arista de ese triángulo no basta en general: hay más ciclos impares (por ejemplo ALM–RIO–CEN–ALM? — ALM–RIO, RIO–CEN, CEN–ALM: otro triángulo). Habría que romper todos los ciclos impares, y aquí comparten aristas: quitar CEN–ALM elimina esos dos triángulos, pero queda el ciclo de 5 ALM–MER–CEN–HOS–?… la comprobación honesta es relanzar es_bipartito tras cada supresión. Moraleja: la bipartición es una propiedad global, no local.

Ejercicio 2:

No hay asignación perfecta: máximo 3. El certificado de Hall: el grupo {Ana, Dani, Elia} solo alcanza en conjunto los turnos {Norte, Centro} — 3 personas, 2 turnos posibles: alguien se queda fuera, elija como elija el algoritmo. Obsérvese la dualidad, ya familiar: cuando el emparejamiento no puede crecer, existe un "cuello de botella" estructural que lo certifica (aquí el conjunto deficiente de Hall; en 03-05 era el corte mínimo). Los buenos algoritmos no solo fallan: explican por qué.

Ejercicio 3:

La asignación no cambia: el óptimo original (Ana→Centro, Bruno→Río, Carla→Sur, Dani→Norte) ya evitaba las celdas ahora prohibidas, así que sigue costando 10. La técnica del "coste 999" es la forma estándar de mezclar restricciones duras con optimización blanda; verifica siempre que ninguna celda prohibida aparezca en la solución final (si aparece, no existía asignación factible y el 999 te lo está gritando).

El emparejamiento cierra el módulo uniendo casi todas sus piezas: el test de bipartición es un BFS de 03-02 con dos colores; el emparejamiento máximo es un flujo de 03-05 con capacidades 1, o directamente el algoritmo de caminos aumentantes, cuya garantía —el teorema de Berge— es hermana del max-flow min-cut; y la versión con costes, resuelta por el algoritmo húngaro o scipy.optimize.linear_sum_assignment, reencuentra la asignación óptima que en 02-01 formulábamos como programación lineal. Rutalia dispone ya de un arsenal completo sobre su red urbana: modelarla (03-01), recorrerla (03-02), encontrar rutas mínimas (03-03), construir infraestructura mínima (03-04), medir su caudal y sus cuellos de botella (03-05) y asignar a su gente de forma óptima (03-06). Hemos recorrido estructuras; el siguiente paso es otro músculo: buscar y ordenar dentro de los datos. Los catálogos de productos, los registros masivos de entregas y los históricos de rutas de Rutalia no son grafos sino volúmenes — millones de filas donde encontrar y ordenar rápido marca la diferencia. En el módulo 4 empezamos por la herramienta más afilada y más traicionera de todas: la búsqueda binaria y sus variantes (04-01).