Algoritmo de Ford-Fulkerson

El método Ford-Fulkerson o algoritmo Ford-Fulkerson ( FFA ) es un algoritmo voraz que calcula el flujo máximo en una red de flujo . A veces se le llama "método" en lugar de "algoritmo" porque el enfoque para encontrar rutas de aumento en un grafo residual no está completamente especificado ^{[ 1 ]} o está especificado en varias implementaciones con diferentes tiempos de ejecución. ^{[ 2 ]} Fue publicado en 1956 por LR Ford Jr. y DR Fulkerson . ^{[ 3 ]} El nombre "Ford - Fulkerson" también se usa a menudo para el algoritmo Edmonds-Karp , que es una implementación completamente definida del método Ford - Fulkerson.

La idea detrás del algoritmo es la siguiente: mientras exista un camino desde el origen (nodo inicial) hasta el destino (nodo final), con capacidad disponible en todos los enlaces del camino, enviamos el flujo a lo largo de uno de esos caminos. Luego encontramos otro camino, y así sucesivamente. Un camino con capacidad disponible se denomina camino de aumento .

Dejar${\displaystyle G(V,E)}$Sea u un grafo, y para cada arista de u a v , sea${\displaystyle c(u,v)}$ser la capacidad y${\displaystyle f(u,v)}$Sea el flujo. Queremos encontrar el flujo máximo desde la fuente s hasta el sumidero t . Después de cada paso del algoritmo se mantiene lo siguiente:

Esto significa que el flujo a través de la red es un flujo válido después de cada ronda del algoritmo. Definimos la red residual.${\displaystyle G_{f}(V,E_{f})}$ser la red con capacidad${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$y ningún flujo. Nótese que puede ocurrir que se permita un flujo de v a u en la red residual, aunque no esté permitido en la red original: si${\displaystyle f(u,v)>0}$y${\displaystyle c(v,u)=0}$entonces${\displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0}$.

Algoritmo Ford – Fulkerson

La ruta en el paso 2 se puede encontrar con, por ejemplo, búsqueda en amplitud (BFS) o búsqueda en profundidad en${\displaystyle G_{f}(V,E_{f})}$El primero se conoce como el algoritmo de Edmonds-Karp .

Cuando no se puedan encontrar más caminos en el paso 2, s no podrá alcanzar t en la red residual. Si S es el conjunto de nodos alcanzables por s en la red residual, entonces la capacidad total en la red original de aristas desde S al resto de V es, por un lado, igual al flujo total que encontramos de s a t , y por otro lado sirve como límite superior para todos esos flujos. Esto demuestra que el flujo que encontramos es máximo. Véase también el teorema del corte mínimo de flujo máximo .

Si el gráfico${\displaystyle G(V,E)}$tiene múltiples fuentes y sumideros, actuamos de la siguiente manera: Supongamos que${\displaystyle T=\{t\mid t{\text{ is a sink}}\}}$y${\displaystyle S=\{s\mid s{\text{ is a source}}\}}$Agregar una nueva fuente${\displaystyle s^{*}}$con un toque de distinción${\displaystyle (s^{*},s)}$de${\displaystyle s^{*}}$a cada nodo${\displaystyle s\in S}$, con capacidad${\displaystyle c(s^{*},s)=d_{s}=\sum _{(s,u)\in E}c(s,u)}$Y añadir un nuevo fregadero${\displaystyle t^{*}}$con un toque de distinción${\displaystyle (t,t^{*})}$desde cada nodo${\displaystyle t\in T}$a${\displaystyle t^{*}}$, con capacidad${\displaystyle c(t,t^{*})=d_{t}=\sum _{(v,t)\in E}c(v,t)}$. Luego, aplique el algoritmo de Ford - Fulkerson.

Además, si un nodo u tiene una restricción de capacidad${\displaystyle d_{u}}$, reemplazamos este nodo con dos nodos${\displaystyle u_{\mathrm {in} },u_{\mathrm {out} }}$y una ventaja${\displaystyle (u_{\mathrm {in} },u_{\mathrm {out} })}$, con capacidad${\displaystyle c(u_{\mathrm {in} },u_{\mathrm {out} })=d_{u}}$. A continuación, podemos aplicar el algoritmo de Ford - Fulkerson.

Al agregar la ruta de aumento de flujo al flujo ya establecido en el grafo, se alcanzará el flujo máximo cuando no se puedan encontrar más rutas de aumento de flujo en el grafo. Sin embargo, no hay certeza de que esta situación se alcance alguna vez, por lo que lo mejor que se puede garantizar es que la respuesta será correcta si el algoritmo termina. En el caso de que el algoritmo no termine, el flujo podría no converger hacia el flujo máximo. Sin embargo, esta situación solo ocurre con valores de flujo irracionales. ^{[ 4 ]} Cuando las capacidades son números enteros, el tiempo de ejecución de Ford-Fulkerson está acotado por${\displaystyle O(Ef)}$(véase la notación de la gran O ), donde${\displaystyle E}$es el número de aristas en el grafo y${\displaystyle f}$es el flujo máximo en el grafo. Esto se debe a que cada ruta de aumento se puede encontrar en${\displaystyle O(E)}$tiempo y aumenta el flujo en una cantidad entera de al menos${\displaystyle 1}$, con el límite superior${\displaystyle f}$.

Una variación del algoritmo de Ford - Fulkerson con terminación garantizada y un tiempo de ejecución independiente del valor máximo del flujo es el algoritmo de Edmonds-Karp , que se ejecuta en${\displaystyle O(VE^{2})}$tiempo.

El siguiente ejemplo muestra los primeros pasos del método de Ford-Fulkerson en una red de flujo con 4 nodos, origen${\displaystyle A}$y fregadero${\displaystyle D}$Este ejemplo muestra el comportamiento del algoritmo en el peor de los casos. En cada paso, solo un flujo de${\displaystyle 1}$se envía a través de la red. Si en su lugar se utilizara la búsqueda en amplitud, solo serían necesarios dos pasos.

Considere la red de flujo que se muestra a la derecha, con origen${\displaystyle s}$, hundir${\displaystyle t}$capacidades de los bordes${\displaystyle e_{1}=1}$,${\displaystyle e_{2}=r=({\sqrt {5}}-1)/2}$y${\displaystyle e_{3}=1}$y la capacidad de todas las demás aristas algún número entero${\displaystyle M\geq 2}$. La constante${\displaystyle r}$fue elegido de tal manera que${\displaystyle r^{2}=1-r}$. Utilizamos rutas de aumento según la siguiente tabla, donde${\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}$,${\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\}}$y${\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\}}$.

