modelosoptimizacionredes

Modelos de Optimizacin de Redes 1 Docente Ing. J. Paredes C.

UNIVERSIDAD SAN PEDRO Ingeniera Industrial

Investigacin Operativa II

MODELOS DE OPTIMIZACION DE REDES

Los modelos de redes son aplicables a una extensa variedad de problemas de decisin, los cuales pueden ser

modelados como problemas de optimizacin de redes que pueden ser eficiente y efectivamente resueltos. Algunos de estos problemas de decisin son realmente problemas fsicos, tales como el transporte o flujo de bienes

materiales, redes de comunicacin, vuelos de los aeropuertos, rutas de navegacin de los cruceros, estaciones de

bombeo que transportan fluido a travs de tuberas, rutas entre ciudades, redes de conductos y todas aquellas

situaciones que puedan representarse mediante una red donde los nodos representan las estaciones o las ciudades, los arcos los caminos, las lneas areas, los cables, las tuberas y el flujo lo representan los camiones, mensajes y

fluidos que pasan por la red. Con el objetivo de encontrar la ruta ms corta si es una red de caminos o enviar el

mximo fluido si es una red de tuberas. Sin embargo, muchos problemas de redes son ms que una representacin

abstracta de procesos o actividades, tales como el camino crtico en las actividades entre las redes de un proyecto gerencial.

La familia de redes de los problemas de optimizacin incluye los siguientes prototipos de modelos:

Problemas de asignacin, camino crtico, flujo mximo, camino ms corto, transporte y costo mnimo de flujos. Los problemas son establecidos fcilmente mediante el uso de arcos de redes y de los nodos.

Uno de los mayores desarrollos recientes en investigacin de operaciones (IO) ha sido el rpido avance

tanto en la metodologa como en la aplicacin de los modelos de optimizacin de redes. La aparicin de algunos algoritmos ha tenido un impacto importante, al igual que las ideas de ciencias de la computacin acerca de

estructuras de datos y la manipulacin eficiente de los mismos. En consecuencia, ahora se dispone de algoritmos y

paquetes de computadora y se usan en forma rutinaria para resolver problemas muy grandes que no se habran

podido manejar hace dos o tres dcadas.

Cuando se trata de encontrar el camino ms corto entre un origen y un destino, la tcnica, algoritmo o el

modelo adecuado es el de la ruta ms corta; aunque existen otros modelos de redes como el rbol de expansin

mnima, flujo mximo y flujo de costo mnimo cada uno abarca un problema en particular. En esta separata se mencionan los modelos de redes existentes y los problemas que abarca cada uno de ellos, adems se describen los

algoritmos que aplican estos modelos para encontrar la solucin optima al problema. Utilizando la terminologa

utilizada para representarlos como una red.

NOTACIN Y TERMINOLOGA

Definicin de Red: Una red consiste en una serie de nodos(o vrtices) enlazados con arcos (o ligaduras, aristas, o ramas). La notacin para describir una red es (N, A), donde N es el conjunto de nodos y A es el conjunto de arcos. Por ejemplo, la red de la figura siguiente se describe como sigue:

N = {1, 2, 3, 4, 5}

A = {(1,2), (1,3), (2,3), (2,5), (3,4), (3,5), (4,2), (4,5)}

Los arcos se etiquetan para dar nombres a los nodos en sus puntos terminales, por ejemplo, 13 es el arco entre los

nodos 1 y 3.

En un problema de programacin lineal, las redes pueden representar un conjunto de estaciones, campos petrolferos, almacenes, fabricas, sucursales, ciudades, interconectadas entre s a travs de caminos, conductos,

tuberas que permiten fluir productos para la comercializacin o la distribucin.

Ejemplo de una red (N, A)

Con cada red se asocia algn tipo de flujo (por ejemplo, flujo de productos petroleros en un oleoducto y flujos de trfico de automviles en carretearas). En general, el flujo en una red est limitado por la capacidad de sus arcos,

que pueden ser finitos o infinitos.

Figura No 1: Representacin de una red




Red de distribucin: Una coleccin finita de nodos (cada uno de los cuales representa una planta, un almacn o una tienda detallista); un arco indica la posibilidad de enviar bienes entre los dos nodos conectados por el arco.

Red de flujo: Entendiendo una red de flujo como un grafo dirigido, donde la fuente es quien produce o inicia el traspaso de algn material o producto por los arcos, estos ltimos, vistos como caminos o conductos y tomando en

cuenta la ley de corrientes de Kirchoff, donde, la suma de flujos entrantes a un vrtice debe ser igual a la suma de

flujos saliendo del vrtice.

Nodo: Es usualmente llamado vrtice, o punto. Es usualmente representado por un crculo de una red de distribucin. En las redes de distribucin o transporte, estos deberan ser las localidades o las ciudades en un mapa,

plantas, almacenes o tiendas al menudeo.

Arco: Es usualmente llamado borde o flecha. Lnea de una red de distribucin que conecta un par de nodos. Se le utiliza para representar una ruta vlida desde el nodo de origen al nodo distribucin. La cabeza es el destino, y la cola el origen. La cabeza y la cola son nodos que pueden estar tanto al origen como al

final. En las redes de transporte, los arcos podran ser los caminos, los canales de navegacin en un ro, o los

patrones de vuelo de un avin. Los arcos proporcionan la conectividad entre los nodos. Una calle de una sola

direccin podra ser representada por un arco, mientras que una calle de dos direcciones podra representada por un arco sin direccin o por dos arcos que apuntan a direcciones opuestas.

Arcos Dirigidos: Se dice que un arco es dirigido cuando el arco tiene flujo en una direccin (como en una calle de un sentido). La direccin se indica agregando una cabeza de flecha al final de la lnea que representa el arco. Al etiquetar un arco dirigido con el nombre de los nodos que une, siempre se coloca primero al nodo de donde viene

y despus el nodo a donde va, esto es, un arco dirigido del nodo 1 al nodo 2 debe etiquetarse como 12 y no como 21.

Otra Manera es 1 2.

Arcos no Dirigidos: Si el flujo a travs de un arco se permite en ambas direcciones (como una tubera que se puede usar para bombear fluido en ambas direcciones), se dice que es un arco no dirigido. Tambin se les llama ligadura. Aunque se permita que el flujo a travs de un arco no dirigido ocurra en cualquier

direccin, se supone que ese flujo ser en una direccin, en la seleccionada, y no se tendr flujos simultneos en

direcciones opuestas.

Ruta o Trayectoria: Es una sucesin de arcos distintos que unen dos nodos pasando por otros nodos, independientemente de la direccin de flujo de cada arco.

Una coleccin de arcos formados por una serie de nodos adyacentes Los nodos estn conectados si existe una ruta entre ellos.

