Scribd
Cargar
749 vistas3 páginas

Ejercicio 5

Un ayuntamiento quiere llevar el agua desde un depósito municipal a 7 casas rurales de la forma más barata posible. Se proporciona un tabla con los posibles conexiones y sus costos. Se pide calcular todas las formas posibles de conectar las casas con el costo total mínimo, y razonar cuántas conexiones se necesitarían si hubiera 8 casas en lugar de 7.

Cargado por

frafra907
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
749 vistas3 páginas

Ejercicio 5

Un ayuntamiento quiere llevar el agua desde un depósito municipal a 7 casas rurales de la forma más barata posible. Se proporciona un tabla con los posibles conexiones y sus costos. Se pide calcular todas las formas posibles de conectar las casas con el costo total mínimo, y razonar cuántas conexiones se necesitarían si hubiera 8 casas en lugar de 7.

Cargado por

frafra907
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Pregunta IO

1) Un Ayuntamiento quiere disear el modo para llevar el agua desde el depsito municipal
D a 7 casas rurales, no necesariamente de forma directa, con el menor coste posible. Las
posibles conducciones entre los depsitos y la casa con sus respectivos costes
correspondientes, en unidades unitarias, vienen recogidas en la siguiente tabla:


Por ejemplo, realizar una conduccin entre la casa 2 y la casa 5 tiene un coste de 4 unidades
monetarias.
a) Calcular todas las formas posibles de establecer las conexiones para el coste total sea el
mnimo.
b) Si en lugar de 7 casas tenemos 8 casas. Cuntas conducciones se necesitaran? Razonar la
Respuesta.



Solucin:
a) Problema del rbol de expansin mnima cuya red asociada es:


Ordenamos en orden creciente las aristas segn el coste y aplicamos el algoritmo Kruskal.
Se tienen dos soluciones ptimas cuyo coste total mnimo es de 30 unidades monetarias.

Solucin ptima A:

Sumando los costes: (10)+ (3)+ (2)+ (3)+ (5)+ (3)+ (4) = 30 unid. Monetarias


Solucin ptima B:

Sumando los costes: (10)+ (3)+ (2)+ (3)+ (5)+ (3)+ (4) = 30 unid. Monetarias

b) Se sabe que dado un subgrafo G de un grafo no dirigido G de n nodos, si G es un rbol de
expansin entonces G tienen n-1 aristas.
Vemos que el apartado anterior las soluciones ptimas tienen 7 conexiones, una menos
que el nmero de nodos. Si en lugar de 7 casas tenemos 8, entonces todas las soluciones
tienen 8 conexiones.

También podría gustarte