Investigacion

2.3 Problema árbol expandido mínimo
2.3 Problema árbol expandido mínimo
Árbol de expansión mínima
Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar unloop.
El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantáneo.
EL TRANSITO DEL DISTRITOMETROPOLITANO
· La ciudad de Vancouver está planificando el desarrollo de una nueva línea en sistemas de tránsito.
· El sistema debe unir 8 residencias y centros comerciales.
· El distrito metropolitano detransito necesita seleccionar un conjunto de líneas que conecten todos los centros a un mínimo costo.
· La red seleccionada debe permitir:
Factibilidad de las líneas que deban ser construidas.Mínimo costo posible por línea.

Algoritmo
Los algoritmos que pueden dar solución a este problema son:
* Algoritmo de Dijkstra
* Algoritmo de Kruskal
* Algoritmo de Prim
En este artículotrataremos el algoritmo de Prim como forma de solución para la cobertura minima, debido a la simplicidad que este algoritmo conlleva puede ser aprovechado sin necesidad de ser un gran experto enprogramación.
Algoritmo de Prim
El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubiertopor Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.Consiste en un algoritmo de la teoría de los grafos para encontrar un árbol de coberturamínimo en un grafo conexo (grafo que  para cada par de nodos está conectado por un camino, o sea, si para cualquier par de nodos A y B, existe al menos un camino posible desde B hacia A), no dirigidoy cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el...