Trayectoria Dirigida o Red Dirigida: Una trayectoria dirigida del nodo i al nodo j, es una sucesin de arcos cuya direccin (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j, a travs de esta

trayectoria es factible. Una red es dirigida si tiene todos sus arcos dirigidos.

Trayectoria no Dirigida o Red no Dirigida: Una trayectoria no dirigida del nodo i al nodo j es una sucesin de arcos cuya direccin (si la tienen) pueden ser hacia o desde el nodo j. Con frecuencia alguna trayectoria no

dirigida tendr algunos arcos dirigidos hacia el nodo j y otros desde l (es decir, hacia el nodo i).

Ciclo: Un ciclo se produce cuando al partir de un nodo por un cierto camino se vuelve al mismo nodo por otra ruta. Por ejemplo en la figura No 1, los arcos (2,3), (3,5) y (5,2) forman un bucle o circuito cerrado.

Un ciclo es dirigido si consiste en una ruta dirigida, por ejemplo (2,3), (3,4) y (4,2) en la figura No 1.

Red conectada es aquella en que cada dos nodos distintos estn enlazados al menos por una ruta. La red de la figura es un ejemplo de este tipo.

Red Conexa: Una red conexa es una red en la que cada par de nodos est conectado. Se dice que dos nodos estn conectados si la red contiene al menos una trayectoria no dirigida entre ellos. Se debe resaltar que no es necesaria

que la trayectoria sea dirigida aun cuando la red sea dirigida. La figura No 1 representa una red conexa.

rbol: Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un rbol. En un grafo con n vrtices, los rboles tienen exactamente n - 1 aristas, y hay nn-2 rboles posibles. Su importancia radica en que los rboles son




grafos que conectan todos los vrtices utilizando el menor nmero posible de aristas. Un importante campo de

aplicacin de su estudio se encuentra en el anlisis filogentico, el de la filiacin de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguacin del parentesco entre especies .

Un rbol es una red conectada que puede consistir slo en un subconjunto de todos los nodos en ella, donde no se

permiten ciclos.

rbol de Expansin: es una red conexa para los n nodos, que contiene ciclos no dirigidos. Todo rbol de expansin tiene justo n-1 arcos, ya que este es el nmero mnimo de arcos necesarios para tener una red conexa y el

mximo nmero posible para que no haya ciclos no dirigidos.

Flujo: Corresponde a la cantidad que debe transportarse desde un nodo i a un nodo j a travs de un arco que los conecta. La siguiente notacin es usada:

Xij= cantidad de flujo

Uij= cota mnima de flujo que se debe transportar Lij= cota mxima de flujo que se puede transportar.

Nodos adyacentes: Un nodo j es adyacente con un nodo i si existe un arco que une el nodo j con el nodo i.

Ruta: Una coleccin de arcos formados por una serie de nodos adyacentes Los nodos estn conectados si existe una ruta entre ellos.

Capacidad de Arco: Es la cantidad mxima de flujo (quizs infinito) que puede circular en un arco dirigido.

Nodo Fuente: (o nodo de origen) tiene la propiedad de que el flujo que sale del nodo excede al flujo que entra a l.

Nodo Demanda: (o nodo destino) es el caso contrario al nodo fuente, donde el flujo que llega excede al que sale de l.

Nodo de Trasbordo: (o nodo intermedio) satisface la conservacin del flujo, es decir, el flujo que entra es igual al que sale.

La importancia de los modelos de redes: o Muchos problemas comerciales pueden ser resueltos a travs de modelos redes o El resultado de un problema de redes garantiza una solucin entera, dada su estructura matemtica. No se

necesitan restricciones adicionales para obtener este tipo de solucin.

o Problemas de redes pueden ser resueltos por pequeos algoritmos, no importando el tamao del problema, dada su estructura matemtica.

Vista general de algunas aplicaciones prcticas de la optimizacin de redes 1. Diseo de redes de telecomunicacin (redes de fibra ptica, de computadores, telefnicas, de televisin por

cable, etc.)

2. Diseo de redes de transporte para minimizar el costo total de proporcionar las ligaduras (vas ferroviarias, carreteras, etc.)

3. Diseo de una red de lneas de transmisin de energa elctrica de alto voltaje.

Figura No 2: Ejemplo de un rbol




4. Diseo de una red de cableado en equipo elctrico (como sistemas de computo) para minimizar la longitud total del cable.

5. Diseo de una red de tuberas para conectar varias localidades. 6. Diseo de una red de tuberas de gas natural mar adentro que conecta fuentes del golfo de Mxico con un

punto de entrega en tierra con el objetivo de minimizar el costo de construccin.

7. Determinacin de la ruta ms corta que une dos ciudades en una red de caminos existentes. 8. Determinar la capacidad anual de mxima en toneladas de una red de conductos de pasta aguada de carbn

que enlaza las minas carboneras de Wyoming con las plantas generadoras de electricidad Houston. (Los

conductos de pasta aguada de carbn transportan ste bombeando agua a travs de tubos adecuadamente

diseados que operan entre las minas de carbn y el destino deseado.) 9. Determinacin del programa de costo mnimo de los campos petrolferos a refineras y finalmente a los

campos de distribucin. Se pueden enviar petrleo crudo y productos derivados de la gasolina en buques

tanque, oleoductos y/o camiones. Adems de la disponibilidad de la oferta mxima en los campos petrolferos

y los requisitos de demanda mnima en los centros de distribucin, deben tomarse en cuenta restricciones sobre la capacidad de las refineras y los modos de transporte.

MODELOS DE REDES Los problemas de optimizacin de redes se pueden representar en trminos generales a travs de uno de estos cuatro

modelos:

o Problemas de transporte o Problemas de asignacin o Modelo de la ruta ms corta. (Algoritmo de Dijkstra, Algoritmo de Floyd-Warshall, Bellman-Ford, Algoritmo

de Johnson)

o Modelo de minimizacin de redes (Problema del rbol de mnima expansin: Algoritmo de Kruskal, Algoritmo de Prim).

o Modelo del flujo mximo(Algoritmo de Ford-Fulkerson, Algoritmo de Edmonds-Karp) o Modelo del flujo del costo mnimo. o Camino critico en la planificacin de Proyecto de Redes

MODELO DE LA RUTA MS CORTA En la Teora de grafos, el problema de los caminos ms cortos es el problema que consiste en encontrar un camino

entre dos vrtices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mnima. Un ejemplo es encontrar el camino ms rpido para ir de una ciudad a otra en un mapa. En este caso, los vrtices

representan las ciudades, y las aristas las carreteras que las unen, cuya ponderacin viene dada por el tiempo que se

emplea en atravesarlas.

Formalmente, dado un grafo ponderado (que es un conjunto V de vrtices, un conjunto E de aristas y una funcin de

variable real ponderada f: E R) y un elemento v V encuentra un camino P de v a v' V, tal que:

Es el mnimo entre todos los caminos que conectan v y v'.

El problema es tambin conocido como el problema de los caminos ms cortos entre dos nodos, para diferenciarlo

de la siguiente generalizacin:

El problema de los caminos ms cortos desde un origen en el cual tenemos que encontrar los caminos ms cortos de un vrtice origen v a todos los dems vrtices del grafo.

El problema de los caminos ms cortos con un destino en el cual tenemos que encontrar los caminos ms cortos desde todos los vrtices del grafo a un nico vrtice destino, esto puede ser reducido al

problema anterior invirtiendo el orden.

El problema de los caminos ms cortos entre todos los pares de vrtices , el cual tenemos que encontrar los caminos ms cortos entre cada par de vrtices (v, v') en el grafo.

Algoritmos Los algoritmos ms importantes para resolver este problema son:

Algoritmo de Dijkstra, resuelve el problema de los caminos ms cortos entre dos vrtices, desde un origen y un nico destino.




Algoritmo de Floyd - Warshall, resuelve el problema de los caminos ms cortos entre todos los vrtices.

Algoritmo de Bellman - Ford, resuelve el problema de los caminos ms cortos desde un origen si la ponderacin de las aristas es negativa.

Algoritmo de Bsqueda A, resuelve el problema de los caminos ms cortos entre un par de vrtices usando la heurstica para intentar agilizar la bsqueda.

Algoritmo de Johnson, resuelve el problema de los caminos ms cortos entre todos los vrtices y puede ser ms rpido que el de Floyd - Warshall en grafos de baja densidad.

Teora perturbacional, encuentra en el peor de los casos el camino ms corto a nivel local.

Problemas Relacionados El problema de viajante de comercio, es el problema que trata de encontrar el camino ms corto que pasa slo una

vez por cada vrtice y regresa al comienzo. A diferencia de los caminos ms cortos, el cual puede ser resuelto en un

tiempo polinomial en grafos sin ciclos negativos.

EL PROBLEMA DEL AGENTE VIAJERO El popular problema del agente viajero, como los dems de redes, involucra un conjunto de nodos y arcos que

conectan todos los nodos. El objetivo es encontrar la forma de realizar una gira completa que conecte todos los nodos visitando slo una vez cada nodo y minimizar o maximizar la distancia de la gira total (itinerario optimo

desde un cierto punto de vista econmico, tiempo mnimo, poltica de relaciones pblicas, comodidad, etc.) y volver

al punto de partida. Este modelo tiene mltiples aplicaciones en ingeniera.

Este es un problema tpico de fenmenos de organizacin y tiene consecuencias e implicaciones econmicas y tcnicas importantes.

Formulacin del El Problema del Agente Viajero (PAV) o Traveling Salesman Problem (TSP)

El TSP presenta una gran facilidad para formularse, pero a medida que crece el nmero de ciudades, el tiempo para obtener una solucin ptima crece ms. Para formular el TSP como un problema de programacin entera se usa la

variable Xij que toma el valor de 1 si el arco (i, j) es usado, y el valor de 0 en cualquier otro caso.

La formulacin de este problema es la siguiente:

{

Cij = el costo asociado a la visita de la ciudad j despus de visitar la ciudad i.

Min z =

Sujeto a las siguientes restricciones, Para garantizar que se llega a cada ciudad exactamente una vez:

(j= 1,2,., n+1) Para garantizar que se sale de cada ciudad exactamente una vez:

(i= 1,.., n)

Por su gran facilidad para ser formulado y por su gran adaptabilidad a mltiples situaciones prcticas el TSP ha sido uno de los problemas de optimizacin que mayor inters ha despertado a los investigadores en las reas de

matemticas discretas, computacin e investigacin de operaciones.

La figura del ejemplo No 1 representa ciudades, en los nodos, y los valores en los arcos son las distancias que las separan.

Definicin del problema

- Existen m nodos




- Un costo unitario C ij es asociado al arco (i,j). El objetivo es encontrar el ciclo que minimice el costo total al visitar todos los nodos exactamente una vez

Complejidad

Escribir el modelo matemtico y resolverlo resulta muchas veces incmodo, ya que un problema de 20 ciudades

requiere de 500,000 restricciones.

Ejemplo Desarrollado No 1: Problema del Controlador

Se debe realizar una visita a cuatro oficinas locales de la empresa, partiendo de la oficina principal y volviendo a la

misma, la cual est ubicada en Lima.

Hacia la oficina

Oficina principal (H) Oficina1 Oficina2 Oficina3 Oficina4

De

Oficina principal (H) 30 45 65 80

Oficina1 30 25 50 50

Oficina2 45 25 40 40

Oficina3 65 50 40 40

Oficina4 80 50 40 35 35

Tabla No 1: Datos del problema

Solucin

- Identificacin de los posibles ciclos.

- Existen (m-1)1 ciclos posibles - Solo problemas pequeos pueden ser resueltos.

- Se utiliza una combinacin de problemas de asignacin con la tcnica Branch and Bound.

- Problemas con menos de 20 nodos pueden ser resueltos en forma eficiente por este mtodo.

EL PROBLEMA DEL CONTROLADOR - Identificacin de los posibles ciclos

Ciclo Tiempo Total

1. H-O1-O2-O3-O4-H 210

2. H-O1-O2-O4-O3-H 195 3. H-O1-O3-O2-O3-H 240

4. H-O1-O3-O4-O2-H 200

5. H-O1-O4-O2-O3-H 225

6. H-O1-O4-O3-O2-H 200 7. H-O2-O3-O1-O4-H 265

8. H-O2-O1-O3-O4-H 235

9. H-O2-O4-O1-O3-H 250

10. H-O2-O1-O4-O3-H 220 11. H-O3-O1-O2-O4-H 260

12. H-O3-O1-O2-O4-H 260

Figura No 3: Tiempo en minutos para

trasladarse de la oficina principal a

cualquier oficina y entre oficinas




SOLUCION CON WINQSB Hacer clic sobre el comando NetWork Modeling

La opcin Nuevo Problema (New Problem) generar la siguiente ventana:

Existen 7 modelos fundamentales para el tratamiento de los problemas que involucran redes con el fin de optimizar

el uso de algn recurso, generalmente tratndose de la minimizacin de costos, tiempo o la maximizacin del flujo a

travs de una red. Estos modelos son:

Flujo en redes o modelo de trasbordo (Network Flow) Problema de transporte (Transportation Problem) Problema de asignacin (Assignment Problem) Problema de la ruta ms corta (Shortest Path Problem) Problema de flujo mximo (Maximal Flow Problem) rbol de mnima expansin (Minimal Spanning Tree) Problema del agente viajero (Traveling Salesman Problem)

Para modificar los nombres de los nodos pulsamos sobre Node Name en el men Editar (Edit). Modifiquemos

dichos nombre como se muestra a continuacin:

Figura No 4: Primera ventana del

WINQSB en blanco

Figura No 5: Primera ventana del

WINQSB con datos

Figura No 6: Ventana en forma de

matriz para los datos de entrada que

son las distancias




Datos de entrada para el problema del controlador

En esta ventana marque la opcin Branch And Bound Method

Figura No 8: Solucin de WINQSB, una combinacin de problema de asignacin y la tcnica Branch and Bound

Ejemplo Desarrollado No 2: Un viajero tiene que visitar cada una de las cuatro ciudades y lo quiere hacer de tal

manera que visite una sola vez partiendo de la ciudad 1 y regresando al final del recorrido, viajando el menor tiempo

posible, la siguiente tabla muestra los tiempos entre ciudades (horas):

De 1 2 3 4

1 0 1 5 4

2 7 0 3 1

3 5 3 0 2

4 4 1 2 0

De 1 2 3 4

1 X1 X2 X3

2 X4 X5 X6

3 X7 X8 X9

4 X10 X11 X12

Cada cuidad debe visitarse una sola vez.

Planteamiento

Figura No 7: Ventana de opciones




1 S pasa por la ciudad i a la j

Xij = { 0 No pasa por la ciudad i a la j

Min Z = X1 + 5X2 + 4X3 + 7X4 + 3X5 + X6 + 5X7 + 3X8 + 2X9 + 4X10 + X11 + 2X12

Sujeto a:

X1 + X2 + X3 = 1 X4 + X7 + X10 = 1

X4 + X5 + X6 = 1 X1 + X8 + X11 = 1

X7 + X8 + X9 = 1 X2 + X5 + X12 = 1 X10 + X11 + X12 = 1 X3 + X6 + X9 = 1

Limitacin de salida Limitacin de llegada

Xij >= 0 Z Solucin DS POM

Ejecute DS POM, seleccione la opcin programacin lineal

Seleccione 8 restricciones y 12 variables y de clic en OK

Digite los datos en la matriz anterior y ejecute Solve




Interpretacin de resultados

Par la interpretacin de resultados regresamos al nombre original de las variables y obtener lo siguiente:

Por lo tanto se dice que el recorrido ser de siguiente manera:

Pasa de la ciudad 1 a la 2

Pasa de la ciudad 2 a la 4

Pasa de la ciudad 4 a la 3 Pasa de la ciudad 3 a la 1 terminando donde se inici el recorrido.

El tiempo mnimo usado asiendo este recorrido ser de 9 horas.

Redes de flujo Los problemas relacionados con la comunicacin de diferentes lugares, en donde existe la necesidad de enviar y /o

recibir unidades (bienes, servicios, gente, informacin), se pueden analizar como modelos de red con flujo de tales unidades.

La estructura matemtica del modelo obtenido a partir de una red de flujo, es muy especial y ha facilitado el

desarrollo de algoritmos de solucin, especficos de esos problemas. La aplicacin de dichos algoritmos de redes de

flujo, es la oportunidad para comprobar su gran eficiencia en cuanto a labor de clculo, comparados con el simplex que as se reconoce, eficiente y, adems verstil. Ahora se presenta la aplicacin de redes de flujo y algoritmos a

problemas importantes en el transporte de unidades.

Teora de grafos En matemticas y en ciencias de la computacin, la teora de grafos (tambin llamada teora de las grficas)

estudia las propiedades de los grafos (tambin llamadas grficas). Un grafo es un conjunto, no vaco, de objetos

llamados vrtices (o nodos) y una seleccin de pares de vrtices, llamados aristas (edges en ingls) que pueden ser orientados o no. Tpicamente, un grafo se representa mediante una serie de puntos (los vrtices) conectados por

lneas (las aristas).

Solucin:

Variable Horas X1 = 1 1

X6 = 1 1

X7 = 1 5

X12 = 1 2

Total 9




Diagrama de un grafo con 6 vrtices y 7 aristas.

Vrtice Los vrtices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de

las matemticas, a la Teora de Grafos no le interesa saber qu son los vrtices.

Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definicin de grafo

pueden verse como grafos y as aplicar la Teora de Grafos en ellos.

Grafo Un grafo es una pareja de conjuntos G = (V, A), donde V es el conjunto de vrtices, y A es el conjunto de aristas, este

ltimo es un conjunto de pares de la forma (u, v) tal que, tal que. Para simplificar, notaremos la arista (a, b) como ab.

En teora de grafos, slo queda lo esencial del dibujo: la forma de las aristas no son relevantes, slo importa a qu

vrtices estn unidas. La posicin de los vrtices tampoco importa, y se puede variar para obtener un dibujo ms

claro. Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una

red elctrica o la red de drenaje de una ciudad.

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las

calles de una ciudad con sus direcciones nicas. El conjunto de aristas ser ahora un subconjunto de todos los

posibles pares ordenados de vrtices, con (a, b) (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente: Las aristas no orientadas se consideran bidireccionales para efectos prcticos (equivale a decir que existen dos

aristas orientadas entre los nodos, cada una en un sentido).

En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idnticos: es un lazo (o bucle), y aparece

tambin una arista bidireccional, y corresponde a dos aristas orientadas. Aqu V = {a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.

Se considera la caracterstica de "grado" (positivo o negativo) de un vrtice v (y se indica como (v)), como la

cantidad de aristas que llegan o salen de l; para el caso de grafos no orientados, el grado de un vrtice es

simplemente la cantidad de aristas incidentes a este vrtice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de d es 0.

Segn la terminologa seguida en algunos problemas clsicos de Investigacin Operativa (p.ej.: el Problema del

flujo mximo), a un vrtice del que slo salen aristas se le denomina fuente (en el ejemplo anterior, el vrtice d);

tiene grado negativo 0. Por el contrario, a aquellos en los que slo entran aristas se les denomina pozo o sumidero (en el caso anterior, el vrtice e); tiene grado positivo 0.




Caracterizacin de grafos

Grafos simples Un grafo es simple si a lo sumo slo 1 arista une dos vrtices cualesquiera. Esto es equivalente a decir que una arista

cualquiera es la nica que une dos vrtices especficos.

Un grafo que no es simple se denomina Multigrfica o Grafo mltiple.

Grafos conexos Un grafo es conexo si cada par de vrtices est conectado por un camino; es decir, si para cualquier par de vrtices

(a, b), existe al menos un camino posible desde a hacia b.

Un grafo es fuertemente conexo si cada par de vrtices est conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vrtice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Bsqueda en anchura (BFS) o Bsqueda en

profundidad (DFS). En trminos matemticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer en base a l una

relacin de equivalencia para sus vrtices, la cual lleva a una particin de stos en "componentes (fuertemente)

conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados.

Esta propiedad es importante para muchas demostraciones en teora de grafos.

Grafos completos Un grafo es completo si existen aristas uniendo todos los pares posibles de vrtices. Es decir, todo par de vrtices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente , siendo el grafo completo de n vrtices.

Un Kn, es decir, grafo completo de n vrtices tiene exactamente aristas. La representacin grfica de los Kn como los vrtices de un polgono regular da cuenta de su peculiar estructura.

Grafos ponderados o etiquetados En muchos casos, es preciso atribuir a cada arista un nmero especfico, llamado valuacin, ponderacin o coste

segn el contexto, y se obtiene as un grafo valuado.

Formalmente, es un grafo con una funcin v: A R+. Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre s por carreteras; su inters previsible ser minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente

tendr como vrtices las ciudades, como aristas las carreteras y la valuacin ser la distancia entre ellas.

Y, de momento, no se conocen mtodos generales para hallar un ciclo de valuacin mnima, pero s para los caminos

desde a hasta b, sin ms condicin.

ALGORITMO DE DIJKSTRA El algoritmo de Dijkstra, tambin llamado algoritmo de caminos mnimos, es un algoritmo para la determinacin del camino ms corto dado un vrtice origen al resto de vrtices en un grafo dirigido y con pesos en cada arista. Su

nombre se refiere a Edsger Dijkstra, quien lo describi por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos ms cortos que parten del vrtice

origen y que llevan a todos los dems vrtices; cuando se obtiene el camino ms corto desde el vrtice origen, al resto de vrtices que componen el grafo, el algoritmo se detiene. El algoritmo es una especializacin de la bsqueda

de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la bsqueda nodos que en prximas iteraciones bajaran el costo

general del camino al pasar por una arista con costo negativo).

Algoritmo Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamao N

guardar al final del algoritmo las distancias desde x al resto de los nodos.




1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sera 0.

2. Sea a = x (tomamos a como nodo actual). 3. Recorremos todos los nodos adyacentes de a menos los nodos marcados, llamaremos a estos v i. 4. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a sumada a la

distancia desde a hasta vi; esta se substituye con la segunda nombrada, esto es: si (Di > Da + d(a,vi)) entonces Di = Da + d(a, vi)

5. Marcamos como completo el nodo a. 6. Tomamos como prximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en

una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados. - Una vez terminado al algoritmo, D estar completamente lleno.

ALGORITMO DE DIJKSTRA PARA RUTA MNIMA EN RED ORIENTADA Condiciones: Se aplica en una red estrictamente orientada, entendiendo que cada una de sus ramas es

unidireccional y ningn conjunto, de ramas incluidas, forma ciclo. Tambin se utiliza una etiqueta que puede ser de carcter temporal, o bien permanente, para cada uno de los nodos graficados. Algo para anotar es que, una red,

con todas sus ramas unidireccionales, ya tiene definido el nodo origen. Los pasos a seguir del algoritmo de Dijkstra

son:

1. El nodo origen siempre se etiqueta permanente as: (-, 0) P 2. Enseguida debe etiquetarse permanente aquel nodo que tenga como nico inverso al origen: ( # del

origen, costo cero + costo desde el origen ) P 3. A partir de los nodos con permanencia deben etiquetarse en forma temporal, los que sean nodos vecinos

directos conectados a los mismos. Luego se revisan las temporales, con el propsito de eliminar la etiqueta duplicada y mantener una sola ( la que tenga el menor costo), para cada nodo directo.

4. Convertir a permanente, aquel nodo que tenga todos sus nodos vecinos inversos con etiqueta permanente. En caso de empate en menor costo, se deben considerar todas las etiquetas que cumplan tal condicin.

5. Se repite el procedimiento desde el paso 3, hasta que todos los nodos tengan etiqueta permanente. 6. Las rutas mnimas para cada uno de los nodos, se definen con la identificacin del nodo inmediato anterior

de la ruta en el lado izquierdo de la etiqueta permanente, retrocediendo hacia el origen conforme a lo

indicado. El proceso se completa sealando las n-1 rutas calculadas, tanto en la red como en una tabla.

Aplicaciones del Algoritmo de Dijkstra

Problema Desarrollado No 3: De ruta mnima

Definicin: Dada una red de n nodos ( i ) conectadas por ramas ( i, j ), asociadas a un costo Cij; el objetivo es

determinar n-1 rutas mnimas, desde un nodo ( i ) fijado como origen, hasta los restantes n-1 nodos.

La red de la figura anterior muestra las rutas con sus longitudes, en Km, entre la ciudad 1(nodo 1) y otras ciudades

(nodos 2 a 5): Determinar las rutas ms cortas entre la ciudad 1 y cada una de las cuatro ciudades restantes.

Iteracin 0: Asignar la etiqueta permanente [0, -] al nodo 1

Figura No 9: Datos del problema No 3




Iteracin 1: Se puede llegar a los nodos 2, 3 y 5 desde el nodo 1 (ltimo que se etiquet en forma permanente). As,

la lista de los nodos etiquetados (temporales y permanentes) es la siguiente:

Nodo Etiqueta Estado

1 [0, -] Permanente 2 [2, 1] Temporal

3 [1, 1] Temporal

5 [3, 1] Temporal

Para las tres etiquetas temporales [2,1], [1,1] y [3,1], el nodo 3 produce la menor distancia (u3 = 1). Entonces, se

cambia el estado del nodo 3 a permanente.

Iteracin 2: Del nodo 3 se puede ir a los nodos 5 y 2, y la lista de nodos etiquetados es:


1 [0, -] Permanente

2 [2, 1], [2,3] Temporal

3 [1, 1] Permanente 5 [3, 1], [2, 3] Temporal

El estado de la etiqueta temporal [2,3] en el nodo 2 se cambia a permanente (u2 = 2). Observe que tambin empata el

nodo 5 con una etiqueta [2,3].

Iteracin 3: Del nodo 2 se puede ir al nodo 4. Entonces la lista actualizada de los nodos etiquetados es:


1 [0, -] Permanente

2 [2,3] Permanente

3 [1, 1] Permanente

Figura No 10: Iteracin 0






5 [2, 3] Temporal

4 [6, 2] Temporal

La etiqueta temporal del nodo 5, [2,3], en la iteracin 3 se cambia a permanente, para indicar que se ha encontrado

una ruta ms corta que pasa por el nodo 5.


1 [0, -] Permanente

2 [2,3] Permanente

3 [1, 1] Permanente

5 [2, 3] Permanente

4 [6, 2] Temporal

Iteracin 4: Del nodo 5 no se puede ir a ningn nodo, pero el nodo 4 tiene una etiqueta temporal, por tanto se

convierte en permanente.


1 [0, -] Permanente

2 [2,3] Permanente

3 [1, 1] Permanente

5 [2, 3] Permanente

4 [6, 2] Permanente

Aplicacin del Algoritmo de Dijkstra

Problema Desarrollado No 4: La red en la figura proporciona las rutas permisibles y sus longitudes en km entre

la ciudad 1 (nodo 1) y otras cuatro ciudades (nodos 2 al 5). Se desea determinar las rutas ms cortas de la ciudad 1 a

cada una de las cuatro ciudades restantes.

Iteracin 0: Asignar la clasificacin permanente [0, -] al nodo 1






Iteracin 0: Asignar la clasificacin permanente [0, -] al nodo 1 Iteracin 1: Es posible llegar a los nodos 2 y 3 desde el nodo 1 (el ltimo clasificado permanentemente)

Iteracin 2: Se puede llegar a los nodos 4 y 5 desde el nodo 3 (el ltimo clasificado permanente)

Iteracin 3: Se puede llegar a los nodos 2 y 5 desde el nodo 4 (el ltimo clasificado permanente)

Iteracin 4: Solo se puede llegar al nodo 3 desde el nodo 2. Sin embargo, debido a que el nodo 3 est clasificado permanentemente, no se puede volver a clasificar. La nueva lista de clasificaciones permanece igual que en la

iteracin 3, excepto que la clasificacin en el nodo 2 es permanente. Esto deja al nodo 5 como la nica clasificacin

temporal. Debido a que el nodo 5 no lleva a otros nodos, su status se convierte a permanente y el proceso termina.

La ruta ms corta entre el nodo 1 y el nodo 2 se obtiene as: 2 4 3 1 (2) [55,4] (4) [40,3] (3) [30, 1] (1)

Ejercicios propuestos Problema Propuesto No 1: En la siguiente red orientada de 7 nodos (Figura No 16), determinar las rutas

mnimas desde el origen O hacia los restantes nodos, utilizando el algoritmo de Dijkstra. Tambin utilice el

software Grafos

Figura No 15: Datos del problema No 4




Problema Propuesto N

o 2: Ruta mnima, aplicar algoritmo de Dijkstra.

La siguiente red (Figura No 17) es no orientada, con un total de ocho nodos de los cuales se fija como origen al nodo

8. Determine las rutas mnimas desde el origen hasta los 8 - 1 = 7 nodos restantes, utilizando el algoritmo de Dijkstra.

Problema Propuesto No 3: Como ejercicio para el estudiante, considere la red ejemplo anterior con los mismos

costos Cij asociados a las ramas. Pero en este caso se considera al nodo No 6, como origen, lo cual produce un

problema diferente, que podr comprobar con sus resultados y los anotados en la red correspondiente.

Problema Propuesto No 4: Aplicar el algoritmo de Dijkstra a la siguiente Red:

Problema Propuesto No 5: Determine la ruta mnima, aplicando el algoritmo Dijkstra, desde el nodo 1 fijado

como origen y el 8 como destino en la siguiente red:

Figura No 16: Red del problema

propuesto No 1


propuesto No 2


propuesto No 4




Respuesta problema No 5: Rutas mnimas, red no orientada, algoritmo de Dijkstra.

ALGORITMO DE FLOYD-WARSALL: CAMINOS MINIMOS ENTRE POSIBLES PARES DE

NODOS DE UNA RED En informtica, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de anlisis sobre grafos para encontrar el camino mnimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre

todos los pares de vrtices en una nica ejecucin. El algoritmo de Floyd-Warshall es un ejemplo de programacin

dinmica.

Algoritmo El algoritmo de Floyd-Warshall compara todos los posibles caminos a travs del grafo entre cada par de vrtices. El

algoritmo es capaz de hacer esto con slo V3 comparaciones (esto es notable considerando que puede haber hasta V2

aristas en el grafo, y que cada combinacin de aristas se prueba). Lo hace mejorando paulatinamente una estimacin del camino ms corto entre dos vrtices, hasta que se sabe que la estimacin es ptima.

Sea un grafo G con conjunto de vrtices V, numerados de 1 a N. Sea adems una funcin camino Mnimo

(i, j, k) que devuelve el camino mnimo de i a j usando nicamente los vrtices de 1 a k como puntos intermedios en el camino. Ahora, dada esta funcin, nuestro objetivo es encontrar el camino mnimo desde cada i a cada j usando

nicamente los vrtices de 1 hasta k + 1.

Hay dos candidatos para este camino: un camino mnimo, que utiliza nicamente los vrtices del conjunto (1...k); o

bien existe un camino que va desde i hasta k + 1, despus de k + 1 hasta j que es mejor. Sabemos que el camino ptimo de i a j que nicamente utiliza los vrtices de 1 hasta k est definido por camino Mnimo(i, j, k), y est claro

que si hubiera un camino mejor de i a k + 1 a j, la longitud de este camino sera la concatenacin del camino mnimo

de i a k + 1 (utilizando vrtices de (1...k)) y el camino mnimo de k + 1 a j (que tambin utiliza los vrtices en

(1...k)).

Por lo tanto, podemos definir camino Mnimo (i, j, k) de forma recursiva:

Camino Mnimo (i, j, k)=min (camino Mnimo (i,j,k-1), camino Mnimo(i, k, k-1)+camino Mnimo(k,j,k-1));

Camino Mnimo (i, j, 0) = peso Arista (i, j)

Esta frmula es la base del algoritmo Floyd-Warshall. Funciona ejecutando primero camino Mnimo (i,j,1) para todos los pares (i, j), usndolos para despus hallar camino Mnimo(i,j,2) para todos los pares (i, j)... Este proceso

contina hasta que k = n, y habremos encontrado el camino ms corto para todos los pares de vrtices (i, j) usando

algn vrtice intermedio.


propuesto No 5




Comportamiento con ciclos negativos Para que haya coherencia numrica, Floyd-Warshall supone que no hay ciclos negativos (de hecho, entre cualquier pareja de vrtices que forme parte de un ciclo negativo, el camino mnimo no est bien definido porque el camino

puede ser infinitamente pequeo). No obstante, si hay ciclos negativos, Floyd-Warshall puede ser usado para

detectarlos. Si ejecutamos el algoritmo una vez ms, algunos caminos pueden decrementarse pero no garantiza que,

entre todos los vrtices, caminos entre los cuales puedan ser infinitamente pequeos, el camino se reduzca. Si los nmeros de la diagonal de la matriz de caminos son negativos, es condicin necesaria y suficiente para que este

vrtice pertenezca a un ciclo negativo.

Este algoritmo proporciona las distancias y caminos mnimos entre todos los posibles pares de nodos de la red. El algoritmo de Floyd es ms general que el de Dijkstra, porque determina la ruta ms corta entre dos nodos

cualesquiera de la red. El algoritmo representa una red de n nodos como matriz cuadrada con n renglones y n

columnas. El elemento (i, j) de la matriz expresa la distancia o valor dij del nodo i al nodo j, que es finita si i est conectado directamente con j, e infinita en caso contrario.

El concepto del algoritmo de Floyd es directo. Dados tres nodos i, j y k en la figura anterior, con las distancias entre

si indicadas en los tres arcos, es ms corto ir a k desde i pasando por j si

dij + djk < dik En este caso, lo ptimo es reemplazar la ruta directa de i k por la ruta indirecta i j k. Este intercambio de operacin triple se aplica en forma sistemtica a la red, con los siguientes pasos:

Paso 0: Definir las matrices inciales de distancias D0 y de secuencias de nodos S0 como se describe abajo. Los elementos diagonales se marcan con (--) para indicar que estn bloqueadas. Igualar k = i.

1 2 j n

1 d12 d1j d1n

2 d21 d2j d2n

Do =

i di1 di2 din

n dn1 dn2 dnj

1 2 j n

1 2 j n

2 1 j n

So =

i 1 2 j n

n 1 2 j




Paso general k: Definir el rengln k y la columna k como rengln pivote y columna pivote.

Aplicar la operacin triple a cada elemento dij en Dk-1 para toda i y j. Si se satisface la condicin

dik + dkj < dij (i k, j k e i j)

Hacer los siguientes cambios

a) Crear Dk reemplazando dij en Dk-1 por dik + dkj b) Crear Sk reemplazando sij en Sk-1 por k. Igualar k = k + 1 y repetir el paso k.

Figura No 18: Implementacin de la operacin triple en forma matricial

Se puede explicar el paso k del algoritmo representando a Dk-1 como se ve en la figura No . Aqu, el rengln k y la

columna k definen el rengln y la columna pivote actual. El rengln i representa cualesquiera de los renglones 1, 2, , y k 1, y el rengln p representa cualesquiera de los renglones k+1, k+2, , y n. De igual modo, la columna j representa cualquiera de las columnas 1, 2,, y k-1, y la columna q representa cualquiera de las columnas k+1, k+2, y n. Con la operacin triple, si la suma de los elementos del rengln pivote y la columna pivote (representado por cuadrados) es menor que el elemento de interseccin asociado (representado por un crculo), entonces es ptimo reemplazar la distancia de interseccin por la suma de las distancias pivote.

Despus de n pasos se puede determinar la ruta ms corta entre los nodos i y j con las matrices Dn y Sn con las

siguientes reglas:

1. En Dn, dij representa la distancia ms corta entre los nodos i y j. 2. En Sn, se determina el nodo intermedio k = sij que forme la ruta i k j. Si Sik = k y skj = j, detenerse;

todos los nodos intermedios de la ruta se han determinado. En caso contrario, repetir el procedimiento entre

los nodos i y k y entre los nodos k y j.

Otra forma de aplicar este algoritmo

Al valor de los arcos lo denominaremos Cij, que indicar el valor del arco que va del nodo i al nodo j. Si no existe el

arco que va de la i a j: Cij = Se forma una matriz, C, cuyos elementos son los Cij y otra matriz D, cuyos elementos son los nodos del grafo y que

est construida como sigue: Si se tienen n nodos, la dimensin de la matriz D ser de: nxn. Para inicializar la matriz cada fila se rellena con el

identificador del nodo correspondiente.

Si la red tiene los nodos 1, 2, 3, 4 y 5:




En estas condiciones la matriz C proporcionara las distancias y la matriz D los caminos.

El algoritmo sigue los siguientes pasos: Paso 1: Se forman las matrices C y D.

Paso 2: Se selecciona la fila 1 y la columna 1 de la matriz C. Para todo i, j 1 Cij = min [ ( )]

Si (Ci1 + C1j) < Cij entonces dij = d1j Paso 3: Se reitera el paso 2 seleccionando la fila k y la columna k.

Paso 4: Se termina el algoritmo cuando k coincide con el nmero de nodos del grafo.

Los elementos de la matriz C son las distancias entre los nodos. Con los elementos de la matriz D se obtiene el camino existente entre el nodo i y el nodo j de la siguiente forma:

En el elemento dij de la matriz D el nodo 1 es el predecesor del nodo j. Si 1 = i ya se ha obtenido el camino; si no, miramos el elemento di1 que ser el predecesor de 1.

Terminaremos cuando de encuentre en la matriz el nodo i.

Problema Desarrollado N

o 5:

Para la red en la figura, encuentre las rutas ms cortas entre cada dos nodos. Las distancias se dan en los arcos. El

arco (3,5) es direccional, de manera que no est permitido ningn trfico del nodo 5 al nodo 3. Todos los dems arcos permiten el trfico en ambas direcciones.


desarrollado No 5




Las matrices D0 y S0 son la representacin inicial de la red. D0 es simtrica, excepto que d53 = porque no se permite trafico del nodo 5 al nodo 3.

Iteracin 1: Se iguala k = 1. El rengln y la columna pivotes se ven en la matriz D0 con sombra ligera: son el primer rengln y la primera columna: Las celdas ms oscuras, d23 y d32 son las nicas que pueden mejorar con la operacin

triple. As, D1 y S1 se obtienen partiendo de D0 y S0 como sigue:

1. Sustituir d23 con d21 + d13 = 3+ 10 = 13, e igualar s23 = 1

2. Sustituir d32 con d31 + d12 = 10 + 3 = 13, e igualar s32 = 1 Estos cambios se muestran en negritas, en las matrices D1 y S1




Iteracin 2: Se iguala k = 2, como indican el rengln y la columna con sombra ligera en D1. Se aplica la operacin triple a las celdas ms oscuras de D1 y S1. Los cambios que resultan se indican con negritas en D2 y en S2.




Iteracin 3: Se iguala k = 3, como indican el rengln y la columna sombreadas en D2. Las nuevas matrices son D3 y S3.




Iteracin 4: Se iguala k = 4 como se indica con el rengln y la columna con sombra ligera en D3. Las nuevas matrices son D4 y S4.




Iteracin 5: Se iguala k = 5, como se ve en el rengln y la columna sombreada de D4. No hay ms mejoras posibles en esta iteracin. Por consiguiente, D5 y S5 son iguales que D4 y S4.




Las matrices finales D5 y S5 contienen toda la informacin necesaria para determinar la ruta ms corta entre dos

nodos cualesquiera de la red. Por ejemplo para determinar la ruta ms corta del nodo 1 al nodo 5, primero se ve la

distancia asociada d15 = 12. Para determinar la ruta asociada, recurdese que un segmento (i, j) representa un enlace

directo slo si sij = j. En caso contrario, i y j estn enlazados mediante al menos un nodo intermedio. Como s15 = 4, la ruta inicial es 1 4 5. Ahora bien, como s14 = 2 4, el segmento (1,4) no es un enlace directo y 1 4 se debe reemplazar por 1 2 4, y la ruta 1 4 5 se transforma ahora en 1 2 4 5. A continuacin, como s12 = 2, s24 = 4 y s45 = 5, la ruta 1 2 4 5 no necesita ms disecciones y el proceso termina.

Solucin con DS POM

Ejecute DS POM

Seleccione la opcin Networks

Seleccione la opcin New




Seleccione la opcin Shortest Route

Digite el ttulo y seleccione el nmero de arcos, para este caso hay 11 (tenga en cuenta que el arco sin flechas quiere

decir que es de doble sentido, excepto el que va de 3 a 5, es de 1 solo sentido)

Haga clic en OK, se presentara el siguiente cuadro donde debe digitar el inicio y fin del arco, as como su distancia respectiva.

A continuacin haga clic en Solve




Este cuadro es igual que el cuadro de distancias calculado anteriormente

Ejemplo Desarrollado No 6:

Ejercicios propuestos

Problema Propuesto No

1: Aplique el algoritmo de Floyd a la red de la figura No 20. Los arcos (7,6) y (6,4) son unidireccionales y todas las distancias son en Km. Determine la ruta ms corta entre los siguientes pares de nodos:

a) Del nodo 1 al nodo 7. b) Del nodo 7 al nodo 1. c) Del nodo 6 al nodo 7.

