===algoritmo de Ford-Fulkerson===
**//flujo máximo//**
{{ :delbertrayfulkerson_foto.jpg?nolink|Delbert Ray Fulkerson}}{{ :lesterrandolphford_foto.jpg?nolink|Lester Randolph Ford Jr.}}
**Lester Randolph Ford Jr.** al continuar los pasos de su padre Ford Sr. también hizo una enorme contribución al campo de las matemáticas. Su trabajo con **Delbert Ray Fulkerson** (14 agosto de 1924 - 10 Enero de 1976) ha puesto la base de casi toda la investigación en flujos de grafos. El artículo de Ford y de Fulkerson (1956) con el problema de flujo máximo estableció el famoso teorema del flujo máximo - mínimo corte.
Se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, por tanto, puede considerarse como un conducto que tiene cierta capacidad de flujo. De igual modo que en redes eléctricas ([[wpes>Leyes_de_Kirchhoff|Leyes de Kirchhoff]]), la suma de flujos entrantes a un nodo, debe ser igual a la suma de los salientes (principio de conservación de energía), excepto para el nodo fuente y el nodo sumidero.
Por tanto, el problema de flujo máximo se enuncia como: ¿cuál es la tasa a la cual se puede transportar el material desde el nodo fuente al nodo sumidero, sin violar las restricciones de capacidad?. Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Una red de flujo es un grafo dirigido //G=(V,E)// donde cada arco //(u,v)// perteneciente a //E// el número de arcos del grafo; tiene una capacidad no negativa. Se distinguen dos nodos: la fuente o nodo //s//, y el sumidero o nodo //t//. Si existen múltiples fuentes y sumideros, el problema se puede simplificar añadiendo una fuente común y un sumidero común. Este algoritmo depende de tres conceptos principales:
* Un camino de aumento, es una trayectoria desde el nodo fuente //s// al nodo sumidero //t// que puede conducir más flujo.
* La capacidad residual es la capacidad adicional de flujo que un arco puede llevar //c_f (u,v) = c(u,v) - f(u,v)//
* Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
El algoritmo es iterativo, se comienza con //f(u,v)=0// para cada par de nodos y en cada iteración se incrementa el valor del flujo buscando un camino de aumento. El proceso se repite hasta no encontrar un camino de aumento. A continuación se muestra el pseudocódigo del algoritmo:
Ford-Fulkerson (G,s,t)
para cada arco (u,v) de E
f(u,v) = 0
f(v,u) = 0
mientras exista un camino p desde s a t en la red residual G_f
c_f (p) = min {c_f (u,v) : (u,v) está sobre p}
para cada arco (u,v) en p
f(u,v) = f(u,v) + c_f (p)
f(u,v) = -f(u,v)
Una variación del algoritmo de Ford-Fulkerson es el algoritmo de Edmonds-Karp (J. Edmonds; R.M. Karp - 1972). En éste, el 'camino de aumento' es elegido usando una búsqueda por niveles o en anchura (breadth-first search). El algoritmo de Edmonds-Karp requiere //O(VE^2)// tiempo de computación, donde //V// es el número de nodos o vértices, y //E// el número de arcos del grafo.
Puede encontrar más información en:
* [[wp>L._R._Ford,_Jr.|L. R. Ford Jr.]]
* [[wp>D._R._Fulkerson|Delbert Ray Fulkerson]]
* Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ. Princeton University Press, 1962.
* Edmonds, J. and Karp, R. M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. //J. ACM// 19, 248-264, 1972.
* Berge, C. Two Theorems in Graph Theory. Proc. Nat. Acad. Sci. USA 43, 842-844, 1957.
===ejemplo de flujo máximo===
Para el presente ejemplo, construiremos una grafo con las siguientes matrices de datos para los valores mínimo, máximo y coste de los arcos:
Matriz de mínimo:
N1\N2 s 1 2 3 4 t
s 12 11
1 12 0
2 0 19
3 0 11
4 7 4
t
Matriz de máximo:
N1\N2 s 1 2 3 4 t
s 16 13
1 12 10
2 9 20
3 4 14
4 7 4
t
Matriz de coste:
N1\N2 s 1 2 3 4 t
s 0 0
1 0 0
2 0 0
3 0 0
4 0 0
t
El grafo dibujado tendría el siguiente aspecto.
{{ :grafos_ejemplo_flujomaximo01.png?nolink |ejemplo de flujo máximo}}
Nótese que en los arcos se han representado los valores de mínimo, máximo y coste respectivamente. Antes de iniciar el algoritmo se deben seleccionar un nodo origen y un nodo destino, en este ejemplo se tomará el nodo //s// y el nodo //t// respectivamente.
{{ :grafos_ejemplo_flujomaximo02.png?nolink |ejemplo de flujo máximo}}
Tras ejecutar el algoritmo se muestra la siguiente solución:
Flujos calculados desde el nodo origen (s) hasta el nodo destino (t)
Flujo máximo = 23
Matriz de Arcos con flujo máximo:
N1\N2 s 1 2 3 4 t
s 0 12 0 11 0 0
1 -12 0 12 0 0 0
2 0 -12 0 0 -7 19
3 -11 0 0 0 11 0
4 0 0 7 -11 0 4
t 0 0 -19 0 -4 0
Matriz de Capacidades Residuales:
N1\N2 s 1 2 3 4 t
s 0 4 0 2 0 0
1 12 0 0 10 0 0
2 0 12 0 9 7 1
3 11 4 0 0 3 0
4 0 0 0 11 0 0
t 0 0 19 0 4 0
Como se puede observar, el flujo máximo es de 23 unidades. A continuación Grafos subrayará los arcos de la solución, diferenciando el color ligeramente para distinguir los arcos saturados de aquellos que tienen capacidad residual.
{{ :grafos_ejemplo_flujomaximo03.png?nolink |ejemplo de flujo máximo}}
Si observa la figura verá cómo todo el flujo originario del nodo //s// se distribuye por los arcos de la red, hasta llegar al nodo destino //t//. Nótese además, que en este algoritmo no se han tenido en cuenta los costes asociados al transporte o flujo, simplemente las conexiones y la restricción/capacidad de flujo de los arcos.
----
~~NOTOC~~