investigacion

Árbol de expansión mínima.
Este árbol vincula los nodos de una red valiéndose de la longitud mínima total de lasramas de conexión.

Trabajaremos con un ejemplo para comparar los métodos propuestospor los libros:

Hamdy A. Taha - Investigación De Operaciones
Investigación De Operaciones Hiller Lieberman
Investigación De Operaciones Serie De Shaum

Ejemplo:

La administración de la seervadaparck necesita determinar los caminos bajo los cuales deben tender líneas telefónicas para encontrar todas las estaciones con longitudes totales mínimas de cable. Se decidirá en base a la figura. (Lasdistancias están dadas en millas).










Todos los libros propone el mismo planteamiento para resolver el algoritmo del árbol de expansión mínima.
Paso 1: determinar cuál será el nodo inicial (eneste caso O)
Paso 2: conectar el nodo con distancia más corta al nodo inicial (O-A).
Paso 3: conectar el siguiente nodo más cercano a cualquiera delos nodos ya conectados.
Los nodos no pueden estarconectados repetidas veces
Solución:
1)










2)










3)









4)









5)








6)










Lugo de haber encontrado la red final podemos encontrar la longitud total de millasrecorridas.
O-A-B-C-E-D-T
2+2+1+3+1+5=14 MILLAS










RUTA MAS CORTA2
2 1 3

1 76

2 2 36
1

5 8
La red graficada contiene los datos de cada...