Flujo de Red y el Teorema Max-Flow Min-Cut

1. ¿Qué es una Red de Flujo?

Imagina un complejo sistema de agua de la ciudad. Tienes una planta principal de tratamiento de agua empujando el agua hacia afuera, y un depósito principal donde eventualmente termina toda el agua. Entre ellos se encuentra una enorme red de tuberías de diferentes tamaños.

Algunas tuberías son tuberías maestras masivas (alta capacidad), mientras que otras son tuberías residenciales pequeñas (baja capacidad). La pregunta es: ¿Cuál es la cantidad máxima de agua que puedes bombear desde la planta hasta el depósito por segundo sin reventar ninguna tubería?

En teoría de grafos, esto se modela como una Red de Flujo (Flow Network). Una red de flujo es un grafo dirigido donde:

• Fuente (s): El nodo de inicio donde se origina el "flujo" (la planta de agua).
• Sumidero (t): El nodo de destino donde termina todo el "flujo" (el depósito).
• Aristas: Las conexiones entre nodos (las tuberías).
• Capacidad (c): La cantidad máxima de flujo que una arista puede manejar (el ancho de la tubería).

2. Las Tres Reglas del Flujo de Red

Para definir matemáticamente un flujo válido a través de esta red, debemos seguir tres reglas absolutas:

1. Restricción de Capacidad: El flujo en cualquier arista no puede exceder su capacidad. Si una tubería puede contener 10 galones por segundo, no puedes empujar 11 galones a través de ella. Matemáticamente: 0 ≤ f(u,v) ≤ c(u,v).
2. Conservación del Flujo: Para cada nodo en el grafo (excepto la Fuente y el Sumidero), el flujo total que entra al nodo debe ser exactamente igual al flujo total que sale del nodo. Los nodos no generan mágicamente ni consumen agua. Lo que entra debe salir.
3. Simetría Sesgada (Regla opcional pero útil): El flujo del nodo U al V es el negativo del flujo de V a U. Si 5 unidades fluyen de U a V, entonces -5 unidades fluyen de V a U.

El objetivo del Problema de Flujo Máximo es encontrar una asignación válida de flujo a cada arista que maximice el flujo total que sale de la Fuente s (que, debido a la conservación del flujo, será perfectamente igual al flujo total que llega al Sumidero t).

3. El Algoritmo de Ford-Fulkerson (Caminos Aumentantes)

Para resolver el problema del flujo máximo, utilizamos el Algoritmo de Ford-Fulkerson, desarrollado en 1956. La lógica subyacente es deliciosamente intuitiva.

El algoritmo funciona de la siguiente manera:

1. Comienza con un flujo de 0 en todas las aristas.
2. Encuentra un camino desde la Fuente hasta el Sumidero donde cada arista en el camino tenga capacidad disponible y no utilizada. Esto se llama un Camino Aumentante.
3. Encuentra la arista en este camino con la capacidad disponible más pequeña. Este es el "cuello de botella".
4. Empuja una cantidad de flujo igual a la capacidad del cuello de botella a lo largo de todo el camino.
5. Repite los pasos 2-4 hasta que no se puedan encontrar más caminos aumentantes.

Cuando ya no puedas encontrar un camino desde la Fuente hasta el Sumidero que pueda aceptar más flujo, habrás encontrado el Flujo Máximo. ¡Pero espera, hay una trampa!

4. El Arma Secreta: Grafos Residuales

Si implementas Ford-Fulkerson exactamente como se describió anteriormente, es posible que obtengas la respuesta incorrecta. ¿Por qué? Porque podrías hacer una "mala" elección codiciosa desde el principio, enviando flujo por una tubería que bloquea una ruta mucho mejor más adelante.

Para solucionar esto, Ford-Fulkerson utiliza un concepto brillante llamado Grafo Residual. El grafo residual permite que el algoritmo "deshaga" las malas decisiones.

Siempre que empujes X unidades de flujo hacia adelante a lo largo de una arista de U a V, debes agregar una "arista inversa" en el grafo residual de V a U con una capacidad de X. Esta arista inversa representa tu capacidad para "empujar hacia atrás" o cancelar el flujo que acabas de enviar.