Problema Propuesto No 2: Aplique el algoritmo de Floyd, para encontrar la distancia ms corta del origen al

destino de la siguiente red.

Problema Propuesto No 3: Desarrolle la siguiente red, aplicando el algoritmo de Floyd

2 4

3

2

6 5

1 2

2 2

2

2 2

2

2


propuesto No 1


propuesto No 2


propuesto No 3




Problema Propuesto No 4. Una empresa qumica fabrica 5 compuestos diferentes. Debido a economas de escala,

cada compuesto es producido una sola vez al da. Los costes que se generan no solo dependen de las materias primas usadas para generar cada compuesto, sino que tambin de la secuencia elegida para generarlos.

Debido a que cada compuesto deja algunas impurezas que afectan a la calidad de los siguientes productos a generar,

y que esta prdida de calidad tiene algunos costes asociados, se desea encontrar el plan diario de produccin de los

compuestos con un coste mnimo.

Los costes en euros se indican en la siguiente matriz C, el valor cij es el coste cuando se pasa de producir el compuesto i a producir el compuesto j:

Problema Propuesto No 5. Mediante el algoritmo de Floyd, encuentre el camino mnimo del nodo H al resto de

nodos.

ALGORITMO DE BELLMAN-FORD El algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino ms corto en un Grafo dirigido

ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el

Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue

