Problemas de redes y flujos

Grado en Estadística TRABAJO FIN DE GRADO Problemas de Redes y Flujos Presentado por: Silvia Flores Ramos Tutor: Antonio Rufián Lizana Sevilla, junio de 2021 Índice general Prólogo ....................................... iii Resumen....................................... v Abstract....................................... vi ÍndicedeFiguras.................................. x 1. Teoría de Grafos 1 1.1. Introducción.................................. 1 1.2. El problema de los puentes de Königsberg . . . . . . . . . . . . . . . . . 1 1.3. Definiciones .................................. 3 1.4. Problema del camino más corto . . . . . . . . . . . . . . . . . . . . . . . 5 1.4.1. Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4.1.1. Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . . 6 1.4.1.2. Aplicación.......................... 7 1.4.1.3. Implementación del algoritmo en R . . . . . . . . . . . . 9 1.4.2. AlgoritmoA*............................. 10 1.4.2.1. Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . . 11 1.4.2.2. Aplicación.......................... 12 1.4.3. Algoritmo de Floyd . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4.3.1. Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . . 16 1.4.3.2. Aplicación.......................... 17 2. Árboles 25 2.1. Introducción.................................. 25 2.2. Definiciones .................................. 25 2.3. Propiedades.................................. 27 2.4. Problema del árbol de expansión de mínimo costo . . . . . . . . . . . . . 28 2.4.1. Algoritmo de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.1.1. Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . . 29 2.4.1.2. Aplicación.......................... 29 2.4.2. Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.2.1. Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . . 35 2.4.2.2. Aplicación.......................... 36 3. Flujos y Redes 43 3.1. Introducción.................................. 43 3.2. Reddeflujo.................................. 43 3.3. Problema de flujo máximo . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3.1. Algoritmo de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . 46 3.3.1.1. Definiciones previas . . . . . . . . . . . . . . . . . . . . 46 i 3.3.1.2. Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . . 47 3.3.1.3. Aplicación.......................... 48 3.3.1.4. Posible generalización: redes con múltiples fuentes y sumideros............................. 49 3.3.2. Algoritmo de Edmonds-Karp . . . . . . . . . . . . . . . . . . . . 50 3.3.2.1. Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . . 50 3.3.2.2. Aplicación.......................... 50 3.3.3. Algoritmo de Dinic . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.3.1. Definiciones previas . . . . . . . . . . . . . . . . . . . . 55 3.3.3.2. Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . . 55 3.3.3.3. Aplicación.......................... 56 Conclusiones 59 Bibliografía 61 ii Prólogo El Trabajo Fin de Grado que se presenta a continuación recibe el nombre de “Problemas de Redes y Flujos”, y ha sido elaborado entre enero y junio de 2021. Como se verá en el desarrollo del mismo, existen diversos algoritmos que resuelven este tipo de problemas, los cuales son más comunes de lo que se piensa en la vida cotidiana. Me gustaría agradecer a mi tutor Antonio por su orientación y entrega durante el proceso de realización de mi trabajo. También me gustaría dar las gracias a Pedro Luis Luque por facilitar la creación del TFG con su plantilla. A mis amigas y compañeras de carrera: gracias por vuestro apoyo incondicional, y por seguir unidas en este proceso que hemos compartido. Mi familia se merece un agradecimiento especial: vuestro apoyo y confianza en mí han conseguido que llegase hasta donde he llegado. Gracias como siempre. Silvia Flores Ramos iii Resumen 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. v Abstract 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. vi Índice de figuras 1.1. Mapa de Königsberg en la década de 1730 . . . . . . . . . . . . . . . . . 1 1.2. Diagrama de Euler. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Ejemplo de grafo. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4. Ejemplo de grafo. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5. Grafo para calcular su camino más corto. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6. Algoritmo de Dijkstra. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.7. Algoritmo de Dijkstra. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.8. Algoritmo de Dijkstra. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.9. Algoritmo de Dijkstra. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.10. Algoritmo de Dijkstra. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.11. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.12. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.13. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.14. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.15. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.16. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.17. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.18. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.19. Algoritmo A*. Fuente: Elaboración propia . . . . . . . . . . . . . . . . . . . . . . . . . . 16 vii 1.3. DEFINICIONES Figura 1.3: Ejemplo de grafo. Fuente: Elaboración propia Este tipo de grafo se denomina grafo dirigido. Definición 1.3.3 Un grafo dirigido odigrafo G = (V, E) consta de un conjunto V de vertices, un conjunto E de aristas, que son pares ordenados de elementos de V. En este caso, el conjunto de las aristas vendría dado por (A,B), (B,A) (A,D), (B,C), (C,B), (B,D), (C,D). Hasta ahora hemos visto ejemplos de grafos sin pesos, que son los menos comunes. Imaginemos que queremos representar mediante grafos los distintos caminos entre un determinado punto inicial y un punto final, siendo dichos caminos unos más cortos que otros. Lo más lógico sería dar unos pesos a estos caminos (aristas en el grafo) para así poder identificar cuál convendría elegir en cada paso para llegar antes a nuestro destino. Esto nos lleva a la definición de grafo ponderado: Definición 1.3.4 G es un grafo ponderado si a cada arista e de G se le asigna un número no negativo w(e) denominado peso olongitud de e. El peso (o longitud de un camino) en un grafo ponderado G se define como la suma de los pesos de las aristas del camino. Veamos un ejemplo: 4CAPÍTULO 1. TEORÍA DE GRAFOS 1.4. PROBLEMA DEL CAMINO MÁS CORTO Figura 1.4: Ejemplo de grafo. Fuente: Elaboración propia 1.4. Problema del camino más corto En Teoría de Grafos, uno de los problemas más importantes es encontrar el camino más corto, o lo que es lo mismo, el camino de menor longitud (o costo) entre dos vértices cualesquiera. Un claro ejemplo sería elegir el camino para llegar desde una ciudad A hasta una ciudad E, de manera que dispongamos de diferentes caminos y queramos recorrer la menor distancia posible. Representamos los pesos o costos de nuestro grafo como l(i, j). A continuación, se explicarán los algortimos más utilizados para resolver este tipo de problema, y los aplicaremos sobre el siguiente ejemplo para entender sus pasos: Figura 1.5: Grafo para calcular su camino más corto. Fuente: Elaboración propia CAPÍTULO 1. TEORÍA DE GRAFOS 5 1.4. PROBLEMA DEL CAMINO MÁS CORTO 1.4.1. Algoritmo de Dijkstra Un método para hallar dicho camino, muy útil sobre todo para grafos (dirigidos o no) con muchos nodos y pesos positivos es aplicar el algoritmo de Dijkstra. Definimos d ( i ): longitud más corta desde el nodo inicial x1 , de donde parte el camino hasta el momento. p(i): nodo anterior a xien el camino que se tiene en ese momento desde x1. 1.4.1.1. Pasos del algoritmo Paso 1 d(x1)=0 p(x1) = ∗(sin asignación) d(j) = ∞,p(j) = ∗,∀j6= 1 El nodo x1 es cerrado, es decir, su etiqueta es permanente y no modificable. Los demás, abiertos (sus etiquetas son provisionales y se pueden modificar) k= 1, que es el último nodo cerrado Paso 2 Se calcula d ( j ) = min{d ( j ) , d ( k ) + l ( k, j ) } para todos los xj para los que exista una arista (xk, xj) Paso 3 Cerrar nodo con menor d(j)de los nodos abiertos Si hay empate, se elige arbitrariamente Sea xiel nodo cerrado Paso 4 Para encontrar el predecesor del nodo xi , p ( i ), se consideran las aristas ( j, i )con j cerrado Se escoge el (j, i)tal que d(i)−l(i, j) = d(j) En caso de empate, escoger arbitrariamente p(i) = j Paso 5 Se cierra el nodo i Si todos los nodos están cerrados: STOP En caso contrario, k=iy volver al paso 2 6CAPÍTULO 1. TEORÍA DE GRAFOS 1.4. PROBLEMA DEL CAMINO MÁS CORTO 1.4.1.2. Aplicación En las siguientes figuras, se representan en color verde los nodos abiertos, y en rojo, los cerrados. El punto de partida es A , por lo que comenzamos cerrándolo. A continuación, se cierra el nodo conectado a A cuyo coste sea el mínimo de todos los conectados a este punto. En este caso, sería C. Figura 1.6: Algoritmo de Dijkstra. Fuente: Elaboración propia Tenemos que evaluar ahora las posibles salidas desde el nodo C . Como vemos, solo podemos tomar D . Observamos que de los nodos abiertos, el nodo D es el que tiene menor distancia respecto al origen, con p(i) = C, por lo que Dpasa a ser cerrado: Figura 1.7: Algoritmo de Dijkstra. Fuente: Elaboración propia Procedemos a evaluar las posibles salidas desde el nodo D . El nodo abierto con menor distancia respecto al nodo de origen es B , con p ( i ) = A , por lo que B pasa a ser cerrado: CAPÍTULO 1. TEORÍA DE GRAFOS 7 1.4. PROBLEMA DEL CAMINO MÁS CORTO Figura 1.8: Algoritmo de Dijkstra. Fuente: Elaboración propia Nos queda, por tanto, evaluar las posibles salidas desde B . Vemos que solo está conectado con E , que es el nodo de llegada y a su vez el único nodo que nos queda por cerrar. No obstante, la menor distancia desde este nodo respecto al origen se obtiene para p ( i ) = D , por lo que cerramos E: Figura 1.9: Algoritmo de Dijkstra. Fuente: Elaboración propia Obtenemos de esta forma el resultado final de nuestro problema aplicando el algoritmo de Dijkstra. Se muestra el camino más corto desde el nodo de origen A hasta el nodo de llegada Een color rojo: 8CAPÍTULO 1. TEORÍA DE GRAFOS 1.4. PROBLEMA DEL CAMINO MÁS CORTO Figura 1.10: Algoritmo de Dijkstra. Fuente: Elaboración propia 1.4.1.3. Implementación del algoritmo en R Procedemos a resolver el problema del camino más corto del grafo dado en la Figura 1.2 en R. Para ello, necesitamos crear una lista de cada arista con sus respectivos pesos. Es decir, creamos tres columnas: Las dos primeras, representan los vértices conectados. La tercera, apotará el valor del peso de la arista que los conecta. Escribimos los datos en un data frame utilizando la función edit Creamos a continuación un igraph a partir de este data frame de la siguiente manera: CAPÍTULO 1. TEORÍA DE GRAFOS 9 1.4. PROBLEMA DEL CAMINO MÁS CORTO Obtenemos así: Pasamos a calcular la distancia y el camino más corto entre los vértices A y E mediante el algoritmo de Dijkstra, que es el que utiliza igraph por defecto: Observamos que mediante igraph obtenemos el mismo resultado: el camino más corto entre los nodos AyEviene dado por {A, C, D, E}, con un coste de 7. 1.4.2. Algoritmo A* Otro método útil para resolver el problema del camino más corto es el Algoritmo A*. A diferencia del anterior, este algoritmo no comprueba que todas las rutan existen, por lo que no nos devolverá el camino óptimo, sino uno de los mejores. El Algoritmo A* utiliza una función de evaluación heurística h. 10 CAPÍTULO 1. TEORÍA DE GRAFOS 1.4. PROBLEMA DEL CAMINO MÁS CORTO Definición 1.4.1 Una función de evaluación heurística es una función que hace corresponder situaciones del problema con números Si el valor de la función h es h ( xi ) = 0 ∀i , entonces el algoritmo A* se comportará como el algoritmo de Dijkstra. Cabe destacar que este algoritmo se utiliza para grafos con pesos positivos, independientemente de si el grafo es dirigido o no lo es. Vamos a suponer que nuestro nodo inicial es x1, y el nodo de destino xn. La función de evaluación f(xi)se define usando otras dos funciones: g(xi): Indica el costo del camino desde x1hasta xi. h(xi): Indica el costo estimado desde el nodo xihasta el nodo final xn. Por otra parte, definimos un conjunto Q que contendrá a los nodos en exploración y un conjunto Pcon los nodos ya explorados. 1.4.2.1. Pasos del algoritmo Paso 1 Definimos x1nodo inicial Q={} P={} Paso 2 Calcular f(x1) Q={x1} Paso 3 Seleccionar xital que f(xi) = m´ınxk∈Qf(xk) P=P∪ {xi} Q={} Paso 4 Para cada nodo vecino xjde xi Calcular f(xj) Q=Q∪ {xj} Paso 5 Si xj tal que m´ınxj∈Qf ( xj )es el nodo objetivo xn : hacer P = P∪ {xn} y STOP. La solución es el camino en P En caso contrario, volver al paso 3 CAPÍTULO 1. TEORÍA DE GRAFOS 11 1.4. PROBLEMA DEL CAMINO MÁS CORTO 1.4.2.2. Aplicación Buscaremos de nuevo el camino más corto desde el nodo A hasta el nodo E. Como sabemos, para aplicar el algoritmo A* debemos dar una estimación de los costos desde cada uno de los nodos hasta el nodo final, en este caso E. Estas estimaciones vienen indicadas mediante la función hanteriormente explicada. Supondremos: h(xA)8 h(xB)4 h(xC)6 h(xD)2 h(xE)0 Se mostrarán en color rojo los nodos pertenecientes a P. Figura 1.11: Algoritmo A*. Fuente: Elaboración propia Figura 1.12: Algoritmo A*. Fuente: Elaboración propia Como Qúnicamente está formado por xA, lo añadimos directamente a P: 12 CAPÍTULO 1. TEORÍA DE GRAFOS 1.4. PROBLEMA DEL CAMINO MÁS CORTO Figura 1.13: Algoritmo A*. Fuente: Elaboración propia Los nodos vecinos de xAson xB,xCyxD: Figura 1.14: Algoritmo A*. Fuente: Elaboración propia Obtenemos m´ın xB,xC,xD {f(xB), f(xC), f(xD)}= 9 = f(xC) = f(xD) Como ni xC ni xD son el nodo objetivo, retomamos el paso 3, tomando xi como cualquiera de los dos anteriores. Elegimos xCal azar: CAPÍTULO 1. TEORÍA DE GRAFOS 13 1.4. PROBLEMA DEL CAMINO MÁS CORTO (i, j) m´ın{l(i, j), l(i, k) + l(k, j)} (1,2) m´ın{6,3 + ∞} = 6 (1,3) m´ın{3,3+0}= 3 (1,4) m´ın{7,3+2}= m´ın{7,5}= 5 (1,5) m´ın{10,3 + ∞} = 10 (2,1) m´ın{∞,∞+∞} =∞ (2,3) m´ın{∞,∞+ 0}=∞ (2,4) m´ın{∞,∞+ 2}=∞ (2,5) m´ın{4,∞+∞} = 4 (3,1) m´ın{∞,0 + ∞} =∞ (3,2) m´ın{∞,0 + ∞} =∞ (3,4) m´ın{2,0+2}= 2 (3,5) m´ın{∞,0 + ∞} =∞ (4,1) m´ın{∞,∞+∞} =∞ (4,2) m´ın{5,∞+∞} = 5 (4,3) m´ın{∞,∞+ 0}=∞ (4,5) m´ın{2,∞+∞} = 2 (5,1) m´ın{∞,∞+∞} =∞ (5,2) m´ın{∞,∞+∞} =∞ (5,3) m´ın{∞,∞+ 0}=∞ (5,4) m´ın{∞,∞+ 2}=∞ Por tanto, para k = 3 cambiamos el valor de la posición (1,4) por 5 en la matriz D3 , y sustituimos el valor de la misma posición en la matriz P3por k(3 en este caso). D3=         0 6 3 5 10 ∞0∞ ∞ 4 ∞ ∞ 0 2 ∞ ∞5∞0 2 ∞ ∞ ∞ ∞ 0         Paso 3 P3=         −1 1 3 2 2−2 2 2 3 3 −3 3 4 4 4 −4 5 5 5 5 −         Paso 4 k= 4 y volvemos al paso 2. Paso 2 20 CAPÍTULO 1. TEORÍA DE GRAFOS 1.4. PROBLEMA DEL CAMINO MÁS CORTO (i, j) m´ın{l(i, j), l(i, k) + l(k, j)} (1,2) m´ın{6,5+5}= m´ın{6,10}= 6 (1,3) m´ın{3,5 + ∞} = 3 (1,4) m´ın{5,5+0}= 5 (1,5) m´ın{10,5+2}= m´ın{10,7}= 7 (2,1) m´ın{∞,∞+∞} =∞ (2,3) m´ın{∞,∞+∞} =∞ (2,4) m´ın{∞,∞+ 0}=∞ (2,5) m´ın{4,∞+ 2}= 4 (3,1) m´ın{∞,2 + ∞} =∞ (3,2) m´ın{∞,2+5}= m´ın{∞,7}= 7 (3,4) m´ın{2,2+0}= 2 (3,5) m´ın{∞,2+2}= m´ın{∞,4}= 4 (4,1) m´ın{∞,0 + ∞} =∞ (4,2) m´ın{5,0+5}= 5 (4,3) m´ın{∞,0 + ∞} =∞ (4,5) m´ın{2,0+2}= 2 (5,1) m´ın{∞,∞+∞} =∞ (5,2) m´ın{∞,∞+ 5}=∞ (5,3) m´ın{∞,∞+∞} =∞ (5,4) m´ın{∞,∞+ 0}=∞ Por tanto, para k = 4 cambiamos en la matriz D4 el valor de la posición (1,5) por 5; el de la posición (3,2) por 7, y el valor de la posición (3,5) por 4. Además, sustituimos los valores de estas posiciones en la matriz P4por k(4 en este caso). D4=         0 6 3 5 7 ∞0∞ ∞ 4 ∞7 0 2 4 ∞5∞0 2 ∞ ∞ ∞ ∞ 0         Paso 3 P4=         −1 1 3 4 2−2 2 2 3 4 −3 4 4 4 4 −4 5 5 5 5 −         Paso 4 k= 5 y volvemos al paso 2. Paso 2 CAPÍTULO 1. TEORÍA DE GRAFOS 21 1.4. PROBLEMA DEL CAMINO MÁS CORTO (i, j) m´ın{l(i, j), l(i, k) + l(k, j)} (1,2) m´ın{6,7 + ∞} = 6 (1,3) m´ın{3,7 + ∞} = 3 (1,4) m´ın{5,7 + ∞} = 5 (1,5) m´ın{7,7+0}= 7 (2,1) m´ın{∞,4 + ∞} =∞ (2,3) m´ın{∞,4 + ∞} =∞ (2,4) m´ın{∞,4 + ∞} =∞ (2,5) m´ın{4,4+0}= 4 (3,1) m´ın{∞,4 + ∞} =∞ (3,2) m´ın{7,4 + ∞} = 7 (3,4) m´ın{2,4 + ∞} = 2 (3,5) m´ın{4,4+0}= 4 (4,1) m´ın{∞,2 + ∞} =∞ (4,2) m´ın{5,2 + ∞} = 5 (4,3) m´ın{∞,2 + ∞} =∞ (4,5) m´ın{2,2+0}= 2 (5,1) m´ın{∞,0 + ∞} =∞ (5,2) m´ın{∞,0 + ∞} =∞ (5,3) m´ın{∞,0 + ∞} =∞ (5,4) m´ın{∞,0 + ∞} =∞ Por tanto, para k= 5 no se modifica nada. Es decir, D5=D4. D5=         0 6 3 5 7 ∞0∞ ∞ 4 ∞7 0 2 4 ∞5∞0 2 ∞ ∞ ∞ ∞ 0         Paso 3 P5=P4, es decir, P5=         −1 1 3 4 2−2 2 2 3 4 −3 4 4 4 4 −4 5 5 5 5 −         Paso 4 Tenemos que k= 5 = n. Por tanto, STOP. Resultado final La matriz P5 proporciona la información correspondiente a los caminos mínimos entre todos los nodos, y D5 indica el coste asociado. Por ejemplo, el camino mínimo para ir 22 CAPÍTULO 1. TEORÍA DE GRAFOS 1.4. PROBLEMA DEL CAMINO MÁS CORTO desde el nodo 1 al nodo 4 es 1 − 3 − 4, con un coste de 5. De igual forma, podemos observar que el camino mínimo para ir desde el nodo 3 al nodo 5 es 3−4−5, con un coste de 4. Calculemos ahora el camino mínimo desde el nodo 1 al nodo 5 (camino calculado con el resto de algoritmos). Vemos que dicho camino viene dado por 1 − 3 − 4 − 5, con un costo de 7. CAPÍTULO 1. TEORÍA DE GRAFOS 23 Capítulo 2 Árboles 2.1. Introducción En este apartado nos centraremos en un tipo concreto de grafo: Árboles. Se introducirán definiciones básicas, así como propiedades de los mismos, que nos ayudarán a entender esta parte de la Teoría de Grafos y a resolver problemas de interés. 2.2. Definiciones Definición 2.2.1 Se llama subgrafo de un grafo G = ( V, A )a un grafo G0 = ( V0, A0 ), donde V0⊆VyA0⊆A. Definición 2.2.2 Se denomina camino a una secuencia de nodos unidos por aristas. Definición 2.2.3 Un ciclo es un camino que empieza y acaba en el mismo nodo, es decir, es un camino cerrado. Gracias a estas definiciones, podemos explicar fácilmente el concepto de árbol como sigue: Definición 2.2.4 Se llama árbol a un subgrafo con todos sus vértices conectados, pero que no contiene ciclos. Si dicho árbol incluye a todos los nodos, se denomina árbol de expansión. En un grafo dirigido, los árboles de expansión poseen un nodo "raíz", conectado a todos los demás nodos de forma única. De esta forma, un árbol podría representarse como sigue: 25 2.2. DEFINICIONES Figura 2.1: Árbol de 6 vértices. Fuente: Elaboración propia Como vemos, todos los vértices están conectados y forman un camino abierto, es decir, no se puede empezar y acabar en el mismo nodo (no contiene ciclos). Suponemos ahora que disponemos del mismo árbol, pero esta vez dirigido de la siguiente manera: Figura 2.2: Árbol dirigido. Fuente: Elaboración propia Observamos que el nodo 1 es el único que está conectado con el resto de nodos. Por tanto, 1 sería el denominado nodo “raíz”. Definición 2.2.5 Llamaremos hoja a todo nodo del árbol que tenga grado 1. Por tanto, los nodos hojas serán los nodos extremos del árbol. En el ejemplo anterior, los nodos hojas vienen representados por los nodos 4, 5 y 6. 26 CAPÍTULO 2. ÁRBOLES 2.3. PROPIEDADES 2.3. Propiedades A continuación, mostraremos algunas de las principales propiedades de los árboles, así como sus respectivas demostraciones: Teorema 2.3.1 Sea Tun árbol. Entonces 1. Todo árbol con al menos dos vértices tiene al menos dos hojas. 2. Si ves una hoja de T, entonces T− {v}formará otro árbol. Demostración. La demostración sería la siguiente: 1. En todo grafo con al menos dos vértices, cada extremo de un camino de al menos una arista tendrá como único nodo adyacente a su vecino en el camino. Todo grafo conexo con al menos dos vértices, tendrá al menos una arista, por lo que existirá un camino maximal. Los extremos de dicho camino serán hojas, por lo que el árbol tendrá al menos dos hojas. 2. Sea v una hoja del árbol T . Llamamos T0 = T− {v} . Una hoja solo es adyacente a otro nodo, ya que es de grado 1, por lo que no puede pertenecer a un camino entre dos vértices distintos a v . Por tanto, todo camino entre dos vértices u y w de T , también existirá en T0 , siempre que u6 = v y w6 = v . Por tanto, T0 también será un grafo conexo, y permanecerá sin ciclos, puesto que al eliminar un eje no se pueden formar ciclos nuevos.  Teorema 2.3.2 Sea Tun grafo de nnodos. Son equivalentes: 1. Tes conexo y sin ciclos. 2. Tes conexo y tiene n−1arcos. 3. Tes conexo, pero al quitar un arco se vuelve inconexo. 4. Tno tiene ciclos, pero al agregar un nuevo arco se forma un ciclo. 5. Solo hay un camino que conecte dos nodos. Demostración. Demostraremos que toda afirmación implica a la siguiente, así como que la útilma afirmación implica a la primera 1⇒2 Probemos por inducción que T tiene n− 1arcos. En primer lugar, si n = 1, el grafo solo tendrá un nodo y ningún eje, por lo que se verifica la hipótesis. Supongamos ahora que se verifica para n− 1. Sea por tanto el grafo T con n nodos. Entonces, al ser conexo y sin ciclos, tendrá forzosamente un nodo de grado 1 (nodo "raíz"), que llamaremos v . Entonces, el grafo T0 = T− {v} seguirá siendo conexo y sin ciclos, con n− 1vértices. Por hipótesis de inducción, el número de arcos de T0 será el número de nodos menos 1, es decir, n− 2. Por tanto, como el número de arcos de T será uno más que de T0 al haber eliminado uno, concluimos finalmente que T posee n−1ejes. CAPÍTULO 2. ÁRBOLES 27 2.4. PROBLEMA DEL ÁRBOL DE EXPANSIÓN DE MÍNIMO COSTO 2⇒3 Sean T1, ..., Tk las k componentes conexas de T , que serán conexas y sin ciclos. Llamamos E [ Ti ]al número de arcos de Ti y V ( Ti )al número de vértices. De esta forma, se tendrá que para cada i= 1, ..., k,|E[Ti]|=|V[Ti]| − 1. Por tanto, |E[T]|= k X i=1 |E[Ti]|= k X i=1 (|V[Ti]| − 1) = n−k Si se eliminase un arco de T , se tendría que |E [ T ] | = n− 2, es decir, tendríamos k= 2. Así, Ttendría dos componentes conexas, por lo que no sería conexo. 3⇒4 Al existir un ciclo en un grafo, se tiene que existen al menos dos caminos para ir de un nodo del ciclo a otro. Por hipótesis, al quitar un arco de T , el grafo deja de ser conexo, por lo que T no posee ningún ciclo. Además, al ser T conexo, se tiene que existe al menos un camino que une a todos los vértices. Por tanto, al añadir un nuevo eje entre dos nodos se obtiene un nuevo camino entre ellos, formando así un ciclo. 4⇒5 Razonaremos por reducción al absurdo. Supongamos que para un par de nodos u y v existen dos caminos que los conectan. Luego forzosamente debe existir un ciclo que los contenga, lo cual contradice la hipótesis (4). Supongamos ahora que existe un nodo w en T que no está conectado con ningún otro nodo. Entonces, al añadir un arco desde w , el grado de este nodo será 1. Se vuelve a contradecir la hipótesis (4) porque un nodo de grado 1 nunca puede formar parte de un ciclo. Por tanto, podemos concluir que existe un único camino entre cada par de nodos del grafo. 5⇒1 Al existir un camino entre cada par de nodos del grafo, T será obviamente conexo. Por hipótesis, no existe más de un camino entre ningún par de nodos, luego T no posee ningún ciclo.  2.4. Problema del árbol de expansión de mínimo costo Como vimos anteriormente, el árbol de expansión de un grafo es un subgrafo conexo y sin ciclos que contiene todos los nodos del grafo. Suponemos que este grafo es ponderado y tiene un peso o un costo asociado a las aristas. Si queremos encontrar el camino de mínimo costo entre dos vértices cualesquiera, en el árbol de expansión se traduce en solucionar el problema del árbol de expansión de mínimo costo (MST). Claramente, si el grafo tiene n vértices, el árbol de expansión poseerá n− 1aristas. Hallar el MST es otra manera de solucionar el problema del camino más corto visto en el capítulo anterior, pues al hallar el árbol de mínimo coste, se tiene un camino entre cada par de vértices con el menor coste posible. A continuación, se explicarán los algoritmos más utilizados para resolver este problema, y los aplicaremos sobre un grafo no dirigido y otro dirigido, que son: 28 CAPÍTULO 2. ÁRBOLES 2.4. PROBLEMA DEL ÁRBOL DE EXPANSIÓN DE MÍNIMO COSTO Figura 2.3: Grafos para el problema del MST. Fuente: Elaboración propia 2.4.1. Algoritmo de Prim Este algoritmo calcula el MST en grafos no dirigidos y ponderados. Si partimos de un grafo no conexo, el algoritmo devolverá el MST de una de sus componentes conexas. Por otra parte, si el grafo es dirigido, el algoritmo devolverá un árbol de expansión, sin asegurar que sea el de mínimo costo. 2.4.1.1. Pasos del algoritmo Suponemos un grafo Gcon nnodos. Paso 1 Elegir aleatoriamente un vértice i iforma parte del árbol Hallar el nodo jmás cercano a iy añadirlo al árbol k= 1 Paso 2 Si k=n−1, STOP. Todos los nodos están en el árbol Si k < n −1 • Tomar el vértice j no conectado al árbol que sea más cercano a cualquier vértice del árbol, es decir, el de menor costo •Añadir jal árbol Paso 3 k=k+ 1 y volver al paso 2 2.4.1.2. Aplicación En las siguientes figuras se representan en color rojo los nodos pertenecientes al árbol, y en verde, los que no. Se señalan también las aristas con el menor costo en cada paso. GRAFO NO DIRIGIDO CAPÍTULO 2. ÁRBOLES 29 2.4. PROBLEMA DEL ÁRBOL DE EXPANSIÓN DE MÍNIMO COSTO Paso 2 Si E6 = {} , se toma la arista de menor costo de E que una dos árboles diferentes sin formar ningún ciclo Paso 3 Si se tiene un único árbol, STOP. Se tiene el MST. En caso contrario, volver al paso 2. 2.4.2.2. Aplicación En las siguientes figuras se representan en color rojo los nodos pertenecientes al árbol, y en verde, los que no. Se señalan también las aristas con el menor costo en cada paso. GRAFO NO DIRIGIDO Comenzamos aplicando el algoritmo de Kruskal sobre el primer grafo, que es no dirigido. Se describen con diferentes colores los árboles definidos en el grafo. Como hay 7 nodos, partiremos de 7 árboles independientes: Figura 2.17: Algoritmo de Kruskal. Grafo no dirigido. Fuente: Elaboración propia E está formado por todas las aristas del grafo. Observamos que la arista de menor costo que une dos árboles diferentes (en este caso que une dos vértices cualesquiera) es aquella que conecta a los nodos FyG, con costo 1. Así: 36 CAPÍTULO 2. ÁRBOLES 2.4. PROBLEMA DEL ÁRBOL DE EXPANSIÓN DE MÍNIMO COSTO Figura 2.18: Algoritmo de Kruskal. Grafo no dirigido. Fuente: Elaboración propia Podemos unir a continuación los vérices A y B , ó B y D indistintamente, pues ambas aristas tienen peso 2 y estarían uniendo árboles diferentes en cada caso. Nos decantamos por la primera opción: Figura 2.19: Algoritmo de Kruskal. Grafo no dirigido. Fuente: Elaboración propia El siguiente paso sería unir el vértice D al árbol formado anteriormente (aquel formado por los nodos AyB), mediante la arista que une a Dcon B: CAPÍTULO 2. ÁRBOLES 37 2.4. PROBLEMA DEL ÁRBOL DE EXPANSIÓN DE MÍNIMO COSTO Figura 2.20: Algoritmo de Kruskal. Grafo no dirigido. Fuente: Elaboración propia De las aristas restantes pertenecientes a E , la que tiene menor costo es aquella que conecta a C con el árbol formado por los nodos A , B y D (mediante la arista que une a Ccon A, que tiene costo 3): Figura 2.21: Algoritmo de Kruskal. Grafo no dirigido. Fuente: Elaboración propia Nos encontramos en el mismo caso que antes. Podemos comenzar uniendo los nodos E y G ó A y F , pues ambas aristas tienen el costo mínimo de E , que es 4. Claramente el resultado será el mismo. Tomando la primera opción de nuevo: 38 CAPÍTULO 2. ÁRBOLES 2.4. PROBLEMA DEL ÁRBOL DE EXPANSIÓN DE MÍNIMO COSTO Figura 2.22: Algoritmo de Kruskal. Grafo no dirigido. Fuente: Elaboración propia Unimos los dos árboles restantes mediante la arista que acabamos de mencionar, la que conecta AyFcon costo 4. Figura 2.23: Algoritmo de Kruskal. Grafo no dirigido. Fuente: Elaboración propia Se tiene ya un árbol único. Por tanto, STOP. Resultado final El árbol de expansión de mínimo costo dado por el algoritmo de Kruskal sería el siguiente: CAPÍTULO 2. ÁRBOLES 39 2.4. PROBLEMA DEL ÁRBOL DE EXPANSIÓN DE MÍNIMO COSTO Figura 2.24: Algoritmo de Kruskal. Grafo no dirigido. Resultado final. Fuente: Elaboración propia GRAFO DIRIGIDO Utilizamos la misma mecánica para calcular el MST del grafo dirigido: Figura 2.25: Algoritmo de Kruskal. Grafo dirigido. Fuente: Elaboración propia Figura 2.26: Algoritmo de Kruskal. Grafo dirigido. Fuente: Elaboración propia 40 CAPÍTULO 2. ÁRBOLES 2.4. PROBLEMA DEL ÁRBOL DE EXPANSIÓN DE MÍNIMO COSTO Figura 2.27: Algoritmo de Kruskal. Grafo dirigido. Fuente: Elaboración propia Figura 2.28: Algoritmo de Kruskal. Grafo dirigido. Fuente: Elaboración propia Resultado final El árbol de expansión de mínimo costo dado por el algoritmo de Kruskal sería el siguiente: Figura 2.29: Algoritmo de Kruskal. Grafo dirigido. Resultado final. Fuente: Elaboración propia CAPÍTULO 2. ÁRBOLES 41 Capítulo 3 Flujos y Redes 3.1. Introducción En esta sección introduciremos las redes de flujo, que son un modelo que permite representar sistemas tales como mapas de carreteras, redes de tuberías o conexiones de red, desde un punto de vista abstracto. Estos sistemas se pueden asimilar a grafos cuyos arcos tienen una capacidad máxima y por los cuales transitan elementos (coches, líquidos, datos, etc.). Sobre las redes de flujo se pueden plantear numerosos problemas, entre ellos el de la búsqueda del flujo máximo, que consiste en encontrar la máxima cantidad de elementos que se pueden enviar entre dos vértices de la red. Nos centraremos tanto en el planteamiento de este tipo de problema como en su resolución gracias a varios algoritmos. 3.2. Red de flujo Definición 3.2.1 Una red de flujo es un grafo dirigido G = ( V, E )en el cual cada arco ( u, v ) ∈E tiene una capacidad no negativa c ( u, v ) ≥ 0. Se asume que si ( u, v ) /∈E , entonces c ( u, v ) = 0. En toda red de flujo se distinguen dos vértices especiales, la fuente syeldestino osumidero t. Mostraremos a continuación un ejemplo de red de flujo, en el que el valor de cada arco representa su capacidad: 43 3.2. RED DE FLUJO Figura 3.1: Red de flujo (con capacidad). Fuente: Elaboración propia Esta red de flujo podría representar, por ejemplo, una red de pozos, en la que se bombea agua hacia un pozo principal, representado por el vértice t . Suponemos que la capacidad de esta red se mide en litros por segundo. De esta forma, podemos decir que la capacidad de la tubería que conecta el pozo fuente ( s ) hacia el pozo v1 es de 11 litros por segundo; la capacidad de la tubería que parte desde el pozo v3 hacia el pozo v4 es de 9 litros por segundo; la de la tubería que se dirige desde éste último pozo hacia el pozo principal es de 6 litros por segundo... Dada una determinada red de flujo, un flujo para ella es una función f : V×V→R que satisface las siguientes condiciones: Restricción de capacidad: ∀u, v ∈V : f ( u, v ) ≤c ( u, v ). La cantidad f ( u, v ), que puede ser positiva, negativa o nula, es llamada flujo desde el vértice u al vértice v . Esta restricción impone un límite a la red en cuanto a la capacidad de flujo que se puede enviar por cada arco. Simetría: ∀u, v ∈V : f ( u, v ) = −f ( v, u ). Se trata de una propiedad añadida para facilitar la notación. Básicamente, nos dice que si un flujo f circula desde el vértice u hasta el vértice v , entonces ese mismo flujo, pero con signo negativo, puede suponerse que circula en sentido inverso (de vau). Conservación de flujo: ∀u∈V−{s, t} : Pv∈Vf ( u, v ) = 0. Es decir, para cualquier vértice, sin tener en cuenta la fuente y el destino, la suma del flujo saliente de dicho vértice es nula. Si combinamos las dos últimas propiedades, podemos llegar a la conclusión de que para cualquier vértice, sin contar s y t , se cumple que entra y sale la misma cantidad de flujo. Esto es: ∀u∈V− {s, t}:f(u, V ) = f(V, u) = 0 Además, podemos ya definir el valor del flujo fde la siguiente manera: |f|=Pv∈Vf(s, v), es decir, el valor de un flujo es la cantidad total de flujo que parte desde la fuente. En la siguiente figura mostraremos la misma red de flujo expuesta anteriormente, pero con un flujo concreto. Cada arco lleva asociado un par de valores que representan, respectivamente, el flujo y la capacidad de dicho arco. 44 CAPÍTULO 3. FLUJOS Y REDES 3.3. PROBLEMA DE FLUJO MÁXIMO Figura 3.2: Red de flujo (con flujo y capacidad). Fuente: Elaboración propia Volviendo al caso anterior, podemos decir que aunque la tubería que conecta el pozo fuente con el primer pozo tiene capacidad de 11 litros por segundo, ésta recibe un flujo de 6 litros por segundo; el tercer pozo, v3 , envía un litro por segundo hacia el pozo v4 , aunque podría enviar hasta 9 litros por segundo; éste último pozo expulsa hacia el pozo de destino todo el agua que puede, esto es, 6 litros por segundo... 3.3. Problema de flujo máximo Tras esta introducción a las redes de flujos y su aplicación, podríamos preguntarnos: ¿Cuál es la cantidad máxima de flujo que se puede enviar, en una determinada red de flujo, desde el vértice fuente s al vértice destino t ? Encontrar la solución a esta cuestión es encontrar la solución del denominado problema de flujo máximo. El problema de maximizar un flujo a lo largo de las aristas de una red de flujo fue estudiado por primera vez por el matemático estadounidense Ted Harris en 1955. Este estudio, que en un principio fue catalogado como información confidencial del Estado, modelizaba la red ferroviaria soviética en el área comprendida entre Moscú, el mar Báltico, Polonia, Rumanía y el mar Negro: Figura 3.3: Red de ferrocarriles rusos de 1955 El planteamiento del problema era el siguiente: CAPÍTULO 3. FLUJOS Y REDES 45 3.3. PROBLEMA DE FLUJO MÁXIMO Figura 3.11: Algoritmo de Edmonds-Karp. Fuente: Elaboración propia Buscamos a continuación el segundo camino incremental. Volvemos a crear un árbol como el anterior, pero uniremos aquellos nodos conectados por aristas con coste distinto de cero: Figura 3.12: Algoritmo de búsqueda en anchura. Fuente: Elaboración propia Al ser c12 = 0, no podemos volver a tomar el nodo 2de nuevo para encontrar un camino. De esta forma, como muestra el árbol, el segundo camino incremental viene dado por C={1,4,3,6}, con ∆ = m´ın{4,2,1}= 1. 52 CAPÍTULO 3. FLUJOS Y REDES 3.3. PROBLEMA DE FLUJO MÁXIMO Figura 3.13: Algoritmo de Edmonds-Karp. Fuente: Elaboración propia Creamos de nuevo el árbol con los nodos disponibles (aquellos conectados por aristas cuyo coste es distinto a 0): Figura 3.14: Algoritmo de búsqueda en anchura. Fuente: Elaboración propia Observamos que el tercer camino incremental viene dado por C = { 1 , 4 , 5 , 6 } , con ∆ = m´ın{3,2,4}= 2. CAPÍTULO 3. FLUJOS Y REDES 53 3.3. PROBLEMA DE FLUJO MÁXIMO Figura 3.15: Algoritmo de Edmonds-Karp. Fuente: Elaboración propia Formando el árbol de nuevo, Figura 3.16: Algoritmo de búsqueda en anchura. Fuente: Elaboración propia creamos el tercer camino de incremental: C = { 1 , 4 , 3 , 5 , 6 } , con ∆ = m´ın{ 1 , 1 , 2 , 2 } = 1. 54 CAPÍTULO 3. FLUJOS Y REDES 3.3. PROBLEMA DE FLUJO MÁXIMO Figura 3.17: Algoritmo de Edmonds-Karp. Fuente: Elaboración propia Ya no quedan más caminos por recorrer desde 1hasta 6Por tanto, el problema ha terminado, y el flujo máximo viene dado por 7, al igual que antes. 3.3.3. Algoritmo de Dinic El algoritmo de Dinic es similar al algoritmo de Edmonds-Karp en lo que respecta al uso de los caminos incrementales más cortos. Para este algoritmo se usaremos muchas de las definiciones vistas anteriormente, aunque debemos hacer uso de otras nuevas que plantearemos a continuación. 3.3.3.1. Definiciones previas Definición 3.3.4 El grafo de nivel del grafo residual Gf es el grafo GL = (( V, EL ) , cf|EL, s, t ), donde EL = { ( u, v ) ∈Ef : dist ( v ) = dist ( u )+1 } y donde, a su vez, dist ( v )es la distancia del camino incremental más corto de v a s en Gf y Ef={(u, v)∈V×V:cf(u, v)>0}. Definición 3.3.5 Un flujo bloqueante es un flujo desde s a t de longitud f tal que el grafo G0 = (( V, E0 L ) , s, t ), donde E0 L = { ( u, v ) : f ( u, v ) < cf|EL ( u, v ) } no contiene caminos de sat. 3.3.3.2. Pasos del algoritmo Consideramos G = ( V, E )el grafo de n nodos, donde el nodo 1es el inicial y el nodo n es el final. Cada arista (i, j)tiene una capacidad máxima de flujo, cij Paso 1 Establecer f(e)=0,∀e∈E Paso 2 Contruir el grafo de nivel GL a partir del grafo residual Gf , el cual se obtiene de G Si dist(t)=+∞, parar y devolver f Paso 3 CAPÍTULO 3. FLUJOS Y REDES 55 3.3. PROBLEMA DE FLUJO MÁXIMO Encontrar un flujo bloqueante de longitud f0en GL Paso 4 Sumar la cantidad f0al flujo f 3.3.3.3. Aplicación Llamamos G al grafo dado en la Figura 3.4, en el que renombramos los nodos como 1,2, 3,4,5y6, siendo 1la fuente y 6el destino. Como se indica en el Paso 1, todos los flujos que circulan en esta red deben tomar el valor 0. Al lado, mostramos el grafo residual Gf , así como el grafo de nivel GL, en el que los vértices indican los valores dist(v): Figura 3.18: Algoritmo de Dinic. Fuente: Elaboración propia Observamos que el grafo de nivel muestra en sus nodos los niveles del grafo original tras haber calculado el bloqueo de flujo. Nótese que el bloqueo de flujo está constituido por {1,2,3,6}con 3 unidades de flujo {1,4,3,6}con 1 unidad de flujo {1,4,5,6}con 2 unidades de flujo Por lo tanto, el bloqueo del flujo es de 6 unidades y el valor del flujo |f| es 6. Observamos que el algoritmo solo toma en este ejemplo estos 3 bloqueos de flujos, pues según la definición de nivel, se debe ir a un niel u+ 1. Repetimos el proceso con el grafo resultante: Figura 3.19: Algoritmo de Dinic. Fuente: Elaboración propia En este caso, el bloqueo está constituido por 56 CAPÍTULO 3. FLUJOS Y REDES 3.3. PROBLEMA DE FLUJO MÁXIMO {1,4,3,5,6}con 1 unidad de flujo Por lo tanto, el bloque de flujo es de una unidad y el valor del flujo |f|es de 6+1=7. Repetimos de nuevo el proceso: Figura 3.20: Algoritmo de Dinic. Fuente: Elaboración propia Observamos que desde el nodo inicial no se puede conseguir un camino hasta el nodo de destino en Gf . De esta manera, el algoritmo termina, aportando un flujo máximo de 7. CAPÍTULO 3. FLUJOS Y REDES 57 Conclusiones Este trabajo ha sido elaborado con el fin de introducir al lector en el planteamiento y resolución de problemas que podemos describir como Problemas de Redes y Flujos. Se pretende que las situaciones y ejemplos incluidos en el proyecto permitan entender mejor no sólo la manera de plantearlos y las conclusiones finales que se han obtenido, sino también el funcionamiento de los algoritmos explicados. Como para entender “Redes y Flujos” es necesario un conocimiento previo de “Teoría de Grafos” y “Árboles”, he visto oportuno explicar y aplicar algoritmos para resolver los problemas más importantes en estas ramas. 59 Bibliografía M. E. Abajo Casado. Grafos con tamaño máximo y cintura inferiormente acotada. 2009. URL https://idus.us.es/bitstream/handle/11441/24322/2009abajografo.pdf?sequence= 1&isAllowed=y. J. ADIEGO RODRIGUEZ and N. ZIVIANI. Diseño de algoritmos con implementaciones en Pascal y C. Editorial Paraninfo, 2007. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows. 1988. M. F. Alvarez Nuñez. Teoría de grafos. 2013. URL http://repobib.ubiobio.cl/jspui/ bitstream/123456789/1953/3/Alvarez_Nunez_Marcelino.pdf. R. Balakrishnan and K. Ranganathan. A textbook of graph theory. Springer Science & Business Media, 2012. J. Barelles Menes. Algoritmos para la resolución de problemas en redes. 2017. URL http://repositori.uji.es/xmlui/bitstream/handle/10234/173687/TFG_2017_ BarellesMenes_Jorge.pdf?sequence=1. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399–404, 1956. L. R. Ford and D. R. Fulkerson. A simple algorithm for finding maximal network flows and an application to the hitchcock problem. Canadian journal of Mathematics, 9: 210–218, 1957. A. Gibbons. Algorithmic graph theory. Cambridge university press, 1985. J. L. Gross and J. Yellen. Graph theory and its applications. CRC press, 2005. D. Jungnickel and D. Jungnickel. Graphs, networks and algorithms. Springer, 2005. URL https://link.springer.com/content/pdf/10.1007/978-3-540-72780-4.pdf. 61