Árbol de expansión de cuello de botella mínimo (MBST)

El árbol de expansión de cuello de botella mínimo en un gráfico no dirigido es un árbol cuyo borde más caro es el mínimo posible. En este artículo, comprenderemos más acerca de cómo identificar un árbol de expansión de cuello de botella mínimo y entenderemos que cada árbol de expansión mínimo es un árbol de expansión de cuello de botella mínimo.

Un árbol de expansión mínimo es completamente diferente de un árbol de expansión de cuello de botella mínimo. Un cuello de botella en un árbol de expansión es el borde de peso máximo presente en el árbol. Puede haber muchos cuellos de botella para el mismo árbol de expansión. Entendamos esto con los siguientes ejemplos:

Ejemplo 1: Sea G la gráfica dada . Encontremos todos los posibles árboles de expansión posibles.

Para el gráfico G dado, la figura anterior ilustra todos los árboles de expansión para el gráfico dado. Entre los árboles de expansión, los árboles de expansión mínimos son los que tienen un peso de 8. Dado que todos los árboles de expansión tienen el mismo valor para el borde del cuello de botella, todos los árboles de expansión son árboles de expansión de cuello de botella mínimo para el gráfico dado. Pero no todos son árboles de expansión mínimos, ya que el peso total es mínimo (8) solo para los dos árboles de expansión.

Ejemplo 2: Sea G la gráfica dada. Busquemos todos los árboles de expansión posibles.

Para el gráfico G dado, la figura anterior ilustra todos los árboles de expansión para el gráfico dado. Entre los árboles de expansión, el árbol de expansión mínimo es el que tiene peso 3. El cuello de botella mínimo Los árboles de expansión para el gráfico son los árboles con borde de cuello de botella de peso 3. Aquí, el árbol de expansión mínimo es un árbol de expansión de cuello de botella mínimo, pero no todos los cuellos de botella mínimos. Los árboles de expansión no son árboles de expansión mínimos.

Demostración de que todo árbol de expansión mínimo es un árbol de expansión de cuello de botella mínimo: supongamos que T es el árbol de expansión mínimo de un grafo G(V, E) y T’ es su árbol de expansión de cuello de botella mínimo. Considere el borde de peso máximo de T y T’ (borde de cuello de botella). Entonces, hay tres casos posibles:

1. Caso 1: Si ambas aristas resultan ser la misma arista. Entonces, T es un árbol de expansión de cuello de botella mínimo (es decir, cada MST es un MBST, debido a la elección arbitraria de G.
2. Caso 2: si ambos bordes resultan ser bordes diferentes, no puede suceder que el peso de T’ sea mayor que el borde ponderado máximo en T, ya que T’ es un MBST.
3. Caso 3: Supongamos que T tiene un borde de peso máximo (p, q) cuyo peso es mayor que el peso del árbol de expansión del cuello de botella T’. Después:
   • Sea X el subconjunto de los vértices de V en T a los que se puede llegar desde p sin pasar por q.
   • Análogamente, sea Y el subconjunto de vértices de V en T a los que se puede llegar desde q sin pasar por p.
   • Dado que G es un gráfico conexo, debe haber un borde de corte entre X e Y. El único borde que se puede agregar a través de este corte es el de peso mínimo.
   • Pero, por la forma en que se definen X e Y, sabemos que (p, q) es el único borde de corte posible de peso mínimo.
   • Sin embargo, tenemos un árbol generador de cuello de botella T’ con menor peso que w(p, q).
   • Esto es una contradicción porque un árbol de expansión de cuello de botella en sí mismo es un árbol de expansión y debe tener un borde a través de este corte. Y será de menor peso que w(p, q).
   • Por lo tanto, la suposición es incorrecta y la única posibilidad es que el borde de peso máximo de T y T’ (borde de cuello de botella) sean iguales.
   • Entonces, por el Caso 1, la prueba se completó y, por lo tanto, se demostró que cada MST es un MBST.