En este tutorial, aprenderá sobre el árbol de expansión y el árbol de expansión mínimo con la ayuda de ejemplos y figuras.
Antes de aprender sobre los árboles de expansión, debemos comprender dos gráficos: gráficos no dirigidos y gráficos conectados.
Un gráfico no dirigido es un gráfico en el que los bordes no apuntan en ninguna dirección (es decir, los bordes son bidireccionales).
Gráfico no dirigido
Un gráfico conectado es un gráfico en el que siempre hay un camino desde un vértice a cualquier otro vértice.
Gráfico conectado
Árbol de expansión
Un árbol de expansión es un sub-gráfico de un gráfico conectado no dirigido, que incluye todos los vértices del gráfico con un número mínimo posible de aristas. Si se pierde un vértice, no es un árbol de expansión.
Los bordes pueden tener o no un peso asignado.
El número total de árboles de expansión con nvértices que se pueden crear a partir de un gráfico completo es igual a .n(n-2)
Si es así n = 4, el número máximo de árboles de expansión posibles es igual a . Por lo tanto, se pueden formar 16 árboles de expansión a partir de un gráfico completo con 4 vértices.44-2 = 16
Ejemplo de un árbol de expansión
Entendamos el árbol de expansión con ejemplos a continuación:
Sea el gráfico original:
Gráfico normal
Algunos de los posibles árboles de expansión que se pueden crear a partir del gráfico anterior son:
Un árbol de 
expansión 
Un árbol de 
expansión 
Un árbol de 
expansión Un árbol de expansión Un árbol de expansión Un árbol de expansión
Árbol de expansión mínimo
Un árbol de expansión mínimo es un árbol de expansión en el que la suma del peso de los bordes es la mínima posible.
Ejemplo de un árbol de expansión
Entendamos la definición anterior con la ayuda del siguiente ejemplo.
El gráfico inicial es:
Gráfico ponderado
Los posibles árboles de expansión del gráfico anterior son:
Árbol de expansión mínimo - 1 
Árbol de expansión mínimo - 2 
Árbol de expansión mínimo - 3 
Árbol de expansión mínimo - 4
El árbol de expansión mínimo de los árboles de expansión anteriores es:
Árbol de expansión mínimo
El árbol de expansión mínimo de un gráfico se encuentra utilizando los siguientes algoritmos:
- Algoritmo de Prim
- Algoritmo de Kruskal
Aplicaciones de árbol de expansión
- Protocolo de enrutamiento de red informática
- Análisis de conglomerados
- Planificación de la red civil
Aplicaciones mínimas del árbol de expansión
- Para encontrar caminos en el mapa
- Diseñar redes como redes de telecomunicaciones, redes de abastecimiento de agua y redes eléctricas.
