El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Algoritmos de Flujo Máximo

Siguiente ►
►

Hasta ahora las aristas de Rutalia medían el coste de atravesarlas (minutos) o de construirlas (euros de fibra). Esta lección les da un tercer significado: capacidad — cuántos paquetes por hora pueden circular por cada calle. La pregunta cambia de naturaleza: ya no buscamos el mejor camino para una furgoneta, sino el caudal máximo que toda la flota puede sostener entre el almacén y un barrio en hora punta. Este es el problema del flujo máximo, uno de los grandes clásicos de los grafos, con una teoría preciosa (la red residual, el teorema max-flow min-cut) y un alcance sorprendente: al final veremos que hasta asignar repartidores a pedidos es, en secreto, un problema de flujo.

Contenido

  1. El problema de flujo: capacidades, conservación, fuente y sumidero
  2. La trampa voraz y la red residual: por qué hacen falta aristas de retroceso
  3. Ford-Fulkerson: el método de los caminos aumentantes
  4. Edmonds-Karp: Ford-Fulkerson con el BFS de 03-02
  5. La red de hora punta de Rutalia, resuelta paso a paso
  6. El teorema max-flow min-cut: el cuello de botella físico
  7. La asignación como flujo: adelanto de 03-06

El problema de flujo: capacidades, conservación, fuente y sumidero

Una red de flujo es un grafo dirigido donde cada arista (u, v) tiene una capacidad c(u, v) ≥ 0, con dos nodos distinguidos: la fuente s (donde el flujo nace) y el sumidero t (donde muere). Un flujo asigna a cada arista una cantidad f(u, v) cumpliendo:

  • Restricción de capacidad: 0 ≤ f(u, v) ≤ c(u, v). Por una calle de 8 paquetes/hora no pasan 9.
  • Conservación: en todo nodo salvo s y t, lo que entra es igual a lo que sale. Los cruces no fabrican ni almacenan paquetes.

El valor del flujo es lo que sale neto de s (equivalentemente, lo que llega a t). El problema del flujo máximo: encontrar el flujo de valor máximo.

Escenario Rutalia: es hora punta y el Centro Histórico (CEN) concentra los pedidos. Del Almacén (ALM) salen paquetes hacia CEN a través de la zona del Mercado (MER), el Puente del Río (RIO) y la Ciudad Universitaria (UNI). Las capacidades (paquetes/hora, estimadas por tráfico y número de furgonetas que admite cada eje, en el sentido útil de la hora punta) son:

graph LR
    ALM((ALM fuente)) -->|12| MER((MER))
    ALM -->|11| RIO((RIO))
    RIO -->|4| MER
    MER -->|7| UNI((UNI))
    MER -->|6| CEN((CEN sumidero))
    RIO -->|9| CEN
    UNI -->|8| CEN

Pregunta: ¿cuántos paquetes/hora puede inyectar Rutalia en el Centro? A ojo no es obvio: de ALM salen 12 + 11 = 23, a CEN entran 6 + 9 + 8 = 23… pero veremos que la respuesta real es 22, y que el límite no está ni en la salida ni en la llegada, sino en un corte intermedio.

La trampa voraz y la red residual: por qué hacen falta aristas de retroceso

Primer impulso: buscar un camino de s a t con capacidad libre, mandar todo lo posible, repetir. El problema es que una elección temprana puede bloquear combinaciones mejores. Ejemplo mínimo (sub-red con capacidades pequeñas para verlo claro):

  • ALM→MER: 8, ALM→RIO: 8, MER→CEN: 8, RIO→CEN: 8 y un atajo transversal MER→RIO: 6.
  • El óptimo es obvio: 8 por arriba (ALM→MER→CEN) y 8 por abajo (ALM→RIO→CEN) = 16, ignorando el atajo.
  • Pero supón que el primer camino explorado es ALM→MER→RIO→CEN y mandamos 6 por él. Ahora ALM→MER tiene 2 libres y RIO→CEN tiene 2 libres: los caminos directos solo aportan 2 + 2 = 4 más. Total 10. Atascados lejos de 16.

La solución es contable, no física: permitir deshacer decisiones. Se define la red residual: para cada arista con capacidad c y flujo f, la residual contiene:

  • la arista hacia delante con capacidad c − f (lo que aún cabe), y
  • una arista de retroceso v→u con capacidad f (lo que se puede cancelar).

En el ejemplo atascado, la red residual contiene RIO→MER con capacidad 6 (retroceso del atajo). El camino residual ALM→RIO→MER→CEN con cuello 6 "manda 6" que en realidad significa: 6 unidades nuevas entran por abajo hasta RIO, y 6 de las que giraban por el atajo hacia RIO se quedan arriba y siguen hacia CEN. Nadie circula marcha atrás: solo se reescribe la contabilidad. Total: 16. La avaricia inicial, corregida sin empezar de cero.

