Proyecto Operativa
Páginas: 6 (1424 palabras)
Publicado: 2 de junio de 2015
Proyecto: Problema del á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. En ambos casos 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 problemas involucrantambié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.
El problema del árbol de expansión mínima se puede resumir como sigue.
1) Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta enla red. (Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.)
2) Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos.
3) El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.
Una red con n nodos requiere sólo (n -1)ligaduras para proporcionar una trayectoria entre cada par de nodos. No deben usarse más ligaduras ya que esto aumentaría, sin necesidad, la longitud total de las ligaduras seleccionadas. Las (n -1) ligaduras deben elegirse de tal manera que la red resultante (con sólo las ligaduras seleccionadas) forme un árbol de expansión. Por lo tanto, el problema es encontrar el árbol de expansión con lalongitud total mínima de sus ligaduras.
La figura 9.5 ilustra el concepto de árbol de expansión para el problema de Seervada Park. La figura 9.5a no es un árbol de expansión, pues los nodos O, A, B y C no están conectados con los nodos D, E y T. Se necesita una ligadura más para hacer esta conexión. En realidad esta red consiste en dos árboles, uno para cada uno de estos dos conjunto de nodos. Lasligaduras de la figura 9.5b sí se expanden por toda la red (es decir, es una gráfica conexa según la definición de la sección “Terminología de Redes”), pero no es un árbol porque tiene dos ciclos (0-A-B-C-O y D-T-E-D). Tiene demasiadas ligaduras. Como el problema de Seervada Park tiene n = 7 nodos, en la sección anterior se indicó que una red debe tener justo n -1 = 6 ligaduras y ningún ciclo paracalificar como árbol de expansión. Esta condición se logra en la figura 9.5c, por lo que esta red es una solución factible (con una longitud total de 24 millas en las ramas o ligaduras) para el problema del árbol de expansión mínima. (Se verá que esta solución no es óptima, ya que es posible construir un árbol de expansión con sólo 14 millas en sus ramas.)
Algunas aplicaciones.
Seproporciona una lista de algunos tipos importantes de aplicaciones de este problema.
1) Diseño de redes de telecomunicación (redes de fibra óptica, de computadores, telefónica, de televisión por cable, etcétera).
2) Diseño de redes de transporte para minimizar el costo total de proporcionar las ligaduras (vías ferroviarias, carreteras, etc.).
3) Diseño de una red de líneas de transmisión de energíaeléctrica de alto voltaje.
4) Diseño de una red de cableado en equipo eléctrico (como sistemas de cómputo) para minimizar la longitud total de cable
5) Diseño de una red de tuberías para conectar varias localidades.
Un algoritmo
El problema del árbol de expansión mínima se puede resolver de una forma bastante directa, pues ocurre que se trata de uno de los pocos problemas de IO en el que sercodicioso en cada etapa del procedimiento de solución conduce al final a una solución óptima. Así, con el inicio en cualquier nodo, la primera etapa consiste en elegir la rama más corta posible a otro nodo, sin preocuparse del efecto que esta elección pueda tener en las decisiones posteriores. En la segunda etapa se trata de identificar el nodo no-conectado que esté más cerca de cual-quiera de los...
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. En ambos casos 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 problemas involucrantambié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.
El problema del árbol de expansión mínima se puede resumir como sigue.
1) Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta enla red. (Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.)
2) Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos.
3) El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.
Una red con n nodos requiere sólo (n -1)ligaduras para proporcionar una trayectoria entre cada par de nodos. No deben usarse más ligaduras ya que esto aumentaría, sin necesidad, la longitud total de las ligaduras seleccionadas. Las (n -1) ligaduras deben elegirse de tal manera que la red resultante (con sólo las ligaduras seleccionadas) forme un árbol de expansión. Por lo tanto, el problema es encontrar el árbol de expansión con lalongitud total mínima de sus ligaduras.
La figura 9.5 ilustra el concepto de árbol de expansión para el problema de Seervada Park. La figura 9.5a no es un árbol de expansión, pues los nodos O, A, B y C no están conectados con los nodos D, E y T. Se necesita una ligadura más para hacer esta conexión. En realidad esta red consiste en dos árboles, uno para cada uno de estos dos conjunto de nodos. Lasligaduras de la figura 9.5b sí se expanden por toda la red (es decir, es una gráfica conexa según la definición de la sección “Terminología de Redes”), pero no es un árbol porque tiene dos ciclos (0-A-B-C-O y D-T-E-D). Tiene demasiadas ligaduras. Como el problema de Seervada Park tiene n = 7 nodos, en la sección anterior se indicó que una red debe tener justo n -1 = 6 ligaduras y ningún ciclo paracalificar como árbol de expansión. Esta condición se logra en la figura 9.5c, por lo que esta red es una solución factible (con una longitud total de 24 millas en las ramas o ligaduras) para el problema del árbol de expansión mínima. (Se verá que esta solución no es óptima, ya que es posible construir un árbol de expansión con sólo 14 millas en sus ramas.)
Algunas aplicaciones.
Seproporciona una lista de algunos tipos importantes de aplicaciones de este problema.
1) Diseño de redes de telecomunicación (redes de fibra óptica, de computadores, telefónica, de televisión por cable, etcétera).
2) Diseño de redes de transporte para minimizar el costo total de proporcionar las ligaduras (vías ferroviarias, carreteras, etc.).
3) Diseño de una red de líneas de transmisión de energíaeléctrica de alto voltaje.
4) Diseño de una red de cableado en equipo eléctrico (como sistemas de cómputo) para minimizar la longitud total de cable
5) Diseño de una red de tuberías para conectar varias localidades.
Un algoritmo
El problema del árbol de expansión mínima se puede resolver de una forma bastante directa, pues ocurre que se trata de uno de los pocos problemas de IO en el que sercodicioso en cada etapa del procedimiento de solución conduce al final a una solución óptima. Así, con el inicio en cualquier nodo, la primera etapa consiste en elegir la rama más corta posible a otro nodo, sin preocuparse del efecto que esta elección pueda tener en las decisiones posteriores. En la segunda etapa se trata de identificar el nodo no-conectado que esté más cerca de cual-quiera de los...
Leer documento completo
Regístrate para leer el documento completo.