Flujo máximo y corte mínimo
Cuánto se puede mandar por una red con capacidades limitadas, y por qué ese número coincide siempre con el costo de la forma más barata de cortarla en dos.
Para este tema conviene tener claro:BFS y DFS
Una red de caños con capacidades, una fuente y un destino: ¿cuánto se puede mandar? La respuesta tiene una propiedad que no es evidente y que hace útil a todo el tema: ese máximo es exactamente igual al costo del corte más barato que separa la fuente del destino.
Qué es un flujo, exactamente
Un flujo asigna a cada arista un valor entre cero y su capacidad, con una restricción: en todo vértice que no sea la fuente ni el destino, lo que entra es igual a lo que sale. Conservación, como en una red física.
El valor del flujo es lo que sale neto de la fuente. Maximizarlo es el problema. Un corte es una partición de los vértices con la fuente de un lado y el destino del otro; su capacidad es la suma de las aristas que van del primer lado al segundo.
Antes de seguir, predecí
El teorema que iguala flujo máximo y corte mínimo
Que todo flujo sea menor o igual a la capacidad de cualquier corte es fácil de ver: todo lo que llega al destino tiene que cruzar el corte. El teorema fuerte es que la igualdad se alcanza: el flujo máximo iguala al corte mínimo.
Eso da una forma barata de convencerse de una respuesta. Un flujo y un corte con el mismo valor son certificado uno del otro, y no hace falta confiar en el algoritmo que los produjo.
La red: de la fuente S al destino T, con las capacidades de cada tubo.
El grafo residual y la arista que va para atrás
El algoritmo se apoya en el grafo residual: para cada arista, cuánta capacidad le queda, y además una arista en sentido contrario con el flujo ya enviado.
Esa arista inversa es la pieza clave. Representa la posibilidad de deshacer una decisión anterior: mandar flujo en contra cancela parte de lo enviado. Sin eso, un camino elegido temprano podría bloquear el óptimo, y el algoritmo goloso se quedaría corto.
Ford-Fulkerson: mientras haya camino, mandar
Ford-Fulkerson es simple: mientras haya un camino de la fuente al destino en el grafo residual, mandar por él todo lo que permita su arista más ajustada y actualizar los residuales. Cuando no queda camino, el flujo es máximo.
Y ahí aparece el corte mínimo gratis: los vértices alcanzables desde la fuente en el residual final forman un lado del corte. El detalle es que “buscar un camino” no está especificado, y con capacidades irracionales el algoritmo puede no terminar.
Edmonds-Karp: elegir el camino con BFS
Edmonds-Karp fija esa elección: buscar el camino con BFS, es decir el de menos aristas. Con esa regla el algoritmo termina en , sin depender de las capacidades.
Dinic mejora eso agrupando caminos por niveles y llega a , o a en grafos de emparejamiento. Para tamaños reales, Dinic es el que se usa.
Cuántos problemas son flujo disfrazado
Lo interesante es cuántos problemas se traducen a flujo. El emparejamiento máximo en un grafo bipartito —asignar personas a tareas— se resuelve agregando una fuente conectada a un lado, un destino al otro y capacidades de uno.
También la segmentación de imágenes, la selección de proyectos con dependencias y la confiabilidad de redes: cuántos enlaces hay que romper para desconectar dos puntos es directamente un corte mínimo. Reconocer la reducción vale más que memorizar el algoritmo.
Lo que se modela como flujo
| Problema | Cómo se modela | Qué da el resultado |
|---|---|---|
| Asignar personas a tareas | fuente → personas → tareas → destino, capacidad 1 | la cantidad máxima de asignaciones |
| Emparejamiento en grafo bipartito | lo mismo | el emparejamiento máximo |
| Segmentar una imagen | píxeles como vértices, similitud como capacidad | el corte mínimo separa fondo de figura |
| Elegir proyectos con costos y beneficios | proyectos y recursos con capacidades | el subconjunto de beneficio máximo |
| Confiabilidad de una red | capacidad 1 por enlace | cuántos enlaces hay que cortar para desconectar |
Más a fondo · formalPor qué el flujo entero sale gratis
Un detalle que hace utilizable toda esta maquinaria: si todas las capacidades son enteras, el algoritmo de caminos de aumento devuelve un flujo entero, sin necesidad de pedirlo. Es el teorema de integralidad, y la razón es directa: cada camino de aumento suma el mínimo de las capacidades residuales, que es entero, así que todos los valores se mantienen enteros.
Eso importa porque los problemas que se modelan como flujo casi siempre necesitan respuestas enteras: media persona no se asigna a media tarea. En programación lineal general, en cambio, el óptimo puede ser fraccionario y forzar enteros vuelve el problema NP-difícil. El flujo es de los pocos casos donde la versión entera es igual de fácil que la continua, y ése es buena parte del motivo de que aparezca en tantos lugares.
Cierre
Flujo máximo se resuelve buscando caminos en el grafo residual, donde las aristas inversas permiten deshacer decisiones previas. Con BFS termina en tiempo polinomial, y el resultado viene con su certificado: el corte mínimo, que vale exactamente lo mismo.
Autoevaluación
¿Lo entendiste?
Práctica