Un camino de s a t en la red residual se llama camino aumentante; su cuello de botella es la capacidad residual mínima de sus aristas.

Ford-Fulkerson: el método de los caminos aumentantes

El método de Ford-Fulkerson es exactamente ese bucle:

mientras exista un camino aumentante s -> t en la red residual:
    enviar por él tantas unidades como permita su cuello de botella
    actualizar la red residual (restar hacia delante, sumar retrocesos)
devolver el flujo acumulado

Propiedades clave:

  • Con capacidades enteras, cada iteración aumenta el flujo en ≥ 1, luego termina; y el flujo máximo resultante es entero (teorema de integralidad — será crucial en 03-06: "medio repartidor" no existe).
  • Coste: O(m) por iteración de búsqueda × número de iteraciones. Si los caminos se eligen mal, las iteraciones pueden ser hasta f* (el valor del flujo máximo): O(m · f*). Existe un ejemplo clásico con capacidades 1.000.000 y un atajo de capacidad 1 donde una elección perversa alterna 2 millones de caminitos de 1 unidad. "Ford-Fulkerson" es un método; falta fijar cómo se busca el camino.

Edmonds-Karp: Ford-Fulkerson con el BFS de 03-02

Edmonds-Karp concreta la elección: buscar siempre el camino aumentante con menos aristas, es decir, con el BFS de 03-02 sobre la red residual. Ese detalle acota las iteraciones en O(n·m) independientemente de las capacidades, dando coste total O(n · m²).

from collections import deque

def edmonds_karp(cap, s, t):
    """cap: {u: {v: capacidad}} DIRIGIDO. Devuelve (flujo_max, flujo, S_del_corte)."""
    # Red residual como dict anidado; incluye retrocesos inicializados a 0
    res = {u: {} for u in cap}
    for u in cap:
        for v, c in cap[u].items():
            res[u][v] = res[u].get(v, 0) + c
            res.setdefault(v, {}).setdefault(u, 0)   # arista de retroceso

    flujo_max = 0
    while True:
        # BFS en la red residual usando solo aristas con capacidad restante
        padre = {s: None}
        cola = deque([s])
        while cola and t not in padre:
            u = cola.popleft()
            for v, c_res in res[u].items():
                if v not in padre and c_res > 0:
                    padre[v] = u
                    cola.append(v)

        if t not in padre:                    # no hay camino aumentante: fin
            S = set(padre)                    # alcanzables en la residual
            return flujo_max, res, S

        # cuello de botella del camino encontrado
        cuello, v = float("inf"), t
        while padre[v] is not None:
            u = padre[v]
            cuello = min(cuello, res[u][v])
            v = u

        # actualizar la red residual a lo largo del camino
        v = t
        while padre[v] is not None:
            u = padre[v]
            res[u][v] -= cuello               # menos hueco hacia delante
            res[v][u] += cuello               # más margen de cancelación
            v = u
        flujo_max += cuello

Lectura guiada del código:

  • La red residual res unifica hueco y retroceso: res[u][v] es "cuánto más puedo empujar de u a v ahora mismo", tanto si (u,v) era una arista real como si es la sombra de una arista contraria.
  • El BFS es literalmente el de 03-02 con un filtro extra (c_res > 0) y parada temprana al alcanzar t; padre reconstruye el camino igual que entonces.
  • Al no haber camino, el conjunto padre (los alcanzables desde s en la residual) no es un subproducto: es la mitad S del corte mínimo, como veremos enseguida. El algoritmo regala el certificado de optimalidad.

La red de hora punta de Rutalia, resuelta paso a paso

HORA_PUNTA = {
    "ALM": {"MER": 12, "RIO": 11},
    "MER": {"UNI": 7, "CEN": 6},
    "RIO": {"MER": 4, "CEN": 9},
    "UNI": {"CEN": 8},
    "CEN": {},
}
f, res, S = edmonds_karp(HORA_PUNTA, "ALM", "CEN")
print(f)   # 22
print(S)   # {'ALM', 'RIO', 'MER'}

Secuencia de caminos aumentantes que encuentra Edmonds-Karp (BFS prioriza los cortos):

Iteración Camino aumentante Cuello Flujo acumulado
1 ALM→MER→CEN 6 6
2 ALM→RIO→CEN 9 15
3 ALM→MER→UNI→CEN 6 21
4 ALM→RIO→MER→UNI→CEN 1 22
5 (BFS no alcanza CEN) — 22

