Propiedades del árbol de expansión mínimo (MST)

Para un gráfico conectado y no dirigido , un árbol de expansión de ese gráfico es un subgrafo que es un árbol y conecta todos los vértices entre sí. Un solo gráfico puede tener varios árboles de expansión. Un árbol de expansión mínimo (MST) o árbol de expansión de peso mínimo para un gráfico ponderado, conectado y no dirigido es un árbol de expansión que tiene un peso menor o igual que el peso de todos los demás árboles de expansión posibles. El peso de un árbol de expansión es la suma de los pesos asignados a cada borde del árbol de expansión.

Condiciones necesarias para el árbol de expansión mínimo:

1. No debe formar un ciclo, es decir, ningún borde se recorre dos veces.
2. No debe haber otro árbol de expansión con menor peso.

En este artículo, discutiremos las propiedades de MST :

Multiplicidad posible :

Si G(V, E) es un gráfico , entonces cada árbol de expansión del gráfico G consta de (V – 1) aristas, donde V es el número de vértices del gráfico y E es el número de aristas del gráfico. Entonces, (E – V + 1) los bordes no son parte del árbol de expansión. Puede haber varios árboles de expansión mínimos del mismo peso. Si todos los pesos de los bordes de un gráfico son iguales, entonces todos los árboles de expansión de ese gráfico son mínimos.

Considere un gráfico completo de tres vértices y todos los pesos de los bordes son los mismos, entonces habrá tres árboles de expansión (que también son mínimos) de la misma longitud de ruta. A continuación se muestra la imagen para ilustrar lo mismo:

Cada uno de los árboles de expansión tiene el mismo peso igual a 2 .

Propiedad de corte :

Para cualquier corte C del gráfico, si el peso de una arista E en el conjunto de cortes de C es estrictamente menor que los pesos de todos los demás bordes del conjunto de cortes de C , entonces este borde pertenece a todos los MST de la gráfico _ A continuación se muestra la imagen para ilustrar lo mismo:

Propiedad del ciclo :

Para cualquier ciclo C en el gráfico, si el peso de un borde E de C es mayor que los pesos individuales de todos los demás bordes de C , entonces este borde no puede pertenecer a un MST . En la figura anterior, en el ciclo ABD , la arista BD no puede estar presente en ningún árbol de expansión mínimo porque tiene el mayor peso entre todas las aristas del ciclo.

Singularidad :

Si cada borde tiene un peso distinto, entonces habrá solo uno, es decir, un árbol de expansión mínimo único.

Subgráfico de costo mínimo

Para todos los árboles de expansión posibles, el árbol de expansión mínimo debe tener el peso mínimo posible. Sin embargo, pueden existir más spanning con el mismo peso que el árbol de expansión mínimo, y todos ellos también pueden considerarse como árbol de expansión mínimo.

• Borde de costo mínimo: si el borde de costo mínimo de un gráfico es único, este borde se incluye en cualquier MST. Por ejemplo, en la figura anterior, el borde AB (de menor peso) siempre se incluye en MST.
• Si se agrega un nuevo borde al árbol de expansión, se volverá cíclico porque cada árbol de expansión es mínimamente acíclico. En la figura anterior, si se agrega el borde AD o BC al MST resultante, entonces formará un ciclo.
• El árbol de expansión está mínimamente conectado, es decir, si se elimina cualquier borde del árbol de expansión, se desconectará el gráfico. En la figura anterior, si se elimina cualquier borde del MST resultante, se desconectará el gráfico.

Algoritmos para encontrar el árbol de expansión mínimo (MST): –

1. Algoritmo de Prim
2. Algoritmo de Kruskal