desarrollado por Richard Bellman, Samuel End y Lester Ford.

Segn Robert Sedgewick, Los pesos negativos no son simplemente una curiosidad matemtica; [] surgen de una forma natural en la reduccin a problemas de caminos ms cortos, y son un ejemplo de una reduccin del problema del camino hamiltoniano que es NP-completo hasta el problema de caminos ms cortos con pesos generales. Si un

grafo contiene un ciclo de coste total negativo entonces este grafo no tiene solucin. El algoritmo es capaz de

detectar este caso. Si el grafo contiene un ciclo de coste negativo, el algoritmo lo detectara, pero no encontrar el camino ms corto que

no repite ningn vrtice. La complejidad de este problema es al menos la del problema del camino ms largo de

complejidad NP-Completo.




Algoritmo

El Algoritmo de Bellman-Ford es, en su estructura bsica, muy parecido al algoritmo de Dijkstra, pero en vez de seleccionar vorazmente el nodo de peso mnimo aun sin procesar para relajarlo, simplemente relaja todas las aristas,

y lo hace |V|-1 veces, siendo |V| el numero de vrtices en el grafo. Las repeticiones permiten a las distancias

mnimas recorrer el rbol, ya que en la ausencia de ciclos negativos, el camino ms corto solo visita cada vrtice una

