Teoría de redes

Abstract

La Teoría de Redes es un área dentro de la Investigación de Operaciones cuyo origen está vinculado a la Programación Lineal. El desarrollo de la computación ha provocado una mayor variedad y velocidad de los algoritmos propios de esta teoría y en general en la teoría del diseño de algoritmos. Su versatilidad y la representación gráfica de los problemas hace de esta una de las áreas más usadas en el campo de las aplicaciones, cuyo rango es tan amplio que abarca la química, la física, redes de computadoras, muchas ramas de la ingeniería, manufactura, política pública y sistemas sociales, tráfico urbano, telecomunicaciones y transporte, por citar solo algunos. El problema central de resolver un problema de flujo a costo mínimo conlleva a que los problemas de flujo máximo, ruta más corta, asignación, transporte y circulación se puedan ver ligados y formando parte de este problema central.

Este texto que consta de ocho capítulos tiene como objetivo ser un apoyo didáctico para la clase. Brinda una visión sencilla y general de la teoría de redes. Aborda temas como flujo máximo y corte mínimo, ruta más corta, árbol de expansión mínima, ruta crítica y por último problema de flujo a costo mínimo. Se exponen diferentes algoritmos de un mismo problema para compararlos y ver su complejidad computacional, así como una variedad de ejemplos desarrollados paso a paso para facilitar su comprensión. Finalmente se expone una serie de notas históricas al final de cada capítulo, con el objetivo de que el lector tenga una visión más amplia sobre cada tema.