Delbert Ray Fulkerson (*14 de agosto de 1924 - †10 de enero de 1976) fue un matemático estadounidense que desarrolló como co-autor, y junto conLester Randolph Ford, Jr., el Algoritmo de Ford-Fulkerson, uno de los algoritmos más utilizados para computar el flujo máximo en una red de flujo.
Fulkerson recibió su Ph.D. en la Universidad de Wisconsin-Madison en 1951. En 1956, su importante artículo científico fue publicado.1 Desde 1979, laSociedad de Programación Matemática (MPS) y la American Mathematical Society (AMS) otorgan cada tres años el Premio Fulkerson, para aquellos matemáticos que hayan creado artículos importantes en el área de la matemática discreta.
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 RayFulkerson (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 (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.
No hay comentarios:
Publicar un comentario