vez. A diferencia de la solucin voraz, la cual depende de la suposicin de que los pesos sean positivos, esta solucin se aproxima ms al caso general.

Existen dos versiones:

Versin no optimizada para grafos con ciclos negativos, cuyo coste de tiempo es O(VE)

Versin optimizada para grafos con aristas de peso negativo, pero en el grafo no existen ciclos de coste negativo, cuyo coste de tiempo, es tambin O(VE).

Aplicaciones de encaminamiento

Una variante distribuida del Algoritmo del Bellman-Ford se usa en protocolos de encaminamiento basados en vector

de distancias, por ejemplo el Protocolo de encaminamiento de informacin (RIP). El algoritmo es distribuido porque

envuelve una serie de nodos (routers) dentro de un Sistema autnomo(AS), un conjunto de redes y dispositivos router IP administrados tpicamente por un Proveedor de Servicio de Internet (ISP). Se compone de los siguientes

pasos:

1. Cada nodo calcula la distancia entre l mismo y todos los dems dentro de un AS y almacena esta informacin en una tabla.

2. Cada nodo enva su tabla a todos los nodos vecinos. 3. Cuando un nodo recibe las tablas de distancias de sus vecinos, ste calcula la ruta ms corta a los dems

nodos y actualiza su tabla para reflejar los cambios.

