rbol de expansi n

Árbol de expansión
Ejemplo 1:
En un desarrollo residencial se construirá una red de cableado eléctrico y de comunicaciones con tuberías subterráneas. En la siguiente figura se muestra la posición ylongitud (en metros) de las tuberías compatibles con el proyecto. Determine la red mínima que interconecta todas las casas, partiendo de la casa 1.
Solución:
De los arcos contenidos en el conjunto seselecciona el de menor longitud , en este caso el arco 1-4


Segunda expansión Tercera expansión

Cuarta expansión Quintaexpansión

Sexta expansión Séptima expansión

Octava expansión Novena expansión


Décima expansiónUndécima expansión

Duodécima expansión Decimotercera expansión
Con los nodos 1-4 conectados expande el conjunto conexo y se encuentra el arco con menorlongitud 4-7. Al conectar el nodo 7 se observa que los arcos 3-4, 6-7 y 7-10 tienen la misma longitud ; se selecciona arbitrariamente el arco 3-4. Con el nodo 3 conectado con el nodo a través delarco 3-4 se descarta el arco 1-3; el arco con menor longitud es el arco 3-6. El nuevo arco de menor longitud es ahora el 6-9. El arco 6-7 se descarta y se observa que existen dos arcos con longitud de 30m; se selecciona arbitrariamente el arco 7-10. El arco 9-10 se descarta y el 9-12 pasa a formar parte del árbol de expansión. Los arcos 1-2 y 4-5 tienen la menor longitud; arbitrariamente se escogeel 4-5. Se descarta el arco 5-7 y se observa que el arco 2-5 es el menor. El arco 1-2 es descartado y el 12-14 es elegido. El arco 13-14 es el menor, por lo tanto el nodo 13 entra al conjunto conexo.El arco 19-13 se descarta y el árbol se expande desde el nodo 13 hacia el nodo 11. De los tres arcos restantes el de menor longitud es el 8-11, que es el último perteneciente al árbol de mínima...