1.- Las distancias en millas entre ciudades de
Indiana: Gary, Fort Wayne, Evansville, Terre Haute y South Bend, se muestran en
la siguiente tabla. Es necesario construir un sistema estatal de carreteras que
una todas estas ciudades. Suponga que por razones políticas no es necesario
construir una carretera a Gary y Fort Evansville ¿Cuál es la longitud mínima de
la carretera requerida?
Gary
|
Fort Wayne
|
Evansville
|
Terre Haute
|
South Bend
|
|
Gary
|
--
|
132
|
217
|
164
|
58
|
Fort Wayne
|
132
|
--
|
290
|
201
|
79
|
Evansville
|
217
|
290
|
--
|
113
|
303
|
Terre Haute
|
164
|
201
|
113
|
--
|
196
|
South Bend
|
58
|
79
|
303
|
196
|
--
|
Por el método de Kruskal,se tiene lo siguiente:
Iteración
|
Aristas Ordenadas
|
K
|
Costo
|
1
|
(1,5)
|
1
|
58
|
2
|
(2,5)
|
2
|
137
|
3
|
(4,3)
|
3
|
250
|
4
|
(1,2)
|
3
|
250
|
5
|
(1,4)
|
4
|
414
|
6
|
(5,4)
|
4
|
414
|
7
|
(2,4)
|
4
|
414
|
8
|
(1,3)
|
4
|
414
|
9
|
(2,3)
|
4
|
414
|
10
|
(5,3)
|
4
|
414
|
La distancia mínima entre las carreteras será de 414 millas.
No hay comentarios:
Publicar un comentario