Estructura de datos y algoritmos: árbol de expansión

Un árbol de expansión es un subconjunto del Gráfico G, que tiene todos los vértices cubiertos con el mínimo número posible de aristas. Por lo tanto, un árbol de expansión no tiene ciclos y no se puede desconectar.

Con esta definición, podemos llegar a la conclusión de que todo Gráfico G conectado y no dirigido tiene al menos un árbol de expansión. Un gráfico desconectado no tiene ningún árbol de expansión, ya que no se puede expandir a todos sus vértices.

Encontramos tres árboles de expansión en un gráfico completo. Un gráfico completo no dirigido puede tener un máximonn-2 número de árboles de expansión, donde nes el número de nodos. En el ejemplo mencionado anteriormente,n is 3, por lo tanto 33−2 = 3 árboles de expansión son posibles.

Propiedades generales del árbol de expansión

Ahora entendemos que un gráfico puede tener más de un árbol de expansión. A continuación se muestran algunas propiedades del árbol de expansión conectadas al gráfico G:

  • Un gráfico G conectado puede tener más de un árbol de expansión.

  • Todos los árboles de expansión posibles del gráfico G tienen el mismo número de aristas y vértices.

  • El árbol de expansión no tiene ningún ciclo (bucles).

  • Quitar un borde del árbol de expansión hará que el gráfico se desconecte, es decir, el árbol de expansión se minimally connected.

  • Agregar un borde al árbol de expansión creará un circuito o bucle, es decir, el árbol de expansión se maximally acyclic.

Propiedades matemáticas del árbol de expansión

  • El árbol de expansión tiene n-1 bordes, donde n es el número de nodos (vértices).

  • De un gráfico completo, eliminando el máximo e - n + 1 bordes, podemos construir un árbol de expansión.

  • Un gráfico completo puede tener un máximo nn-2 número de árboles de expansión.

Por lo tanto, podemos concluir que los árboles de expansión son un subconjunto del Gráfico G conectado y los gráficos desconectados no tienen árbol de expansión.

Aplicación del árbol de expansión

El árbol de expansión se usa básicamente para encontrar una ruta mínima para conectar todos los nodos en un gráfico. La aplicación común de los árboles de expansión son:

  • Civil Network Planning

  • Computer Network Routing Protocol

  • Cluster Analysis

Entendamos esto con un pequeño ejemplo. Considere la red de la ciudad como un gráfico enorme y ahora planea desplegar líneas telefónicas de tal manera que en líneas mínimas podamos conectarnos a todos los nodos de la ciudad. Aquí es donde entra en escena el árbol de expansión.

Árbol de expansión mínimo (MST)

En un gráfico ponderado, un árbol de expansión mínimo es un árbol de expansión que tiene un peso mínimo que todos los demás árboles de expansión del mismo gráfico. En situaciones del mundo real, este peso se puede medir como distancia, congestión, carga de tráfico o cualquier valor arbitrario indicado en los bordes.

Algoritmo mínimo de árbol de expansión

Aquí aprenderemos sobre los dos algoritmos de árbol de expansión más importantes:

Ambos son algoritmos codiciosos.