Si un camino aumentante futuro utiliza una de estas aristas inversas, está redirigiendo efectivamente el agua que enviaste anteriormente por una tubería diferente y más óptima. Siempre debes buscar tus caminos aumentantes en el Grafo Residual, no en el grafo original.

5. El Teorema Max-Flow Min-Cut

Esto nos lleva a uno de los teoremas más hermosos y profundos de toda la teoría de grafos: El Teorema Max-Flow Min-Cut.

Imagina que quieres sabotear por completo el sistema de agua de la ciudad. Quieres cortar un conjunto de tuberías de tal manera que absolutamente ninguna gota de agua pueda llegar al depósito desde la planta de tratamiento. Naturalmente, quieres hacer esto con la menor cantidad de esfuerzo, lo que significa que quieres cortar las tuberías cuya capacidad total combinada sea lo más pequeña posible.

Esto se llama un Corte (Cut). Un corte s-t particiona los nodos del grafo en dos conjuntos: uno que contiene la Fuente (s) y otro que contiene el Sumidero (t). La capacidad del corte es la suma de las capacidades de todas las aristas que van desde el conjunto fuente al conjunto sumidero.

El Corte Mínimo (Min-Cut) es el corte con la menor capacidad total posible.

El teorema establece una equivalencia increíble:

La cantidad máxima de flujo que puedes empujar a través de una red es EXACTAMENTE IGUAL a la capacidad del corte mínimo.

Son las dos caras de la misma moneda. El cuello de botella que restringe tu flujo es exactamente el mismo cuello de botella que atacarías para cortar la red. Al resolver Max-Flow (usando Ford-Fulkerson), estás encontrando simultáneamente el valor exacto del Min-Cut.

6. Mejorando Ford-Fulkerson: El Algoritmo de Edmonds-Karp

Ford-Fulkerson tiene una falla: no te dice cómo encontrar el camino aumentante. Si solo usas una Búsqueda en Profundidad (DFS) arbitraria, y tu grafo tiene pesos de arista muy específicos, el algoritmo puede ejecutarse increíblemente lento. De hecho, con capacidades de arista irracionales, ¡el simple Ford-Fulkerson podría nunca terminar!

En 1972, Jack Edmonds y Richard Karp publicaron una modificación simple pero brillante: Encuentra siempre el camino aumentante más corto utilizando la Búsqueda en Anchura (BFS).

Al obligar al algoritmo a encontrar caminos aumentantes con el menor número de aristas (ignorando la capacidad), el Algoritmo de Edmonds-Karp garantiza una complejidad de tiempo polinomial de O(V * E^2), totalmente independiente de los valores de capacidad reales en las aristas.

7. Aplicaciones en el Mundo Real

Los algoritmos de flujo de red no son solo para plomería. Resuelven problemas increíblemente complejos de asignación y enrutamiento en ingeniería de software e investigación de operaciones.

Emparejamiento Bipartito Máximo

Imagina que tienes 5 solicitantes de empleo y 5 trabajos disponibles. Cada solicitante solo está calificado para ciertos trabajos. ¿Cómo asignas el número máximo de personas a un trabajo para el que están calificados?

¡Puedes convertir esto en un problema de Max-Flow! Crea un nodo "Fuente" y conéctalo a todos los solicitantes con capacidad 1. Conecta a los solicitantes con los trabajos para los que están calificados con capacidad 1. Conecta todos los trabajos a un nodo "Sumidero" con capacidad 1. Ejecuta Ford-Fulkerson. El flujo máximo será perfectamente igual al número máximo de personas que puedes emplear con éxito.

Segmentación de Imágenes en Visión por Computadora

En visión por computadora, separar un objeto (el primer plano) de su fondo es un problema clásico. Al representar los píxeles como un grafo, donde las aristas representan la similitud de color entre los píxeles vecinos, el problema de separar el primer plano del fondo se puede asignar perfectamente al problema Minimum-Cut.

Eliminación Deportiva

Durante una temporada de béisbol, ¿puedes probar matemáticamente que un equipo está eliminado de los playoffs, incluso si gana todos los juegos restantes? Al crear una red de flujo que represente los juegos restantes entre todos los demás equipos, puedes usar Max-Flow para probar si existe un escenario en el que el equipo aún podría ganar la división.