El flujo final por arista: ALM→MER 12/12, ALM→RIO 10/11, RIO→MER 1/4, MER→CEN 6/6, MER→UNI 7/7, RIO→CEN 9/9, UNI→CEN 7/8. Comprueba la conservación en MER: entran 12 + 1 = 13, salen 6 + 7 = 13 ✓. La iteración 4 es la red residual en acción: el paquete extra entra por el río y usa el atajo RIO→MER para alcanzar el hueco que quedaba en UNI→CEN.

El teorema max-flow min-cut: el cuello de botella físico

Un corte s-t es una partición de los nodos en (S, T) con s ∈ S y t ∈ T; su capacidad es la suma de capacidades de las aristas que van de S a T (solo ese sentido). Todo flujo debe atravesar cualquier corte, luego flujo máximo ≤ capacidad de cualquier corte. El resultado profundo es la igualdad:

Teorema max-flow min-cut: el valor del flujo máximo es exactamente la capacidad del corte mínimo.

Y la demostración es constructiva con lo que ya tenemos: cuando Edmonds-Karp se detiene, S = {alcanzables desde s en la residual} define un corte cuyas aristas S→T están todas saturadas (si tuvieran hueco, el BFS habría cruzado). Ese corte tiene capacidad = flujo actual, y como ningún flujo supera a ningún corte, ambos son óptimos a la vez. El algoritmo no solo da el número: da el certificado, igual que la cota del B&B en 02-03 certificaba el 35,22 del TSP.

En Rutalia: S = {ALM, RIO, MER}, T = {UNI, CEN}. Las aristas del corte mínimo son MER→UNI (7), MER→CEN (6) y RIO→CEN (9): 7 + 6 + 9 = 22. Interpretación física inmediata para el equipo de operaciones:

  • El límite de 22 paquetes/hora no está en la salida del almacén (23) ni en los accesos finales al Centro (23), sino en el anillo intermedio.
  • Si el ayuntamiento pregunta qué calles ampliar, la respuesta del teorema es quirúrgica: solo las del corte mínimo. Ampliar ALM→MER o UNI→CEN no añade ni un paquete; ampliar RIO→CEN en 1 sube el caudal a 23 (hasta que otro corte pase a ser el mínimo — recalcula tras cada cambio).

Nótese el paralelismo con 03-02: allí preguntábamos si un corte desconecta (conectividad); aquí, cuánto estrangula (capacidad). El flujo máximo es la versión cuantitativa de la robustez.

La asignación como flujo: adelanto de 03-06

La sorpresa final: el flujo máximo resuelve problemas donde no hay nada que "fluya". ¿Pueden asignarse 3 repartidores a 3 pedidos si cada repartidor solo puede atender ciertos pedidos (por zona, por tipo de vehículo)? Constrúyase esta red:

  • Fuente s → cada repartidor, capacidad 1 (cada uno atiende a lo sumo un pedido).
  • Repartidor → cada pedido compatible, capacidad 1.
  • Cada pedido → sumidero t, capacidad 1 (cada pedido lo sirve a lo sumo uno).

Cada unidad de flujo entera es una pareja repartidor-pedido, y el flujo máximo es el número máximo de asignaciones compatibles simultáneas. La integralidad de Ford-Fulkerson garantiza que la solución no parte repartidores en fracciones. Esta reducción —convertir un problema en otro ya resuelto— es una de las armas más elegantes de la algoritmia, y es exactamente el puente hacia la próxima lección: el emparejamiento en grafos bipartitos (03-06), donde la desarrollaremos con todo detalle y con sus algoritmos especializados.

Errores Comunes y Consejos

  • Omitir las aristas de retroceso: el error número uno. Sin ellas, el resultado depende del orden de exploración y puede quedarse corto (10 frente a 16 en nuestro ejemplo mínimo). Si tu "flujo máximo" cambia al reordenar vecinos, casi seguro que es esto.
  • Modelar la red como no dirigida: las capacidades de hora punta tienen sentido — una calle de doble sentido se modela como dos aristas dirigidas, cada una con su capacidad. Copiar el grafo de 03-01 sin dirigirlo produce respuestas sin significado.
  • Usar DFS para el camino aumentante con capacidades grandes: Ford-Fulkerson puro puede iterar millones de veces (el ejemplo del atajo de capacidad 1). El BFS de Edmonds-Karp acota las iteraciones sin depender de las capacidades. Para redes serias existen algoritmos mejores (Dinic, push-relabel); networkx.maximum_flow los trae de serie.
  • Leer el corte mínimo como "las aristas saturadas": hay aristas saturadas que no están en el corte mínimo (ALM→MER va a 12/12 y no está). El corte es S→T con S = alcanzables en la residual; la saturación es necesaria pero no suficiente.
  • Olvidar verificar la conservación al depurar: suma entradas y salidas de cada nodo intermedio. Es el assert más barato y delator de toda esta lección.
  • Consejo: dibuja siempre la red residual tras cada aumento en ejemplos pequeños. El momento "ajá" de esta lección es ver cómo un retroceso convierte una mala decisión en reversible.

