Problemas de redes y flujos

Abstract

Las redes de flujos son un modelo que permite representar sistemas tales como mapas de carretera, redes de tuberías, conexiones de red, etc., desde un punto de vista abstracto. En este modelo también quedan representados los elementos que transitan en sus correspondientes sistemas: coches, líquidos, datos. . . Gracias a su estudio, se resuelven problemas tan comunes como calcular cuántos litros de agua deben recorrer una determinada tubería en función de las necesidades de una población, o determinar el número máximo de vehículos que pueden circular por una carretera. Esta investigación se centra, por tanto, en resolver estos problemas de forma eficiente. Para ello, el trabajo ha sido dividido en tres capítulos. En el Capítulo 1, se realiza una introducción a la Teoría de Grafos, explicando su origen y planteando uno de los problemas más importantes en esta rama: El problema del camino más corto. Nos centramos en algoritmos como Dijkstra o A* para resolverlo. En el Capítulo 2, se tratan Árboles, una importante parte de la Teoría de Grafos, que además es de gran utilidad para desarrollar futuros algoritmos. Estudiaremos algunas de sus propiedades, plantearemos el conocido problema del árbol de expansión de mínimo costo y resolveremos una ejemplificación del mismo. Por último, en el Capítulo 3, se realiza un estudio de los flujos y redes, basándonos en los conceptos explicados en los dos capítulos anteriores. Indagamos en el problema más importante de una red de flujo: Problema de flujo máximo. Comezamos con su planteamiento, y aplicamos tres de los algoritmos más reconocidos para resolver este tipo de problema: Ford-Fulkerson, Edmonds-Karp y Dinic.

Flow networks are a model that allows to represent systems such as maps of road, pipe networks, network connections, etc., from an abstract point of view. This model also represents the elements that pass through their corridors. relevant systems: cars, liquids, data. . . Thanks to its study, common problems such as calculating how many liters of water must travel through a certain pipeline depending on the needs of a population, or determine the maximum number of vehicles that can circulate on a highway. This research focuses, therefore, on solving these problems efficiently. For this reason, the work has been divided into three chapters. In Chapter 1, an introduction to Graph Theory is made, explaining its origin and proposing one of the most important problems in this branch: Shortest Path problem. We focus on algorithms like Dijkstra or A* to solve it. In Chapter 2, we discuss Trees, an important part of Graph Theory, which is also very useful for developing future algorithms. We will study some of its properties, we will propose the well-known Minimum Degree Spanning Tree problem (MDST) and we will resolve an exemplification of it. Finally, in Chapter 3, a study of flows and networks is carried out, based on the concepts explained in the previous two chapters. We investigate the most important problem of a flow network: Maximum Flow problem. We start with its approach, and we apply three of the most recognized algorithms to solve this type problem: Ford-Fulkerson, Edmonds-Karp and Dinic.