arbol de minimo recorrido
Páginas: 3 (627 palabras)
Publicado: 15 de abril de 2013
ARBOL DE MINIMO RECORRIDO
El árbol de mínimo recorrido no es más que otra forma o algoritmo para solucionar situaciones y optimizar problema de redes. Sin embargo es pertinente aclarar elconcepto de árbol en programación lineal. Un árbol es una red conectada compuesta por nodos pero que no llegan a formal un ciclo. También es importante definir el concepto de árbol en expansión que es unárbol que enlaza todos los nodos presentes en la red sin permitir ciclos.
Se infiere entonces que esta técnica del árbol de mínimo recorrido o expansión mínima conecta los nodos que están a una distanciamínima, por tanto se puede considerar que este método tiene algunas similitudes con la versión del problema de la ruta más corta. En ambos casos se considera red no dirigida y conexa, en la que lainformación dada incluye alguna medida de longitud positiva (distancia, costo, tiempo, etc.) asociada con cada conexión. Los dos problemas sugieren el hecho de seleccionar la forma o el conjunto deconexiones con la longitud total más corta de todas las posibles.
Existen algunas aplicaciones de esta técnica tales como:
a) Diseño de redes de telecomunicación (de computadores, telefónicas, detelevisión por cable, etc.).
b) Diseño de redes de transportes para minimizar el costo total de proporcionar las conexiones (vías ferroviarias, carreteras).
c) Diseño de una red de líneas de transmisiónde energía eléctrica de alto voltaje.
d) Diseño de una red de tuberías para conectar varias localidades.
En cuanto a la solución de un problema mediante la implementación del árbol de mínimorecorrido se puede hacer uso de los siguientes pasos que pueden llevar a una solución directa y optima:
1. Seleccionar cualquier nodo de manera arbitraria y conectarlo al nodo distinto más cercano; a esteprocedimiento se le denomina en ingeniería, agregar ligadura
2. Identificar el nodo no conectado más cercano a uno ya conectado y agregar una ligadura entre ellos. Esto se repite hasta que todos los...
El árbol de mínimo recorrido no es más que otra forma o algoritmo para solucionar situaciones y optimizar problema de redes. Sin embargo es pertinente aclarar elconcepto de árbol en programación lineal. Un árbol es una red conectada compuesta por nodos pero que no llegan a formal un ciclo. También es importante definir el concepto de árbol en expansión que es unárbol que enlaza todos los nodos presentes en la red sin permitir ciclos.
Se infiere entonces que esta técnica del árbol de mínimo recorrido o expansión mínima conecta los nodos que están a una distanciamínima, por tanto se puede considerar que este método tiene algunas similitudes con la versión del problema de la ruta más corta. En ambos casos se considera red no dirigida y conexa, en la que lainformación dada incluye alguna medida de longitud positiva (distancia, costo, tiempo, etc.) asociada con cada conexión. Los dos problemas sugieren el hecho de seleccionar la forma o el conjunto deconexiones con la longitud total más corta de todas las posibles.
Existen algunas aplicaciones de esta técnica tales como:
a) Diseño de redes de telecomunicación (de computadores, telefónicas, detelevisión por cable, etc.).
b) Diseño de redes de transportes para minimizar el costo total de proporcionar las conexiones (vías ferroviarias, carreteras).
c) Diseño de una red de líneas de transmisiónde energía eléctrica de alto voltaje.
d) Diseño de una red de tuberías para conectar varias localidades.
En cuanto a la solución de un problema mediante la implementación del árbol de mínimorecorrido se puede hacer uso de los siguientes pasos que pueden llevar a una solución directa y optima:
1. Seleccionar cualquier nodo de manera arbitraria y conectarlo al nodo distinto más cercano; a esteprocedimiento se le denomina en ingeniería, agregar ligadura
2. Identificar el nodo no conectado más cercano a uno ya conectado y agregar una ligadura entre ellos. Esto se repite hasta que todos los...
Leer documento completo
Regístrate para leer el documento completo.