Las desventajas principales del algoritmo de Bellman-Ford en este ajuste son:

No escala bien

Los cambios en la topologa de red no se reflejan rpidamente ya que las actualizaciones se distribuyen nodo por nodo.

Contando hasta el infinito(si un fallo de enlace o nodo hace que un nodo sea inalcanzable desde un conjunto de otros nodos, stos pueden estar siempre aumentando gradualmente sus clculos de distancia a

l, y mientras tanto puede haber bucles de enrutamiento)

Mejoras

En 1970 Yen describi una mejora del algoritmo Bellman-Ford para un grafo sin ciclos con peso negativo. Esta

mejora primero asigna un orden arbitrario lineal a todos los vrtices y luego divide el conjunto de todas las aristas en uno o dos subconjuntos. El primer subconjunto, Ef, contiene todas las aristas (vi,vj) tales que i < j; mientras que el

segundo, Eb, contiene aristas (vi,vj) tales que i > j. Cada vrtice se visita en orden v1,v2,,vn, relajando cada arista saliente de ese vrtice en Ef. Cada vrtice es, despus, visitado en orden v|v|,v|v|,,v1, relajando cada arista saliente de ese vrtice en Eb. La mejora de Yen reduce a la mitad, de manera efectiva, el nmero de pases requeridos para la solucin del camino ms corto desde una nica fuente.

Problema Desarrollado No 6: Algoritmo de Bellman Ford

En este artculo se mostrar un ejemplo del Algoritmo de Bellman-Ford. Para ello se mostrar la siguiente tabla y a

partir de esta se explicar el procedimiento para hallar el camino mnimo de todos los vrtices a un nico vrtice

destino.

Figura No 24: Grafo inicial




Grafo inicial y Tabla de relaciones En este ejemplo partimos de este grafo, cuyas relaciones estn expuestas a su derecha:

o

Figura No 25: Grafo inicial y tabla de relaciones

Figura No 25: Camino mnimo final de todos los nodos al primero

Tabla de resolucin final En esta tabla se muestran las soluciones parciales que se han ido obteniendo a travs de la realizacin del algoritmo.




Explicacin del algoritmo

En la tabla anterior donde queda desarrollado el algoritmo paso por paso, podemos apreciar que la resolucin del algoritmo viene dada por aplicar las frmulas que vienen escritas en el paso n, a cada paso. El objetivo del algoritmo

es encontrar el camino mnimo desde todos los nodos al vrtice 1. En las frmulas donde viene D, es la distancia

mnima desde el nodo que aparece en el subndice al vrtice destino, en este caso, el vrtice 1.

