Arbol de costo minimo

Vista previa del material en texto

Trabajo de grafos 
 
 
 
Presentado a: José Waldo de la Ossa 
 
 
 
Presentado por: Daniela Torres 
Luis Buelvas 
Richard Torres 
 
 
 
 
Universidad de Córdoba 
 
 
 
 
Ingeniería de sistemas 
 
 
 
 
 
Montería-Córdoba 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Ejercicio 1. ¿Compruebe si los grafos G y H son isomorfos?... demuestre mediante las matrices 
de adyacencia. (Valor 1 punto) 
 
 
 
 
 
 
G H 
 
 
 
 
Matrices de adyacencia 
 A B C D E F G 
A 0 1 1 1 0 0 0 
B 1 0 0 0 1 0 0 
C 1 0 0 0 0 1 0 
D 1 0 0 0 1 0 1 
E 0 1 0 1 0 0 1 
F 0 0 1 0 0 0 1 
G 0 0 0 1 1 1 0 
 
 7 4 3 6 5 2 1 
7 0 1 1 1 0 0 0 
4 1 0 0 0 1 0 0 
3 1 0 0 0 0 1 0 
6 1 0 0 0 1 0 1 
5 0 1 0 1 0 0 1 
2 0 0 1 0 0 0 1 
1 0 0 0 1 1 1 0 
 
 
Ejercicio 2. Sea un grafo no dirigido (figura 2), mostrar: (valor 1 punto) 
a) El árbol de expansión de costo mínimo utilizando el algoritmo de Kruskal. 
 
 
 
b) El árbol de expansión de costo mínimo utilizando el algoritmo de Prim. ¿Son iguales 
las soluciones obtenidas en ambos algoritmos? En caso contrario, ¿son válidas las 
distintas soluciones? ¿Por qué? 
c) Determine cuál de los dos algoritmos es más eficiente? Sustente su repuesta. 
 
 
Figura 2 
 
 
 
a. El árbol de expansión de costo mínimo utilizando el algoritmo de Kruskal 
 
 
 
 
 
 
 
 
 
b. El árbol de expansión de costo mínimo utilizando el algoritmo de Prim. ¿Son 
iguales las soluciones obtenidas en ambos algoritmos? En caso contrario, ¿son 
válidas las distintas soluciones? ¿Por qué? 
 
 
R/ El resultado de los grafos no es necesariamente igual, ya que puede variar 
dependiendo de los parámetros, pero los resultados en este caso varían pero 
son igualmente validos ambos resultados. 
Ejercicio 3. Un grupo de amigos tiene establecido un chat privado en donde solo 
hablan entre ellos. La frecuencia de diálogo no es la misma para todos y tampoco 
todos hablan con todos. Se ha resumido en una tabla el tiempo transcurrido (en 
minutos) entre conversaciones para cada par de amigos. (Valor 2 punto) 
 
 Pedro Juan Ana Lola Lucia Jesús 
Pedro 4 10 1 20 26 
Juan 2 34 3 48 
Ana 45 5 60 
Lola 10 24 
Lucia 12 
Jesús 
 
Si Lola recibe una noticia, ¿Cuánto tiempo tardaran en conocerla todos? 
¿Cuánto tiempo transcurre como mínimo desde que uno cualquiera recibe 
una noticia hasta que la conocen todos? Elabore el grafo.
 
 
 
 
Si Lola recibe una noticia, ¿Cuánto tiempo tardaran en conocerla todos? 
∑ T= 1 + 4 + 2 + 5 + 12 = 24 
 
¿Cuánto tiempo transcurre como mínimo desde que uno cualquiera recibe una noticia 
hasta que la conocen todos? 
 
Tomaremos de punto a Pedro, el cual ya lleva un tiempo acumulado de 1 minutos desde que la 
noticia partió, hasta que llego a él; con eso tenemos que, Lola se la comunicó a Pedro, ósea 
que ya les llego; Tarda 4 minutos en hacerle llegar la noticia a Juan, 3 minutos en enviársela a 
Lucia y 2 minutos en enviársela a Ana, 12 minutos después de que Lucia recibe el mensaje, 
este llega a Jesús, esto quiere decir que tardan 19 minutos el mensaje de llegar de Pedro a 
Jesús. 
 
 
 
 
 
 
1 
1 
24 
24 
10 
10 
34 
34 
45 
45 
10 10 
4 
4 
20 
20 
26 
26 60 
60 
48 48 
12 
12 
5 
5 
3 
3 
2 
2 
 
 
 
Ejercicio 4. Aplicar el algoritmo de Kruskal sobre el siguiente grafo (figura 
3), mostrando el orden en que son añadidas las aristas a la solución. (Valor 1 
punto) 
 
 
 
 
 
Algoritmo de 
Kruskal 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
a) Si aplicáramos el algoritmo de Prim, ¿podemos asegurar que se obtendría 
siempre la misma solución? ¿Podemos asegurar que el costo de la solución 
sería el mismo? 
R/ Si, ya que utilizando ambos algoritmos ya que aplicando ambos siempre se quiere 
encontrar el camino menos costoso para llegar al objetivo, aunque en algunas ocasiones 
puede que ambos grafos sean distintos de manera mínima 
 
 
 
 
 
 
 
Algoritmo de prim