Actividad09_Martinez_Nava_Jorge_Justino - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

Universidad de Guadalajara 
 
Centro Universitario de Ciencias Exactas e Ingeniería 
 
Algoritmia 
 
Profesor: Salomón Eduardo Ibarra Chávez 
 
Alumno: Jorge Justino Martinez Nava 
 
Actividad 09 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
B) Algoritmo de Prim. 
 
 Peso del árbol de expansión: 24 
 Vértice de Inicio: 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Aristas Peso Aceptación 
6 — 7 1 Si 
7 — 2 4 Si 
2 — 1 3 Si 
1 — 3 2 Si 
3 — 5 8 Si 
5 — 0 6 Si 
3 — 6 5 No 
4 — 6 6 No 
1 — 4 9 No 
2 — 4 10 No 
0 — 1 7 No 
Grafo 2. 
 
 
 
 
 
 
 
 
 
a) Algoritmo de Kruskal 
 
 
 Peso del árbol de expansión: 54 
 
 
 
 
 
 
 
 
Aristas Peso 
A — B 3 
A — E 4 
A — J 5 
A — F 1 
 B — C 6 
B — E 4 
B — G 7 
B — H 2 
C — D 7 
 D — H 4 
E — J 6 
E — I 7 
F — J 7 
G — J 3 
G — L 5 
H — L 3 
J — K 6 
K —L 3 
1 2 3 4 
5 6 7 8 
9 10 11 12 
a) Algoritmo de Prim. 
 
 
 Peso del árbol de expansión: 45 
 Vértice de Inicio: 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Aristas Peso Aceptacion 
7 — 10 3 Si 
10 — 9 4 Si 
9 — 5 7 Si 
5 — 1 4 Si 
 1 —6 1 Si 
1 — 2 3 Si 
2 — 8 2 Si 
8 — 12 3 Si 
9 — 11 7 Si 
8 — 4 4 Si 
4 — 3 7 Si 
2 — 7 7 No 
7 — 12 5 No 
10 — 11 6 No 
2 — 3 6 No 
 5 — 10 6 No 
1 — 10 6 No 
Grafo 3. 
 
 
 
 
 
 
 
 
 
 
a) Algoritmo de Kruskal 
 
 
 Peso del árbol de expansión: 43 
 
 
 
 
 
 
 
 
 
 
 
Aristas Peso 
A — B 2 
A — D 3 
A — E 5 
B — C 10 
 C — E 2 
 C — H 5 
C — I 6 
D — F 8 
F — H 3 
F — E 7 
F — G 4 
H — C 5 
G — J 11 
I — C 6 
b) Algoritmo de Prim. 
 
 Peso del árbol de expansión: 45 
 Vértice de Inicio: 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Aristas Peso Aceptación 
G — F 4 Si 
F — H 3 Si 
H — C 5 Si 
C — E 2 Si 
E — A 5 Si 
A — B 2 Si 
A — D 3 Si 
C — I 6 Si 
B — C 10 No 
D — F 8 No 
E — F 7 No 
G — I 11 No