Gestión de recursos

Abstract

RESUMEN: Este trabajo presenta una introducción al problema del flujo máximo en grafos, que aparece de forma recurrente en diversas áreas y del que se han propuesto diversas soluciones pero que sigue atrayendo interés en el mundo de la investigación. Las aplicaciones más usuales que nos encontramos son en logística (transporte de mercancías), en el flujo de gases y lquidos por redes de tuberías interconectadas, en el flujo de corrientes de intensidad en redes eléctricas con distintas capacidades y en el tráfico ferroviario, por citar algunas. Un problema típico sería hallar cual es el mayor flujo de corriente que se puede transmitir por una red eléctrica. Haciendo uso de la teoría de grafos, la red se representa mediante un grafo dirigido, compuesto por una serie de aristas con capacidades asociadas. El modelo de grafo asocia a un nodo inicial el papel de fuente y a un nodo final o destino el papel de sumidero. Asignando flujos a cada arista, el objetivo es repartir el flujo por los arcos de la red de forma óptima desde el nodo fuente hasta el nodo sumidero. En este proyecto nos centraremos en varios algoritmos de flujo máximo y su implementación. El trabajo se divide en una introducción general a los problemas que pueden ser resueltos utilizando estos algoritmos y una segunda parte que se centra en el algoritmo Ford Fulkenson y su rendimiento para grafos acíclicos, así como una revisión de otros algoritmos propuestos.

ABSTRACT: This work presents an introduction to the maximum flow problem. This problem frequently appears in many different areas and, although many solutions have been proposed, it still attracts interest of many researchers. The most usual applications are found in logistics (goods transportation), liquid or gas flow through interconnected pipes, electrical current through a network with different capacities and railway traffic, just to name a few. A typical question would be to calculate the maximum flow of electrical current that can be transmitted over a given electrical network. Using graph theory, the network is represented by a directed graph, with capacities given to itsl edges. The associated graph model has two distringuished nodes: a source node and a sink node. The solution to the problem is to split the flow optimally between all the edges from the source to the sink. In this project, we focus in several maximum flow algorithms and their implementation. The work can be divided in a first part that introduces examples and problems that can be addressed with these techniques, and a second part that focus on the Ford Fulkenson algorithm and its performance in acyclic graphs, as well as a brief revision of other proposed algorithms.