Tenga en cuenta que después del paso 1, así como después del paso 5, las capacidades residuales de los bordes${\displaystyle e_{1}}$,${\displaystyle e_{2}}$y${\displaystyle e_{3}}$están en la forma${\displaystyle r^{n}}$,${\displaystyle r^{n+1}}$y${\displaystyle 0}$, respectivamente, para algunos${\displaystyle n\in \mathbb {N} }$Esto significa que podemos usar rutas de aumento.${\displaystyle p_{1}}$,${\displaystyle p_{2}}$,${\displaystyle p_{1}}$y${\displaystyle p_{3}}$infinitas veces y las capacidades residuales de estos bordes siempre tendrán la misma forma. El flujo total en la red después del paso 5 es${\displaystyle 1+2(r^{1}+r^{2})}$. Si continuamos utilizando rutas de aumento como se indicó anteriormente, el flujo total converge a${\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}$Sin embargo, tenga en cuenta que existe un flujo de valor.${\displaystyle 2M+1}$, enviando${\displaystyle M}$unidades de flujo a lo largo${\displaystyle sv_{1}t}$, 1 unidad de flujo a lo largo${\displaystyle sv_{2}v_{3}t}$, y${\displaystyle M}$unidades de flujo a lo largo${\displaystyle sv_{4}t}$Por lo tanto, el algoritmo nunca termina y el flujo no converge al flujo máximo. ^{[ 5 ]}

Otro ejemplo no terminante basado en el algoritmo euclidiano lo proporcionan Backman y Huynh (2018) , donde también muestran que el tiempo de ejecución en el peor caso del algoritmo de Ford-Fulkerson en una red${\displaystyle G(V,E)}$en números ordinales es${\displaystyle \omega ^{\Theta (|E|)}}$.

• Teorema de Berge
• Teorema aproximado de flujo máximo y corte mínimo
• Rutas con restricción de giro
• El algoritmo de Dinic

• Cormen, Thomas H.; Leiserson , Charles E.; Rivest , Ronald L .; Stein, Clifford (2001). «Sección 26.2: El método Ford - Fulkerson». Introducción a los algoritmos (Segunda  edición). MIT Press y McGraw - Hill. págs. 651-664 . ISBN  0-262-03293-7.
• George T. Heineman; Gary Pollice; Stanley Selkow (2008). «Capítulo 8: Algoritmos de flujo de red». Algoritmos en pocas palabras . Oreilly Media . págs. 226–250 . ISBN  978-0-596-51624-6.
• Jon Kleinberg ; Éva Tardos (2006). «Capítulo 7: Extensiones al problema del flujo máximo» . Diseño de algoritmos . Pearson Education. págs. 378–384 . ISBN  0-321-29535-8.
• Samuel Gutekunst (2019). ENGRI 1101 . Universidad de Cornell.
• Backman, Spencer; Huynh, Tony (2018). "Ford–Fulkerson transfinito en una red finita". Computability . 7 (4): 341– 347. arXiv : 1504.04363 . doi : 10.3233/COM-180082 . S2CID 15497138 . 

• Un tutorial que explica el método de Ford-Fulkerson para resolver el problema del flujo máximo.
• Otra animación Java
• Aplicación Java Web Start

Contenido multimedia relacionado con el algoritmo de Ford-Fulkerson en Wikimedia Commons.