En el paso 0, inicializamos todas las distancias mnimas a . En el paso 1, actualizamos el paso anterior, aplicando las frmulas. En este caso ponemos la distancia de

los nodos que tienen accesos directos al vrtice 1 y se la sumamos a la distancia mnima acumulada que

hay hasta el vrtice oportuno. Aqu esta distancia acumulada sera 0 para 1, debido a que sera la distancia a l mismo, e infinito para el resto porque no han sido analizados todava.

En el paso 2, al saber ya una distancia mnima acumulada desde los nodos 2 y 3 hasta 1, podemos actualizar las distancias mnimas de los nodos 4 y 5.

En los pasos sucesivos, se van actualizando las distancias mnimas acumuladas (D) de los distintos vrtices hasta 1, y se van utilizando en los pasos siguientes para optimizar el camino mnimo. El final del algoritmo

se da cuando no hay ningn cambio de un paso a otro, es decir, cuando ya no se puede encontrar un camino ms corto.

ALGORITMO DE JOHNSON El algoritmo de Johnson es una forma de encontrar el camino ms corto entre todos los pares de vrtices de un grafo dirigido disperso. Permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo.

Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformacin en el grafo inicial que elimina

todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado. Su nombre viene de Donald B. Johnson, quien fuera el primero en publicar la tcnica en 1977.

Descripcin del algoritmo

El algoritmo de Johnson consiste en los siguientes pasos: 1. Primero se aade un nuevo nodo q al grafo, conectado a cada uno de los nodos del grafo por una arista de

peso cero.

2. En segundo lugar, se utiliza el algoritmo de Bellman-Ford, empezando por el nuevo vrtice q, para determinara para cada vrtice v el peso mnimo h(v) del camino de q a v. Si en este paso se detecta un ciclo negativo, el algoritmo concluye.

3. Seguidamente, a las aristas del grafo original se les cambia el peso usando los valores calculados por el algoritmo de Bellman-Ford: una arista de u a v con tamao w(u,v), da el nuevo tamao w(u,v) + h(u) h(v)

4. Por ltimo, para cada nodo s se usa el algoritmo de Dijkstra para determinar el camino ms corto entre s y los otros nodos, usando el grafo con pesos modificados.

En el grafo con pesos modificados, todos los caminos entre un par de nodos s y t tienen la misma cantidad h(s) h(t) aadida a cada uno de ellos, as que un camino que sea el ms corto en el grafo original tambin es el camino ms

corto en el grafo modificado y viceversa. Sin embargo, debido al modo en el que los valores h(v) son computados, todos los pesos modificados de las aristas son no negativos, asegurando entonces la optimalidad de los caminos

encontrados por el algoritmo de Dijkstra. Las distancias en el grafo original pueden ser calculadas a partir de las

distancias calculadas por el algoritmo de Dijkstra en el grafo modificado invirtiendo la transformacin realizada en

el grafo.

Ejemplo

Las etapas del algoritmo de Johnson estn descritas en la siguiente ilustracin:

En la imagen de la izquierda tiene dos aristas negativas y no contiene ciclos negativos. En la segunda imagen se muestra el nuevo vrtice q con peso 0 hacia todos los nodos. En la tercera imagen, se muestra el rbol de caminos

mnimos calculado con el algoritmo de Bellman-Ford con q como vrtice inicial, y los valores h(v) calculados para




cada otro nodo como la longitud del camino ms corto entre q y ese nodo. A modo de ilustracin, en dicha imagen

solo aparecen los caminos que se tomaran para determinar cada valor h(v). Ntese que todos estos valores h(v) no son positivos, porque q tiene una arista de unin con cada nodo de peso 0, y por tanto el camino ms corto no puede

ser mayor que ese valor. En la parte derecha se muestra el grafo modificado, hecho reemplazando el peso de cada

arista w(u,v) por w(u,v) + h(u) h(v). En este grafo modificado, todos los pesos de las aristas son positivos y el camino ms corto entre dos nodos cualesquiera usa la misma secuencia de aristas que en el camino ms corto entre los mismos dos nodos en el grafo original. El algoritmo concluye aplicando el algoritmo de Dijkstra para cada uno

de los cuatro nodos originales en el grafo modificado (cuarta imagen).

Implementacin La estructura de datos para almacenar el grafo consiste en una representacin de cada vrtice como una lista de las

aristas que parten del mismo. Estas aristas constan de un origen, un destino y un peso. El conjunto de vrtices se

representa como un array de vrtices y un ndice que nos indica el ltimo vrtice empleado del array.

La implementacin del algoritmo devuelve una matriz de elementos precedentes y otra de distancias, mediante la primera se puede seguir el camino de menor coste desde un nodo dado a cualquier otro nodo del grafo, y si

paralelamente vamos sumando las distancias de la otra matriz, obtenemos los costes totales de dichos caminos

mnimos.

Pseudocdigo

Algoritmo de bsqueda A

RBOL DE EXPANSIN En el campo matemtico de la teora de grafos, un rbol de expansin T de un grafo conexo, no dirigido G es un rbol compuesto por todos los vrtices y algunas (quiz todas) de las aristas de G. Informalmente, un rbol de

expansin de G es una seleccin de aristas de G que forman un rbol que cubre todos los vrtices. Esto es, cada

vrtice est en el rbol, pero no hay ciclos.

Por otro lado, todos los puentes de G deben estar contenidos en T. Un rbol de expansin de un grafo conexo G puede ser tambin definido como el mayor conjunto de aristas de G

que no contiene ciclos, o como el mnimo conjunto de aristas que conecta todos los vrtices.

En ciertos campos de la teora de grafos es til encontrar el mnimo rbol de expansin de un grafo ponderado.

Tambin se han abordado otros problemas de optimizacin relacionados con los rboles de expansin, como el mximo rbol de expansin, el mximo rbol que cubre al menos k vrtices, el mnimo rbol de expansin con k

aristas por vrtice como mximo (rbol de expansin de mnimo grado, MDST por sus siglas en ingls), el rbol de

expansin con el mximo nmero de hojas (estrechamente relacionado con el problema del menos conjunto

dominante y conexo), el rbol de expansin con el menor nmero de hojas (relacionado con el problema del camino hamiltoniano), el rbol de expansin de mnimo dimetro o el rbol de expansin de la mnima dilacin.

rboles de Expansin Mnimales Ciclos fundamentales y cortes fundamentales

Si se aade una sola arista a un rbol de expansin, se crea un ciclo: los ciclos de ese tipo se denominan ciclos

fundamentales. Hay un ciclo fundamental distinto para cada arista; es decir, hay una correspondencia biyectiva (uno

a uno) entre ciclos fundamentales y aristas ausentes del rbol de expansin. Para un grafo conexo con V vrtices, cualquier rbol de expansin tiene V-1 aristas, y as, un grafo con E aristas tiene E-V+1 ciclos fundamentales. En

cualquier rbol de expansin dado, esos ciclos forman una base del espacio de ciclos.

De manera dual a la nocin de ciclo fundamental, existe el concepto de corte fundamental. Al eliminar una arista del

rbol de expansin, los vrtices se dividen en dos conjuntos disjuntos (desconectados). El corte fundamental se




define como el conjunto de aristas que deben ser eliminados de un grafo G para llegar a la misma divisin. Por

tanto, hay exactamente V-1 cortes fundamentales en un grafo, uno por cada arista del rbol de expansin. La dualidad entre cortes y ciclos fundamentales se manifiesta al observar que las aristas de un ciclo que no pertenece

al rbol de expansin slo pueden aparecer en los cortes de otras aristas del ciclo, y viceversa: las aristas en un corte

slo pueden aparecer en aquellos ciclos no contenidos en la arista correspondiente al corte. Este problema tiene algunas similitudes con el problema de la ruta ms corta. De manera general, en ambos casos se

considera una red no dirigida y conexa, en la que los datos dados incluyen medidas para cada ligadura (distancia,

costo, tiempo, etc.). Involucran tambin el hecho de seleccionar un conjunto de ligaduras que tiene la longitud total

ms corta entre todas las ligaduras que cumplen determinada propiedad. En el problema de la ruta ms corta, la ligadura seleccionada debe generar una trayectoria entre el origen y el destino, mientras que para el rbol de

expansin mnima se requiere que las ligaduras seleccionadas generen una trayectoria entre cada par de nodos, de tal

manera que la suma de todas las trayectorias sea mnima. Una red con n nodos solo requiere n 1 ligaduras para generar una trayectoria entre cada par de nodos. Por lo tanto, el problema es encontrar el rbol de expansin total mnima de sus ligaduras.

El problema del rbol de mnima expansin se resuelve normalmente con el inicio en cualquier nodo. El primer paso

consiste en seleccionar la rama ms corta posible a otro nodo desde el inicio, sin preocuparse del efecto que esta eleccin pueda tener en las decisiones posteriores. El segundo paso consiste en identificar el nodo no conectado ms

cercano a cualquiera de los dos que se acaban de conectar y despus agregar la ligadura correspondiente a la red.

Este proceso se repite, segn el resumen que se da a continuacin, hasta que se hayan conectado todos los nodos.

Algoritmo para el problema del rbol de expansin mnima. Paso 1: Se selecciona, de manera arbitraria, cualquier nodo y se conecta al nodo ms cercano distinto de ste.

