Árbol De Expansión Mínima
Páginas: 3 (608 palabras)
Publicado: 11 de diciembre de 2012
Árbol de expansión mínima
El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del problema de la ruta más corta que se presentó con anterioridad. En amboscasos se considera una red no dirigida y conexa, en la que la información dada incluye alguna medida de longitud positiva (distancia, costo, tiempo, etc.) asociada con cada ligadura. Los dos problemasinvolucran también el hecho de seleccionar un conjunto de ligaduras con la longitud total más corta entre todos los conjuntos de ligaduras que satisfacen cierta propiedad.
Algunas aplicaciones1.- Diseño de redes de telecomunicación (de computadores, telefónicas, de televisión por cable, etc.)
2.- Diseño de redes de transportes para minimizar el costo total de proporcionar las ligaduras(vías ferroviarias, carreteras)
3.- Diseño de una red de líneas de transmisión de energía eléctrica de alto voltaje
4.- Diseño de una red de cableado en equipo eléctrico (como sistema de cómputo)para minimizar la longitud total del cable.
5.- Diseño de una red de tuberías para conectar varias localidades
Algoritmo para el problema del árbol de expansión mínima
1.- Se selecciona, de maneraarbitraria, cualquier nodo y se conecta (es decir, se agrega una ligadura) al nodo distinto más cercano.
2.- Se identifica el nodo no conectado más cercano a un nodo conectado y se conectan estosdos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que todos los nodos están conectados.
3.- Empates: los empates para el nodo más cercano distinto (paso 1) o para elnodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo debe llegar a una solución óptima. No obstante, estos empates son señal de que pueden existir (pero nonecesariamente) soluciones óptimas múltiples. Todas esas soluciones se pueden identificar si se trabaja con las demás formas de romper los empates hasta el final.
El problema de árbol de expansión...
El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del problema de la ruta más corta que se presentó con anterioridad. En amboscasos se considera una red no dirigida y conexa, en la que la información dada incluye alguna medida de longitud positiva (distancia, costo, tiempo, etc.) asociada con cada ligadura. Los dos problemasinvolucran también el hecho de seleccionar un conjunto de ligaduras con la longitud total más corta entre todos los conjuntos de ligaduras que satisfacen cierta propiedad.
Algunas aplicaciones1.- Diseño de redes de telecomunicación (de computadores, telefónicas, de televisión por cable, etc.)
2.- Diseño de redes de transportes para minimizar el costo total de proporcionar las ligaduras(vías ferroviarias, carreteras)
3.- Diseño de una red de líneas de transmisión de energía eléctrica de alto voltaje
4.- Diseño de una red de cableado en equipo eléctrico (como sistema de cómputo)para minimizar la longitud total del cable.
5.- Diseño de una red de tuberías para conectar varias localidades
Algoritmo para el problema del árbol de expansión mínima
1.- Se selecciona, de maneraarbitraria, cualquier nodo y se conecta (es decir, se agrega una ligadura) al nodo distinto más cercano.
2.- Se identifica el nodo no conectado más cercano a un nodo conectado y se conectan estosdos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que todos los nodos están conectados.
3.- Empates: los empates para el nodo más cercano distinto (paso 1) o para elnodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo debe llegar a una solución óptima. No obstante, estos empates son señal de que pueden existir (pero nonecesariamente) soluciones óptimas múltiples. Todas esas soluciones se pueden identificar si se trabaja con las demás formas de romper los empates hasta el final.
El problema de árbol de expansión...
Leer documento completo
Regístrate para leer el documento completo.