Arbol De Expancion Minima

Universidad Católica de Honduras
-------------------------------------------------
“Nuestra Señora Reina de la Paz”

“Árbol de Expansión Mínima”
Investigación de Operaciones I





Tegucigalpa, M. D. C. 4 de diciembre de 2010.
Índice
* Introducción Pág.3
* Objetivos Pág.4
* HistoriaPág.5
* Concepto de árbol y otros conceptos Pág.5
* Generalidades Pág.6
* Pasos para encontrar un árbol de expansión mínima Pág.7
* Métodos.Pág.8
* Conclusiones Pág. 17
* Anexos Pág. 19
* Bibliografía Pág.21

Introducción

Los árboles de expansión son útiles para difundir y recogerinformación de control en las redes o enrutamientos. Desde varias décadas atrás, se ha planteado diferentes métodos para la solución del problema del Árbol de Expansión Mínima (AEM), conocido también como Mínimum Spanning Tree (en inglés). El problema de AEM se clasifica como un problema de optimización, cuya finalidad es encontrar un árbol de expansión mínima que incluya todos los posiblespuntos y proporcione la manera más optima de incluirlos. Dichos puntos son lugares adonde es necesario llegar y existen varias opciones para llegar a todos.



Objetivos
Objetivo General: Estudiar el algoritmo árbol de expansión mínima.

Objetivos Específicos:
* Narrar brevemente la historia del Árbol de Expansión Mínima.
* Plantear las generalidades del Árbol de ExpansiónMínima.
* Determinar los requisitos para que se presente un problema de Árbol de Expansión Mínima.
* Explicar los métodos mediante los cuales se puede resolver los problemas correspondientes al tema.
* Redactar una conclusión acerca de los métodos disponibles para la solución de un Árbol de Expansión Mínima.

Árbol de Expansión Mínima o Modelo de Minimización de Redes
A. Historia:El Árbol de Expansión Mínima (MST, por sus siglas en ingles) tiene una historia venerable por su aplicación de optimización combinatoria. El MST fue planteado, por primera vez, por Boruvka en 1926. Se dice que Boruvka tuvo que desarrollar este algoritmo durante la electrificación del sur de Moraria, donde él proporcionó una solución para hallar la distribución más económica a través de una redde una línea de energía. Desde entonces, el Árbol de Expansión Mínima ha sido aplicado en numerosos problemas combinatorios tales como: problemas de transporte, diseño de redes de telecomunicaciones, sistemas distribuidos y otros.
Al mismo tiempo, algunos algoritmos fueron desarrollados para su resolución por Prim y Kruskal. El algoritmo de Prim fue creado, en 1930, por el matemático checoVojtech Jarnik. En 1956, el matemático estadunidense Joseph Kruskal desarrollo el algoritmo Kruskal.
B. Concepto de Árbol y otros conceptos:
* Árbol:
Es un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como:
* Un grafo conexo ysin ciclos.
* Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.
* Ciclos:
Se produce cuando a partir de un nodo por un cierto camino se vuelve al mismo nodo por otra ruta.
* Hojas:
En un árbol, a los nodos finales (v3, v5 y v6).
* Árbol de máximo alcance:
Es aquél que obtenemos en un grafo conexo y sin ciclos.
* Árbol de mínima expansión:
Árbol...