Paso 2: Se identifica el nodo no conectado ms cercano a un nodo conectado, y se unen estos nodos dos nodos. Este paso se repite hasta que se hayan conectado todos los nodos. Los empates para el nodo no conectado ms cercano, se

rompen arbitrariamente y el algoritmo an tiende a una solucin ptima. Sin embargo, los empates indican la

posibilidad de soluciones ptimas mltiples: Todas esas soluciones, si existen, se pueden encontrar si se buscan las

dems formas de romper los empates hasta el final.

Es un problema clsico de optimizacin combinatoria, formulado en 1926 por Boruvka quien lo plante para

resolver el problema de hallar la forma ms econmica de distribuir energa elctrica en el sur de Moravia. La

formulacin de este problema ha sido til para la realizacin de muchas investigaciones en varios campos como el transporte, electrnica, telecomunicaciones e investigacin de operaciones.

El modelo contempla un conjunto de arcos que conectan todos los nodos de la red sin crear un solo ciclo o vuelta. El

problema consiste en determinar el rbol que minimiza la distancia de conexin total; se resuelve por el Algoritmo

de Etiquetado. En cuanto a la introduccin de datos y el proceso de solucin es similar a los modelos anteriores de este mdulo.

El algoritmo de rbol de expansin mnima enlaza los nodos de una red, en forma directa o indirecta, con la mnima

longitud de las ramas enlazantes. Una aplicacin caracterstica es en la construccin de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por uno o ms poblaciones adicionales. El

diseo ms econmico del sistema de caminos indica que se minimice la distancia total de caminos pavimentados,

resultado que se obtiene implementando el algoritmo de rbol de expansin mnima.




Figura No 27: rbol de expansin mnima

Un ejemplo de rbol expandido mnimo. Cada punto representa un vrtice, el cual puede ser un rbol por s mismo.

Se usa el Algoritmo para buscar las distancias ms cortas (rbol expandido) que conectan todos los puntos o

vrtices.

Este problema surge cuando todos los nodos de una red se deben conectar entre ellos, sin formar un ciclo. Se dice

que un ciclo se presenta cuando el nodo de inicio de una ruta es el nodo final.

El rbol de expansin mnima es apropiado para problemas en los cuales el flujo a lo largo de los arcos se considera

instantneo.

ALGORITMO DE KRUSKAL El algoritmo de Kruskal es un algoritmo de la teora de grafos para encontrar un rbol recubridor mnimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un rbol, incluyen todos los

vrtices y donde el valor total de todas las aristas del rbol es el mnimo. Si el grafo no es conexo, entonces busca un

bosque expandido mnimo (un rbol expandido mnimo para cada componente conexa). El algoritmo de Kruskal es

un ejemplo de algoritmo voraz. Funciona de la siguiente manera:

se crea un bosque B (un conjunto de rboles), donde cada vrtice del grafo es un rbol separado

se crea un conjunto C que contenga a todas las aristas del grafo

mientras C es novaco o eliminar una arista de peso mnimo de C o si esa arista conecta dos rboles diferentes se aade al bosque, combinando los dos rboles en un

solo rbol

o en caso contrario, se desecha la arista Al acabar el algoritmo, el bosque tiene una sola componente, la cual forma un rbol de expansin mnimo del grafo.

Este algoritmo fue publicado por primera vez en Proceedings of the American Mathematical Society, pp. 4850 en 1956, y fue escrito por Joseph Kruskal.

Como el algoritmo de Prim, el algoritmo ideado por J.B. Kruskal en el ao 1956 (On the shortest spanning subtree of a graph and the traveling salesman problema) se basa en la propiedad de los arboles de expansin minimales: partiendo del rbol vaco, se selecciona a cada paso la arista de menor etiqueta que no provoque ciclo sin requerir

ninguna otra condicin sobre sus extremos.

1. Comenzar en forma arbitraria en cualquier nodo y conectarlo con el ms prximo (menos distante o

costoso).

2. Identificar el nodo no conectado que est ms cerca o menos costoso de alguno de los nodos conectados. Deshacer los empates de forma arbitraria. Agregar este nodo al conjunto de nodos conectado.

3. Repartir este caso hasta que se hayan conectado todos los nodos.

Problema Desarrollado No 8: EL TRANSITO DE LA CIUDAD DE LIMA




La ciudad de Lima est planificando el desarrollo de una nueva lnea en sistemas de trnsito.

El sistema debe unir 8 zonas residenciales y centros comerciales. El Direccin metropolitana de transito necesita seleccionar un conjunto de lneas que conecten todos los centros a un

mnimo costo.

La red seleccionada debe permitir:

- Factibilidad de las lneas que deban ser construidas. - Mnimo costo posible por lnea.

RED QUE REPRESENTA EL ARBOL EXPANDIDO.

Solucin - Analoga con un problema de redes

El algoritmo que resuelve este problema es el algoritmo de Kruskal. Algoritmo:

Empezar seleccionando, desde un arco inicial, el arco de menor longitud.

En cada iteracin, agregue el siguiente arco de menor longitud del conjunto de arcos disponibles, tomando la

precaucin de no formar ningn ciclo El algoritmo finaliza cuando todos los nodos estn conectados.

Partimos del nodo 1 y marcamos la arista que une el nodo 1 y el 2, por ser la arista de menor valor (28) no marcada.


desarrollado No 7

Figura No 29: Primera Iteracin




Marcamos la arista que une el nodo el nodo 2 con el 4, por ser la arista de menor valor (32), no marcada que no

forma ciclos.

Figura No 30: Primera Iteracin

Figura No 31: Segunda Iteracin

Figura No 32: Segunda Iteracin




Marcamos la arista que une el nodo 4 y el nodo 3, por ser la arista menor (30) que no forma ciclos con los ya marcados anteriormente.


Figura No 33: Tercera Iteracin

Figura No 34: Cuarta Iteracin







Figura No 37: Quinta Iteracin





Marcamos la arista que une el nodo 6 y el nodo 7, por ser la arista menor (36) que no forma ciclos con los ya

marcados anteriormente.

Marcamos la arista que une el nodo 5 y el nodo 8, por ser la arista menor (38) que no forma ciclos con los ya

marcados anteriormente.


Figura No 40: Sexta Iteracin

Figura No 41: Stima Iteracin




FIN. Tenemos marcados n1 aristas, siendo n el nmero de nodos.

RESPUESTA

RUTA COSTO

1 - 2 28

2 - 4 32

4 - 3 30

2 - 7 37

7 - 6 36

2 - 5 35

5 - 8 38

236

Solucin con DS POM del rbol de Expansin Mnima

Figura No 42: Stima Iteracin

Figura No 43: rbol de expansin mnima




Seleccione la opcin Minimum Spanning Tree

Ingrese el nmero de arcos y digite el nombre

Figura No 44: Ventana en forma de matrix para el ingreso de datos

En la ventana anterior debe digitar el inicio, fin y distancia del arco. A continuacin de clic en Solve

Figura No 44: Ventana para

ingresar y seleccionar del DS

POM




Figura No 45: Ventana de resultados

Ejemplo Desarrollado No 9: La figura siguiente muestra todas las posibilidades de construir una red elctrica

entre siete municipios (nodos) de un distrito a partir de una subestacin colocada en el nodo 1. Loa valores

asociados con los arcos son los costos en millones de dlares para unir cada par de municipios, determinar cmo debe tenderse la red entre los municipios, de tal manera que todos queden conectados a un costo mnimo.

Figura No 46: Red que representa la solucin

optima




La tabla de la pgina siguiente muestra que el rbol de expansin de mnimo costo total para la red elctrica entre

los siete municipios (nodos) del distrito de la figura anterior es de 44 millones de dlares, representado por los

siguientes circuitos: 1 2 4 3

5 6 7

Figura No 47: Posibilidades de construir una red elctrica entre siete municipios

Aplicacin del algoritmo del rbol de expansin mnima para el ejemplo.

Nodos

conectados i

Nodo k de menor costo

que puede ser

conectado a un nodo i

Costo

Cik

Costo acumulado Tk Costo menor

acumulado Tk

1 1 2 6 6 6 1 2 2 4 6 6+6 12 1 2 4 4 3 4 12+4 16 1 2 4 3 4 5 9 16+9 25 1 2 4 3

5

5 6 4 25+4 29

1 2 4 3

5 6

6 7 15 29+15 44

Figura No 48: Diseo para construir una red elctrica entre siete municipios




Ejemplo Desarrollado No

8: Algoritmo de Kruskal

Este es el grafo original. Los nmeros de las aristas indican su peso.

Ninguna de las aristas est resaltada.

AD y CE son las aristas ms cortas, con peso 5, y AD se ha elegido

arbitrariamente, por tanto se resalta.

Sin embargo, ahora es CE la arista ms pequea que no forma ciclos, con

peso 5, por lo que se resalta como segunda arista.

La siguiente arista, DF con peso 6, ha sido resaltada utilizando el

mismo mtodo.




Las siguientes aristas ms pequeas son AB y BE, ambas con peso 7. AB

se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo,

porque formara un ciclo ABD si se hubiera elegido.

modelosoptimizacionredes

Documents