¡Esta es una revisión vieja del documento!
Análisis y casos
Tras la lectura del manual de usuario, a continuación puede conocer los diferentes tipos de análisis que se pueden realizar con Grafos. Para ello, el software incorpora un conjunto de algoritmos útiles que se organizan en las siguientes categorías:
- Caminos
- camino mínimo
- camino máximo
- Árboles
- árbol mínimo
- árbol máximo
- árbol de valor total mínimo
- árbol de valor total máximo
- Flujos
- flujo máximo
- problema de transbordo
- problema de asignación
- Rutas
- problema de viajante de comercio
- problema de m viajantes de comercio
- problema de rutas de vehículos (VRP)
- problema de rutas con vehículos capacitados (CVRP)
Algoritmos
Seguidamente se describirán los principales algoritmos incorporados en Grafos, prestando especial atención a su aplicación y utilidad.
¿qué es un algoritmo?
Una posible definición de algoritmo es un conjunto de reglas que permiten obtener un resultado determinado a partir de ciertas reglas definidas. Otra definición sería, algoritmo es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito. Ha de tener las siguientes características: legible, correcto, modular, eficiente, estructurado, no ambiguo y a ser posible se ha de desarrollar en el menor tiempo posible. El término proviene del matemático árabe Al'Khwarizmi, que escribió un tratado sobre los números. Este texto se perdió, pero su versión latina, Algoritmi de Numero Indorum, sí se conoce.
algoritmo de Dijkstra
camino mínimo/máximo, árbol mínimo/máximo, camino crítico
Edsger Wybe Dijkstra nació en Rotterdam, (Holanda) en 1930. Sus padres eran ambos intelectuales y él recibió una excelente educación. Su padre era químico y su madre matemática. En 1942, cuando Dijkstra tenía 12 años, entró en Gymnasium Erasminium, una escuela para estudiantes especialmente brillantes, donde dio clases, fundamentalmente, de Griego, Latín, Francés, Alemán, Inglés, biología, matemáticas y química. En 1945, Dijkstra pensó estudiar Derecho y trabajar como representante de Holanda en las Naciones Unidas.
Sin embargo, debido a su facilidad para la química, las matemáticas y la física, entró en la Universidad de Leiden, donde decidió estudiar física teórica. Durante el verano de 1951, asistió a un curso de verano sobre programación en la Universidad de Cambridge. A su vuelta empezó a trabajar en el Centro Matemático en Amsterdam, en marzo de 1952, donde se incrementó su creciente interés en la programación. Cuando terminó la carrera se dedicó a problemas relacionados con la programación. Pero uno de los problemas con que se encontró es que ser programador no estaba oficialmente reconocido como una profesión. De hecho, cuando solicitó una licencia de matrimonio en 1957, tuvo que señalar que su profesión era físico teórico.
Dijkstra continuó trabajando en el Centro Matemático hasta que aceptó un trabajo como desarrollador en Burroughs Corporation, en los Estados Unidos, a principio de la década de los 70. En 1972 ganó el Premio Turing ACM, y ,en 1974, el AFIPS Harry Good Memorial. Dijkstra se trasladó a Austin, Texas a principio de los 80. En 1984, se le ofreció un puesto en Ciencias de la Computación en la Universidad de Texas, donde permaneció desde entonces hasta que recientemente el 6 Agosto del 2002, Edsger W. Dijkstra, Professor Emeritus of Computer Sciences and Mathematics at The University of Texas en Austin, falleció en su hogar de Nuenen, (Netherlands). Es miembro honorario de la Academia Americana de Artes y Ciencias y de Real Academia Holandesa de Artes y Ciencias. Además es miembro distinguido de la Sociedad de Computación Británica. Finalmente es Doctor Honoris Causa en Ciencias por la Queen's University Belfast.
algoritmo de Dijkstra (ruta más corta - árbol mínimo - camino mínimo)
En 1956, Dijkstra anunció su algoritmo de caminos mínimos, después de haber estado trabajando con el ARMAC, el ordenador que el Centro Matemático poseía.
Más tarde propuso el algoritmo del árbol generador minimal. A principios de la década de los 60, Dijkstra aplicó la idea de la exclusión mutua a las comunicaciones entre una computadora y su teclado. Su solución de exclusión mutua ha sido usada por muchos procesadores modernos y tarjetas de memoria desde 1964, cuando IBM la utilizó por primera vez en la arquitectura del IBM 360. El siguiente problema del que se ocupó Dijkstra fue el de los filósofos comensales. En este problema, cinco filósofos están sentados en una mesa circular con un plato de arroz delante y un palillo a cada lado, de manera que hay cinco palillos en total. El problema trata sobre el uso de recursos comunes sin que los procesos (los filósofos) lleguen a una situación de bloqueo mutuo, inanición y que los recursos sean usados de la manera más eficiente por todos los procesos. También ayudó a fomentar la disciplina en la programación: “GOTO se puede considerar dañino. Cuanto más sentencias GOTO haya en un programa, más difícil es entender el código fuente”.
Una red de comunicaciones involucra un conjunto de nodos conectadas mediante arcos, que transfiere vehículos desde determinados nodos origen a otros nodos destino. La forma más común para seleccionar la trayectoria (o ruta) de dichos vehículos, se basa en la formulación de la ruta más corta. En particular a cada arco se le asigna un escalar positivo el cual se puede ver como su longitud.
Un algoritmo de trayectoria más corta, rutea cada vehículo a lo largo de la trayectoria de longitud mínima (ruta más corta) entre los nodos origen y destino. Hay varias formas posibles de seleccionar la longitud de los enlaces. La forma más simple es que cada enlace tenga una longitud unitaria, en cuyo caso, la trayectoria más corta es simplemente una trayectoria con el menor número de enlaces. De una manera más general, la longitud de un enlace puede depender de su capacidad de transmisión y su carga de tráfico.
La solución es encontrar la trayectoria más corta. Esperando que dicha trayectoria contenga pocos enlaces no congestionados; de esta forma los enlaces menos congestionados son candidatos a pertenecer a la ruta. Hay algoritmos de ruteo especializados que también pueden permitir que la longitud de cada enlace cambie en el tiempo, dependiendo del nivel de tráfico de cada enlace. De esta forma un algoritmo de ruteo se debe adaptar a sobrecargas temporales y rutear paquetes alrededor de nodos congestionados. Dentro de este contexto, el algoritmo de ruta más corta para ruteo opera contínuamente, determinando la trayectoria más corta con longitudes que varían en el tiempo.1)
El problema de la ruta más corta se puede resolver utilizando programación lineal sin embargo, debido a que el método simplex es de complejidad exponencial, se prefiere utilizar algoritmos que aprovechen la estructura en red que se tiene para estos problemas. Para ello, el algoritmo mantiene un conjunto S de nodos cuyos pesos finales de camino mínimo desde el nodo origen ya han sido determinados. A continuación se muestra el pseudocódigo del Algoritmo:
Dijkstra (G,s)
Inicializar
for cada v perteneciente a V[G]
do d[v] = infinito
p[v] = nulo
d[s] = 0
S = vacio
Q = V[G]
mientras Q no vacio
do u = nodo v con min d[v]
S = S unión u 'se añade al conjunto de nodos finalizados
for cada v perteneciente Adyacente u
Relajación
if d[v] > d[u] + w(u,v) then
d[v] = d[u] + w(u,v)
p(v) = u
algoritmo de Dijkstra (ruta más larga - árbol máximo - camino crítico)
El camino crítico estará formado por tareas críticas (nodos) cuya duración (coste del arco sucesor) determina la duración total de un proyecto. Si una tarea crítica se retrasa o su duración cambia durante la realización del proyecto, afectaría directamente a la duración total del proyecto y a su fecha de finalización.
Encontrar el camino crítico de la planificación de un proyecto es lo mismo que encontrar el camino más largo desde el nodo inicial (tarea inicial) al nodo final (última tarea); esto es, la mínima cantidad de tiempo necesaria para finalizar un proyecto.
El algoritmo de Dijkstra aunque fue diseñado para encontrar la ruta más corta se puede transformar fácilmente para encontrar la ruta más larga (camino crítico), cambiando simplemente su función objetivo. Del mismo modo, se encuentra el árbol máximo desde un nodo origen.
Puede encontrar más información en:
- Video sobre Dijkstra subtitulado en inglés (MPG 300 Mb) (University of Texas - VPRO TV)
- Dijkstra, E., A note on two problems in connexion with graphs, Numerische Mathematik 1, 269-271, 1959.
algoritmo de Bellman-Ford
camino mínimo - camino máximo
Lester Randolph Ford es uno de los pioneros en el campo de la programación de flujos en grafos. Es el hijo de L.R. Ford Sr. (quién también es un matemático distinguido) y nació el 23 de septiembre de 1927. L. R. Ford Sr es elogiado por su ejemplar trabajo en matemáticas al inventar una interpretación geométrica absolutamente maravillosa de la serie de Farey. También le acredita su trabajo 'Pointwise Discontinuous Functions' que era la base de su trabajo para un grado de M.S. del departamento de matemáticas en la universidad de Missouri-Colombia en 1912. Tal fue su contribución a las matemáticas, que en 1964 se estableció el Lester R. Ford Award para reconocer la contribución a las matemáticas de excelentes autores matemáticos publicados en The American Mathematical Monthly o Mathematics Magazine. Fue redactor de American Mathematical Monthly, de 1942-1946, y el presidente de Mathematical Association of America, 1947-1948. Ford Sr. y Ford Jr. son co-autores de Automorphic Functions cuál fue publicado cerca por McGraw-Hill en 1963.
Al continuar los pasos de su padre Ford Jr. también hizo una enorme contribución al campo de las matemáticas. Su trabajo con Delbert Ray Fulkerson (14 agosto de 1924 - 10 Enero de 1976) ha puesto la base de casi toda la investigación en flujos de grafos. El artículo de Ford y de Fulkerson (1956) con el problema de flujo máximo estableció el famoso teorema del flujo máximo - mínimo corte.
Mientras trabajó en RAND CORPORATION, Ford Jr publicó numerosos artículos que no solo establecieron la base de los flujos de red sino también la futura investigación en este campo. En 1962 Priceton University Press publicó su libro Flow in Networks con D. R. Fulkerson como co-autor. Este libro contiene todo su trabajo sobre redes.
La mayoría del trabajo de Ford lo hizo en la colaboración con Fulkerson, al parecer los dos hacían una buena asociación. Sin embargo, en 1956 presentó varios artículos firmados por él sólo. Ha sido el autor de diversos algoritmos que se han refinado con los años y que todavía se utilizan para solucionar la mayoría de problemas de grafos.
algoritmo de Bellman-Ford (camino mínimo)
Soluciona el problema de la ruta más corta o camino mínimo desde un nodo origen, de un modo más general que el Algoritmo de Dijkstra, ya que permite valores negativos en los arcos.
El algoritmo devuelve un valor booleano si encuentra un circuito o lazo de peso negativo. En caso contrario calcula y devuelve el camino mínimo con su coste. Para cada vértice v perteneciente a V, se mantiene el atributo d[v] como cota superior o coste del camino mínimo desde el origen s al vértice v. A continuación se muestra el pseudocódigo del algoritmo:
Bellman-Ford (G,s)
Inicializar
for cada v perteneciente a V[G]
do d[v] = infinito
p[v] = nulo
p[s] = 0
for i=1 to V[G]-1
do for cada arco (u,v) perteneciente a A[G]
Relajación
if d[v] > d[u] + w(u,v) then
d[v] = d[u] + w(u,v)
p(v) = u
for cada arco (u,v) chequea lazo de peso negativo
do if d[v] > d[u] + w(u,v) then
return FALSO 'el algoritmo no converge
return VERDADERO
algoritmo de Bellman-Ford (camino máximo)
El problema de la ruta más larga puede ser transformado en el de ruta más corta cambiando el signo de los costes de los arcos. De manera alternativa se puede transformar también cambiando los procesos de inicialización y relajación. En este caso el problema es inconsistente para circuitos de peso positivo.
Inicializar
for cada v perteneciente a V[G]
do d[v] = - infinito
p[v] = nulo
p[s] = 0
Relajación
if d[v] < d[u] + w(u,v) then
d[v] = d[u] + w(u,v)
p(v) = u
Puede encontrar más información en:
- Bellman, R. E., On a routing problem, quarterly of Applied Mathematics, 16, 87-90, 1958.
- Ford, L. R.Jr., Network Flow Theory, Paper P-923, RAND Corporation, Santa Monica, California, 1956.
algoritmo de Floyd-Warshall
camino mínimo entre todos los pares de nodos
Robert W. Floyd nació el 8 de junio de 1936 en Nueva York, es profesor de la Stanford University (B.A. Chicago 1955 B.S. Chicago 1958), y en 1978 fue galardonado con el prestigioso premio A.M. Turing que otorga la ACM para reconocer las contribuciones de naturaleza técnica realizadas a la comunidad informática. El premio le fue concedido por tener una influencia clara en las metodologías para la creación de software eficiente y fiable, y por ayudar a fundar las siguientes áreas de la informática: teoría de análisis sintáctico, semántica de los leguajes de programación, verificación automática de programas, síntesis automática de programas y análisis de algoritmos.
Fue uno de los inventores del deterministic linear time selection algorithm. También introdujo mejoras en los algoritmos quicksort y quickselect.
algoritmo de Floyd-Warshall (todos los caminos mínimos)
El problema que intenta resolver este algoritmo es el de encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es semejante a construir una tabla con todas las distancias mínimas entre pares de ciudades de un mapa, indicando además la ruta a seguir para ir de la primera ciudad a la segunda. Este es uno de los problemas más interesantes que se pueden resolver con algoritmos de grafos.
Existen varias soluciones a este problema y los algoritmos a aplicar dependen también de la existencia de arcos con pesos o costes negativos en el grafo. En el caso de no existir pesos negativos, sería posible ejecutar V veces el algoritmo de Dijkstra para el cálculo del camino mínimo, donde V es el número de vértices o nodos del grafo. Esto conllevaría un tiempo de ejecución de O(V^3) (aunque se puede reducir). Si existen arcos con pesos negativos, se puede ejecutar también V veces el Algoritmo de Bellman-Ford, una vez para cada nodo del grafo. Para grafos densos (con muchas conexiones o arcos) esto conllevaría un tiempo de ejecución de O(V^4).
El algoritmo de Floyd-Warshall ('All-Pairs-Shortest-Path' - Todos los caminos mínimos) ideado por Floyd en 1962 basándose en un teorema de Warshall también de 1962, usa la metodología de Programación Dinámica para resolver el problema. Éste puede resolver el problema con pesos negativos y tiempos de ejecución iguales a O(V^33); sin embargo, para ciclos de peso negativo el algoritmo tiene problemas. A continuación se muestra el pseudocódigo del algoritmo:
Floyd-Warshall (G)
Inicializar
D = A ' matriz de distancias = matriz de arcos
si i=j o Dij= infinito entonces Pi,j = nulo sino Pi,j=i 'matriz de caminos
for k = 1 to V
for i = 1 to V
for j = 1 to V
Di,j = min(Di,j , Di,k + Dk,j )
si min = Di,k + Dk,j entonces
Pi,j = Pk,j
fin
Este algoritmo se puede aplicar a multitud de problemas, incluyendo el diseño de circuitos, el diseño de rutas de transporte, aproximaciones al problema del viajante de comercio, o como base de otros algoritmos más complejos.
- Robert W. Floyd, Algorithm 97 (Shortest Path). Communications of the ACM, 5(6):345, 1962.
- Stephan Warshall, A theorem on boolean matrices. Journal of the ACM, 9(1):11-12, 1962.
- C. H. Papadimitriou, M. Sideri, On the Floyd-Warshall algorithm for logic programs shows that the Floyd-Warshall algorithm is essentially unique, J. of Logic Programming.
algoritmo de Kruskal
árbol de coste total mínimo/máximo
Joseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST) también llamado árbol recubridor euclídeo mínimo. Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.
El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles.
La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.
La formulación del MST también ha sido aplicada para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros).
Otra aplicación menos obvia es que el árbol de coste total mínimo puede ser usado como solución aproximada al problema del viajante de comercio (traveling salesman problem), recuerde que encontrar la solución óptima a este problema es NP-Hard. La manera formal de definir este problema es encontrar la trayectoria más corta para visitar cada punto al menos una vez. Nótese que si se visitan todos los puntos exactamente una vez, lo que se tiene es un tipo especial de árbol. En el ejemplo anterior, 12 de los 16 árboles son trayectorias de este tipo. Si se tiene una trayectoria que visita algunos vértices o nodos más de una vez, siempre se puede soltar algunos nodos del árbol. En general el peso del árbol total mínimo es menor que el del viajante de comercio, debido a que su minimización se realiza sobre un conjunto estrictamente mayor. Existen diferentes algoritmos y maneras de usar el árbol de coste total mínimo para encontrar la solución al problema del viajante de comercio (con resultados cercanos al óptimo).
algoritmo de Kruskal (árbol de coste total mínimo)
Dado un grafo G con nodos conectados por arcos con peso (coste o longitud): el peso o coste total de un árbol será la suma de pesos de sus arcos. Obviamente, árboles diferentes tendrán un coste diferente. El problema es entonces ¿cómo encontrar el árbol de coste total mínimo?
Una manera de encontrar la solución al problema del árbol de coste total mínimo, es la enumeración completa. Aunque esta forma de resolución es eficaz, no se puede considerar un algoritmo, y además no es nada eficiente.
Este problema fue resuelto independientemente por Dijkstra (1959), Kruskal (1956) y Prim (1957) y la existencia de un algoritmo polinomial (que todos ellos demostraron) es una grata sorpresa, debido a que un grafo con N vértices puede llegar a contener NN-2 subárboles. A lo largo de la historia se ha hecho un gran esfuerzo para encontrar un algoritmo rápido para este problema. El algoritmo de Kruskal es uno de los más fáciles de entender y probablemente el mejor para resolver problemas a mano.
El algoritmo se basa en una propiedad clave de los árboles que permite estar seguros de si un arco debe pertenecer al árbol o no, y usar esta propiedad para seleccionar cada arco. Nótese en el algoritmo, que siempre que se añade un arco (u,v), éste será siempre la conexión más corta (menor coste) alcanzable desde el nodo u al resto del grafo G. Así que por definición éste deberá ser parte del árbol.
Este algoritmo es de tipo greedy, ya que a cada paso, éste selecciona el arco más barato y lo añade al subgrafo. Este tipo de algoritmos pueden no funcionar para resolver otro tipo de problemas, por ejemplo para encontrar la ruta más corta entre los nodos a y b.
Para simplificar, se asumirán que existe un único árbol de coste total mínimo, aunque en muchos problemas puede existir más de una solución optima de igual valor total mínimo.
A continuación se muestra el pseudocódigo del algoritmo:
Kruskal (G)
E(1)=0, E(2)= todos los Arcos del grafo G
Mientras E(1) contenga menos de n-1 arcos y E(2)=0 do
De los arcos de E(2) seleccionar el de menor coste -->e(ij)
E(2)= E(2) - {e(ij)}
Si V(i), V(j) no están en el mismo árbol entonces
juntar los árboles de V(i) y de V(j) en uno sólo
end Si
end do
Fin del algoritmo
Este problema puede ser resuelto por diferentes algoritmos, e incluso en la actualidad sigue siendo tema de interés en investigaciones. Es interesante la lectura de los siguientes algoritmos (que resuelven este problema para diferentes supuestos), aunque son bastante complejos y probablemente no requiera utilizarlos a no ser que trabaje con grafos de grandes dimensiones:
- Karger, Klein, and Tarjan, A randomized linear-time algorithm to find minimum spanning trees, J. ACM, vol. 42, 1995, pp. 321-328.
- Fredman and Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, 31st IEEE Symp. Foundations of Comp. Sci., 1990, pp. 719-725.
- Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, vol. 6, 1986, pp. 109-122.
Puede encontrar más información en:
- J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society, 7:48-50, 1956.
algoritmo de Prim
árbol de coste total mínimo/máximo
Robert Prim en 1957 descubrió un algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST). Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka en 1926 mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia. Este problema también fue resuelto por Joseph B. Kruskal en 1956.
En los años 60 estos científicos del Math Center (Bell Labs) fueron los pioneros de la moderna teoría de secuenciación, particularmente en el análisis de algoritmos de aproximación y en secuenciación multiprocesador (Ed Coffman, Ron Graham, David Johnson y Mike Garey). En las siguientes tres décadas, se añadieron multitud de contribuciones que mejoraron la teoría general.
El algoritmo de Prim encuentra un árbol de peso total mínimo conectando nodos o vértices con arcos de peso mínimo del grafo sin formar ciclos.
Al igual que el algoritmo de Kruskal, el de Prim también ha sido aplicado para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros). También se ha utilizado para encontrar soluciones aproximadas a problemas NP-Hard como el del 'viajante de comercio'.
algoritmo de Prim (árbol de coste total mínimo)
Consiste en dividir los nodos de un grafo en dos conjuntos: procesados y no procesados. Al principio, hay un nodo en el conjunto procesado que corresponde a el equipo central; en cada interacción se incrementa el grafo de procesados en un nodo (cuyo arco de conexión es mínimo) hasta llegar a establecer la conexión de todos los nodos del grafo a procesar. A continuación se muestra el pseudocódigo del algoritmo:
Prim ( L [1..n , 1..n ]) : 'conjunto de arcos
'Inicialización: sólo el nodo 1 se encuentra en B
T =NULL 'T contendrá los arcos del árbol de extensión mínima Distmin[1]=-1
para i=2 hasta n hacer
más_próximo [ i ]=1
distmin [ i ]=L [ i , 1]
para i=1 hasta n -1 hacer
min=infinito
para j=2 hasta n hacer
si 0 <= distmin [ j ] < min entonces
min=distmin [ j ]
k=j
T=T union {{mas_próximo [ k ], k }}
distmin [ k ]= -1 'se añade k a B
para j=2 hasta n hacer
si L [ j , k ] < distmin [ j ] entonces
distmin [ j ]=L [ j , k ]
más_próximo [ j ]=k
devolver T
Algunos trabajos han comparado la eficiencia entre los algoritmos de Kruskal y de Prim:
Sea a es el número de arcos y n el número de nodos. El algoritmo de Kruskal requiere un tiempo que está en O(a log n). Para un grafo denso, a tiende a n(n-1)/2, por lo que el algoritmo requiere un tiempo que está en O(n2 log n), y el algoritmo de Prim puede ser mejor O(n2). En un grafo disperso, a tiende a n-1, por lo que el algoritmo de Kruskal requiere un tiempo que está en O(n log n) y el algoritmo de Prim es menos eficiente. Sin embargo, si el algoritmo de Prim se implementa con montículos, el tiempo requerido por este algoritmo está, como el de Kruskal, en O(a log n).
- Si a es aproximadamente igual a n (grafo con pocos arcos) conviene usar Kruskal
- Si a es aproximadamente igual a n2 (grafo denso) conviene usar Prim
En cualquier caso, la complejidad del algoritmo de Kruskal depende de la técnica de ordenación empleada. El algoritmo de Prim requiere más memoria que el algoritmo de Kruskal. Ambos algoritmos son relativamente fáciles de paralelizar. Puede encontrar más información en:
- R.C. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal, 36, pp. 1389-1401, 1957.
algoritmo de Ford-Fulkerson
flujo máximo
Se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, por tanto, puede considerarse como un conducto que tiene cierta capacidad de flujo. De igual modo que en redes eléctricas (Ley de Kirchhoff), la suma de flujos entrantes a un nodo, debe ser igual a la suma de los salientes (principio de conservación de energía), excepto para el nodo fuente y el nodo sumidero.
Por tanto, el problema de flujo máximo se enuncia como: ¿cuál es la tasa a la cual se puede transportar el material desde el nodo fuente al nodo sumidero, sin violar las restricciones de capacidad?. Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Una red de flujo es un grafo dirigido G=(V,E) donde cada arco (u,v) perteneciente a E tiene una capacidad no negativa. Se distinguen dos nodos: la fuente o nodo s, y el sumidero o nodo t. Si existen múltiples fuentes y sumideros, el problema se puede simplificar añadiendo una fuente común y un sumidero común. Este algoritmo depende de tres conceptos principales:
- Un camino de aumento, es una trayectoria desde el nodo fuente s al nodo sumidero t que puede conducir más flujo.
- La capacidad residual es la capacidad adicional de flujo que un arco puede llevar c_f (u,v) = c(u,v) - f(u,v)
- Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
El algoritmo es iterativo, se comienza con f(u,v)=0 para cada par de nodos y en cada iteración se incrementa el valor del flujo buscando un camino de aumento. El proceso se repite hasta no encontrar un camino de aumento. A continuación se muestra el pseudocódigo del algoritmo:
Ford-Fulkerson (G,s,t)
para cada arco (u,v) de E
f(u,v) = 0
f(v,u) = 0
mientras exista un camino p desde s a t en la red residual G_f
c_f (p) = min {c_f (u,v) : (u,v) está sobre p}
para cada arco (u,v) en p
f(u,v) = f(u,v) + c_f (p)
f(u,v) = -f(u,v)
Una variación del algoritmo de Ford-Fulkerson es el algoritmo de Edmonds-Karp (J. Edmonds; R.M. Karp - 1972). En éste, el 'camino de aumento' es elegido usando una búsqueda por niveles o en anchura (breadth-first search). El algoritmo de Edmonds-Karp requiere O(VE2) tiempo de computación, donde V es el número de nodos o vértices, y E el número de arcos del grafo.
Puede encontrar más información en:
- Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ. Princeton University Press, 1962.
- Edmonds, J. and Karp, R. M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM 19, 248-264, 1972.
- Berge, C. Two Theorems in Graph Theory. Proc. Nat. Acad. Sci. USA 43, 842-844, 1957.