Una red de flujo modela el transporte de una cantidad a través de conexiones con capacidad limitada. El flujo sale de una fuente, se conserva en los nodos intermedios y llega a un sumidero.
Muchos sistemas transportan algo por una red: agua por tuberías, datos por enlaces, vehículos por carreteras o productos por rutas logísticas. Cada conexión admite una cantidad máxima y la pregunta habitual es cuánto puede enviarse desde un origen hasta un destino.
Las redes de flujo convierten esa situación en un grafo dirigido con reglas precisas. Sobre este modelo se construyen los algoritmos de flujo máximo.
Una red de flujo es un grafo dirigido G = (V, E) que incluye:
Ninguna arista puede transportar un flujo negativo ni superar su capacidad.
Si una tubería tiene capacidad 8, son válidos los flujos entre 0 y 8. Un flujo 9 hace inválida toda la solución, aunque las demás aristas respeten sus límites.
En todo vértice intermedio, la cantidad total que entra debe ser igual a la que sale. Los nodos no crean, destruyen ni almacenan flujo.
La fuente y el sumidero son las excepciones: la fuente produce el flujo neto y el sumidero lo recibe.
El valor |f| es la cantidad neta que sale de la fuente. Por conservación, coincide con la cantidad neta que entra al sumidero.
Comprobar ambos extremos es una buena técnica para detectar errores al construir o actualizar una solución.
Ajusta el flujo de cada arista. El laboratorio verifica capacidad, conservación y valor total. Puedes cargar directamente un ejemplo factible de valor 12.
Flujo / capacidad
Diagnóstico
Las etiquetas muestran flujo/capacidad. Un nodo rojo viola conservación y una arista roja excede su capacidad.
Un flujo es factible si respeta capacidad y conservación. El flujo cero siempre es factible, pero normalmente no es útil.
El problema de flujo máximo busca, entre todos los flujos factibles, uno cuyo valor |f| sea el mayor posible. Ser factible no implica ser máximo.
Si una arista u → v tiene capacidad 10 y actualmente transporta 6, todavía pueden enviarse 4 unidades adicionales.
Una capacidad residual positiva indica que la arista admite más flujo en ese sentido.
Por cada flujo f(u,v) aparece una capacidad residual f(u,v) en sentido contrario. No representa una tubería física: permite deshacer parte de una decisión anterior.
Esta posibilidad de corregir elecciones es esencial. Un algoritmo no queda atrapado simplemente por haber enviado flujo por una ruta poco conveniente.
La red residual Gf contiene todas las aristas con capacidad residual positiva, tanto hacia adelante como hacia atrás.
| Situación en u → v | Residual u → v | Residual v → u |
|---|---|---|
| f = 0, c = 8 | 8 | 0 |
| f = 3, c = 8 | 5 | 3 |
| f = 8, c = 8 | 0 | 8 |
Un camino aumentante es un camino desde s hasta t dentro de la red residual. A lo largo de él puede enviarse flujo adicional.
La cantidad máxima que puede agregarse está limitada por la menor capacidad residual del camino, llamada cuello de botella.
Al aumentar Δ unidades por un camino residual, se suma Δ sobre las aristas originales recorridas hacia adelante y se resta sobre las recorridas hacia atrás.
for (const arista of camino) {
if (arista.esOriginal) {
flujo[arista.u][arista.v] += delta;
} else {
flujo[arista.v][arista.u] -= delta;
}
}La actualización mantiene la conservación en los nodos internos del camino.
Un corte (S,T) divide los vértices en dos conjuntos: s pertenece a S y t pertenece a T. La capacidad del corte suma las capacidades de las aristas que van de S hacia T.
Las aristas que van de T hacia S no se suman porque el corte respeta la dirección del transporte.
Todo flujo de s a t debe atravesar cualquier corte que los separe. Por lo tanto, el valor de un flujo nunca puede superar la capacidad de un corte.
Encontrar un flujo y un corte con el mismo valor demuestra que ambos son óptimos.
El teorema central afirma que el valor del flujo máximo es exactamente igual a la capacidad del corte mínimo.
La igualdad conecta una solución constructiva —enviar flujo— con un certificado de imposibilidad —un cuello de botella que ninguna solución puede superar—.
Una implementación suele almacenar capacidad, flujo y conexiones residuales. Una matriz resulta sencilla; las listas de adyacencia son más eficientes en redes dispersas.
function crearRed(cantidadVertices) {
return {
adyacentes: Array.from({ length: cantidadVertices }, () => []),
capacidad: Array.from(
{ length: cantidadVertices },
() => Array(cantidadVertices).fill(0)
),
flujo: Array.from(
{ length: cantidadVertices },
() => Array(cantidadVertices).fill(0)
)
};
}
function agregarArista(red, u, v, capacidad) {
red.adyacentes[u].push(v);
red.adyacentes[v].push(u); // necesaria para la red residual
red.capacidad[u][v] += capacidad;
}Las redes de flujo combinan límites locales y una regla global de conservación. La red residual revela no solo cuánto espacio queda disponible, sino también cómo revisar decisiones anteriores.
En el próximo tema utilizaremos estas ideas para estudiar Ford-Fulkerson, un método que aumenta repetidamente el flujo a través de caminos residuales.