Red de Flujo

Comencemos con explicando el término Red de flujo:

Como decimos en el vídeo, uno de los trabajos que dan salida al uso de las redes de flujo es el Algoritmo de Ford-Fulkerson para encontrar el flujo máximo de una red. Este algoritmo se publica en 1956 por L. R. Ford, Jr.  y D. R. Fulkerson, en el artículo Maximal flow through a network (Canadian Journal of Mathematics 8: 399. doi:10.4153/CJM-1956-045-5). Sin embargo, en el comienzo de la publicación nos dice que plantean estudiar el problema, formulado por T.E. Harris, siguiente:

«Consider a rail network connecting two cities by way of  number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.»

Este problema lo presenta T.E. Harris en una correspondencia con F.S Ross sobre el trabajo que publican en 1955 (T.E. Harris, F.S. Ross, Fundamentals of a Method for Evaluating Rail Net Capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica, California, 1955).  Pero si tenemos que encontrar el inicio, debemos retroceder a 1930, cuando A.N. Tolstoi publica un trabajo sobre un problema del transporte (la figura de arriba pertenece al artículo). Tolstoi trataba de analizar los problemas de las comunicaciones en la redes ferroviales soviéticas.

El problema del transporte, que daría paso al teoría de transporte, muy desarrollada en economía, fue formulada por el matemático francés  Gaspard Monge en 1781. Pero en los años 20 del siglo pasado, A.N. Tolstoi realizaría los primeros trabajos para estudiar el problema del transporte matemáticamente.

Para más información ver Schrijver, Alexander, Combinatorial Optimization, Berlin ; New York : Springer, 2003. ISBN 3540443894. 

Esta entrada participa en la Edición 6.4: pseudoprimos del Carnaval de Matemáticas cuyo anfitrión es pimedios.