Ejercicios

  1. Ampliación quirúrgica. Usando edmonds_karp, comprueba cuánto mejora el caudal de la red de hora punta si (a) ALM→MER pasa de 12 a 15, (b) RIO→CEN pasa de 9 a 11. Explica ambos resultados con el corte mínimo antes de ejecutar el código, y verifica.
  2. El peor corte del analista. Calcula a mano la capacidad de los cortes S = {ALM} y S = {ALM, MER, RIO, UNI} de la red de hora punta y comprueba que ambos superan 22. ¿Qué te dice esto sobre usar "lo que sale del almacén" como estimación de capacidad de reparto?
  3. Asignación exprés. Rutalia tiene 3 repartidores con compatibilidades: R1→{P1, P2}, R2→{P2}, R3→{P2, P3}. Monta la red de asignación (fuente, sumidero, capacidades 1) y calcula con edmonds_karp cuántos pedidos pueden servirse a la vez. ¿Hay asignación perfecta?

Soluciones

Ejercicio 1:

red_a = {u: dict(vs) for u, vs in HORA_PUNTA.items()}
red_a["ALM"]["MER"] = 15
print(edmonds_karp(red_a, "ALM", "CEN")[0])   # 22 -> no mejora nada

red_b = {u: dict(vs) for u, vs in HORA_PUNTA.items()}
red_b["RIO"]["CEN"] = 11
print(edmonds_karp(red_b, "ALM", "CEN")[0])   # 23 -> +1 (no +2)

(a) ALM→MER no pertenece al corte mínimo {MER→UNI, MER→CEN, RIO→CEN}: ampliarla es tirar el dinero, el estrangulamiento sigue aguas abajo. (b) RIO→CEN sí está en el corte: ampliar en 2 sube el corte a 24, pero entonces manda otro límite (con 23 se satura la salida ALM: 12+11) y solo se gana 1. Los cortes se relevan: tras cada obra hay que recalcular.

Ejercicio 2:

  • S = {ALM}: aristas ALM→MER (12) + ALM→RIO (11) = 23.
  • S = {ALM, MER, RIO, UNI}: aristas hacia T = {CEN}: MER→CEN (6) + RIO→CEN (9) + UNI→CEN (8) = 23.

Ambos cortes valen 23 > 22: son cotas superiores válidas pero no ajustadas. Moraleja: la capacidad de salida del almacén (o de entrada al barrio) es una estimación optimista del caudal real; el verdadero límite puede esconderse en cualquier corte intermedio, y solo el flujo máximo lo encuentra con certificado.

Ejercicio 3:

ASIGNACION = {
    "s": {"R1": 1, "R2": 1, "R3": 1},
    "R1": {"P1": 1, "P2": 1},
    "R2": {"P2": 1},
    "R3": {"P2": 1, "P3": 1},
    "P1": {"t": 1}, "P2": {"t": 1}, "P3": {"t": 1},
    "t": {},
}
print(edmonds_karp(ASIGNACION, "s", "t")[0])   # 3

Flujo máximo 3 = asignación perfecta: R1→P1, R2→P2, R3→P3. Fíjate en que la voracidad ingenua podía fallar (si R1 tomara P2, R2 quedaba sin pedido) y es la maquinaria de caminos aumentantes la que lo endereza — en 03-06 veremos esta misma corrección con su nombre propio: camino alternante.

Conclusión

Hemos añadido la tercera lectura de una arista —capacidad— y con ella el problema del flujo máximo: caudal de s a t respetando capacidades y conservación. La pieza conceptual clave es la red residual, cuyas aristas de retroceso convierten las decisiones voraces en reversibles y sostienen el método de Ford-Fulkerson; la concreción práctica es Edmonds-Karp, que busca cada camino aumentante con el BFS de 03-02 y garantiza O(n·m²). Y el premio teórico es max-flow min-cut: el flujo máximo de la hora punta de Rutalia es 22 paquetes/hora no por lo que sale del almacén ni por lo que cabe en el Centro, sino por un corte intermedio de tres calles — el cuello de botella físico que dice exactamente qué ampliar y qué no. De regalo, una reducción con futuro inmediato: la asignación repartidor-pedido es un flujo con capacidades 1. En 03-06, última lección del módulo, esa idea florece en los algoritmos de emparejamiento en grafos bipartitos: bipartición, caminos alternantes, el algoritmo húngaro y la asignación óptima que en 02-01 resolvíamos con programación lineal.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados