Algoritmos de Flujo en Redes

Los algoritmos de flujo en redes calculan la cantidad máxima de flujo que se puede enviar desde una fuente a un sumidero a través de una red con capacidades, un problema cuyo óptimo está ligado por dualidad al corte mínimo de la red.

Definition

Una red de flujo es un grafo dirigido con capacidades en las aristas, una fuente y un sumidero; un algoritmo de flujo máximo encuentra una asignación de flujo a las aristas, respetando las capacidades y la conservación en los vértices intermedios, que maximiza el flujo total de la fuente al sumidero.

Scope

Este tema cubre el problema del flujo máximo y sus algoritmos: el método de Ford-Fulkerson con rutas de aumento, los refinamientos de Edmonds-Karp y Dinic que acotan el tiempo de ejecución, y el teorema de flujo máximo-corte mínimo que caracteriza el óptimo. También cubre las reducciones de otros problemas —emparejamiento bipartito, rutas disjuntas de vértices, selección de proyectos— al flujo en redes. Excluye la programación lineal general, de la cual el flujo es un caso especial.

Core questions

• ¿Cómo se define un flujo y qué restricciones debe satisfacer?
• ¿Cómo aumentan las rutas de aumento en el grafo residual el flujo hacia el máximo?
• ¿Por qué el flujo máximo es igual a la capacidad del corte mínimo?
• ¿Cómo garantizan los algoritmos de Edmonds-Karp y Dinic un tiempo de ejecución polinomial?
• ¿Cómo se reducen el emparejamiento y otros problemas al flujo máximo?

Key concepts

• red de flujo
• capacidad y conservación
• ruta de aumento
• grafo residual
• teorema de flujo máximo-corte mínimo
• algoritmo de Edmonds-Karp
• algoritmo de Dinic
• reducción de emparejamiento bipartito

Key theories

Teorema de flujo máximo-corte mínimo

El valor de un flujo máximo de la fuente al sumidero es igual a la capacidad mínima de un corte que los separa; esta dualidad, debida a Ford y Fulkerson, certifica la optimalidad y vincula el flujo con problemas de conectividad y partición.

Rutas de aumento y grafos residuales

El método de Ford-Fulkerson aumenta el flujo al encontrar rutas con capacidad sobrante en el grafo residual; la elección de las rutas de aumento más cortas (Edmonds-Karp) o el uso de grafos de nivel y flujos de bloqueo (Dinic) proporciona garantías de tiempo polinomial.

Clinical relevance

El flujo en redes es una herramienta de modelado versátil: resuelve la asignación y programación bipartita, calcula la conectividad y fiabilidad de las redes, realiza la segmentación de imágenes mediante cortes de grafo en visión por computadora, y sustenta la logística, la planificación del transporte y la optimización de la selección de proyectos donde las capacidades y los cuellos de botella son importantes.

History

Ford y Fulkerson introdujeron el problema del flujo máximo y el teorema de flujo máximo-corte mínimo en 1956 mientras estudiaban redes de transporte. Edmonds y Karp (1972) e, independientemente, Dinic (1970) proporcionaron los primeros algoritmos de tiempo polinomial, y el trabajo posterior ha mejorado constantemente el tiempo de ejecución asintótico del flujo máximo.

Key figures

• Lester Ford
• Delbert Fulkerson
• Jack Edmonds
• Yefim Dinic

Seminal works

• fordfulkerson1956
• cormen2009

Frequently asked questions

¿Qué dice realmente el teorema de flujo máximo-corte mínimo?

Establece que la mayor cantidad de flujo que se puede empujar de la fuente al sumidero es igual a la capacidad total más pequeña de cualquier conjunto de aristas cuya eliminación desconecta la fuente del sumidero. El corte mínimo actúa como el cuello de botella que limita el flujo máximo.

¿Por qué el algoritmo de Ford-Fulkerson simple no tiene un tiempo de ejecución polinomial?

Si las rutas de aumento se eligen de manera deficiente y las capacidades son grandes (o irracionales), el número de aumentos puede ser enorme o incluso no terminar. La elección de las rutas de aumento más cortas (Edmonds-Karp) o el uso de flujos de bloqueo (Dinic) acota el número de aumentos y proporciona un tiempo polinomial.