MODELO DE REDES

EJERCICIOS RESUELTOS:
1.- Dada la siguiente red obtenga el árbol de mínima expansión

SOLUCIÓN

Caminos que se deben pavimentar
-	1	2	3	4	5	6	7
1 (2)	x	224	-	-	-	300	539
2 (1)	224	x	200	-	-	-	539
3 (inicio)	-	200	x	400	-	-	600
4 (5)	-	-	400	x	400	-	200
5 (6)	-	-	-	400	x	600	447
6 (3)	300	-	-	-	600	x	283
7 (4)	539	539	600	200	447	283	x

 -- Árbol de expansión mínima = 200+224+300+283+200+400 = 1607

2.- La siguiente red representa una serie de poblados que se encuentran comunicados a través de caminos rurales o empedrados. El Gobernador del Estado al que pertenecen ha aprobado se pavimenten los caminos que permitan unir a todos los poblados, buscando que la distancia a pavimentar sea la mínima posible. ¿Cuáles caminos son los que se deben de pavimentar?

Caminos que se deben pavimentar
Iteración	Ck	Cck	Distancia
1	1	234567	0
2	13	24567	4
3	132	4567	6
4	1327	456	6
5	13276	45	3
6	132765	4	5
7	1327654	--	6
-	-	-	30

3.- La siguiente red representa una serie de nuevas colonias que se han establecido en una localidad, la compañía de Luz desea suministrar el servicio correspondiente, para ello se requiere instalar el cableado eléctrico. Determine la cantidad de km de cable mínimo que debe de instalarse de tal forma que se proporcione el servicio a todas las colonias?

Caminos que se deben pavimentar
Iteración	Ck	Cck	Distancia
1	3	124567	0
2	32	14567	4
3	326	1457	6
4	3267	145	7
5	32675	14	7
6	326754	1	6
7	3267541	--	11
-	-	-	41

     -- La distancia minima de cable necesario es de 41km

4.- El tránsito de Rusia está planificando la construcción de una línea de sistemas de transito que conecte 7 zonas principales de la ciudad. (A, B, C, D, E, F, G). Donde los kilómetros entre ellas se representan son un número en el arista correspondiente. Cada kilómetro de construcción le costara al tránsito 4 millones.El transito desea acortar la distancia de traslación entre las 7 zonas pero asegurando no gastar demasiado del presupuesto. Es decir, desean optimizar la construcción por kilómetro recorrido.

SOLUCIÓN

1.- A Y D son aristas que se han elegido arbitrariamente y las resaltamos en color verde.

2.- Para este grafico C es la arista mas pequeña que no forma ciclos, con distancia 5 , por lo que se resalta como la segunda arista.

3.- La siguiente arista DF con distancia 6 , ha sido resaltada utilizando el mismo método.

4.- Las siguientes aristas mas pequeñas son AB y BE, ambas con distancia de 7. AB se elige arbitrariamente y se resalta, la arista BD se resalta en rojo porque formaría un ciclo ABD si se hubiera elegido.

5.-El proceso continua marcando aristas, BE con distancia 7. Muchas otras aristas se marcaron en rojo en este paso BC.(  formaría el ciclo BCE) ,DE (formaría el ciclo DEBA) , Y FE ( formaría el ciclo FEBAD )