Actividad No 10 - Arbol de costo minimo

Vista previa del material en texto

UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORIA DE GRAFOS Semestre: IX Horario: Actividad No. 10 
Profesor: Jose Waldo de la Ossa Temática: Búsqueda de árbol de costo mínimos 
 
1 | T e o r í a d e G r a f o s V e r 6 . 2 3 
 
Consideraciones generales 
 La fecha de presentación es el 28-06-2023 a las 6:00 PM, en grupo (3 personas). 
 Recuerde que debe imprimir la actividad, desarrollarla a mano (bien presentado) y 
entregarlo al inicio de la clase. Pero, antes de entregar, un integrante del grupo debe 
escanear todo el documento y subirlo a la plataforma. 
 
Ejercicios 
Ejercicio 1. ¿Compruebe si los grafos G y H son isomorfos?... demuestre mediante las 
matrices de adyacencia. (Valor 1 punto) 
 
 
Figura 1 
 
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. 
 
G H
' 
 
UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORIA DE GRAFOS Semestre: IX Horario: Actividad No. 10 
Profesor: Jose Waldo de la Ossa Temática: Búsqueda de árbol de costo mínimos 
 
2 | T e o r í a d e G r a f o s V e r 6 . 2 3 
 
 
Figura 2 
 
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 
 
a) 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. 
 
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) 
 
 
 
 
 
 
 
UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORIA DE GRAFOS Semestre: IX Horario: Actividad No. 10 
Profesor: Jose Waldo de la Ossa Temática: Búsqueda de árbol de costo mínimos 
 
3 | T e o r í a d e G r a f o s V e r 6 . 2 3 
 
 
Figura 3 
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?