algorithm - prim - ¿En qué se diferencia un árbol de expansión de cuello de botella mínimo de un árbol de expansión mínimo?

minimum spanning tree wiki (2)

Antes de responder a su pregunta, permítame definir algunos de los términos que se usan aquí ...

1) Árbol de expansión: Árbol de expansión de un gráfico dado es un árbol que cubre todos los vértices de ese gráfico.

2) Árbol de expansión mínimo (MST): MST de un gráfico dado es un árbol de expansión cuya longitud es mínima entre todos los posibles árboles de expansión de ese gráfico. Más claramente, para un gráfico dado, enumere todos los posibles árboles de expansión (que pueden ser muy grandes) y elija aquel cuya suma de pesos de borde sea mínima.

3) Árbol de expansión de cuello de botella mínimo (MBST): MBST de un gráfico dado es un árbol de expansión cuyo peso máximo de borde es mínimo entre todos los árboles de expansión posibles. Más claramente, para un gráfico dado, enumere todos los árboles de expansión posibles y el peso máximo del borde para cada uno de los árboles de expansión. Entre estos, elija el árbol de expansión cuyo máximo peso de borde es mínimo.

Ahora echemos un vistazo a la siguiente imagen con un gráfico de cuatro nodos ...

Graph-A es el gráfico original dado. Si enumero todos los árboles de expansión posibles para este gráfico y elijo la suma de pesos de borde que es mínima, obtendré el Gráfico-B. Entonces Graph-B es el árbol de expansión mínimo (MST). Tenga en cuenta que su peso total es 1 + 2 + 3 = 6.

Ahora, si selecciono un árbol de expansión cuyo máximo peso de borde es mínimo (es decir MBST), entonces puedo terminar recogiendo ya sea Graph-B (o) Graph-C. Tenga en cuenta que estos dos árboles tienen un peso máximo de borde 3, que es el mínimo entre todos los árboles de expansión posibles.

Desde el Gráfico-B y el Gráfico-C, está claro que aunque el Gráfico-C es un MBST, no es MST. Debido a que su peso total es 1 + 3 + 3 = 7, que es mayor que el peso total de MST dibujado en el Gráfico-B (es decir, 6).

Entonces MBST no necesariamente es un MST de un gráfico dado. Pero el MST debe ser MBST.

Un árbol de expansión de cuello de botella mínimo de un gráfico ponderado G es un árbol de expansión de G tal que minimiza el peso máximo de cualquier borde en el árbol de expansión. Un MBST no es necesariamente un MST (árbol de expansión mínimo).

Por favor dé un ejemplo donde estas declaraciones tengan sentido.

Mira el ejemplo de MST en Wikipedia para referencia:

Un cuello de botella en un árbol de expansión es un borde de peso máximo en ese árbol. Puede haber varios cuellos de botella (todos del mismo peso, por supuesto) en un árbol de expansión. En Wikipedia MST hay dos cuellos de botella de peso 8.

Ahora, tome un árbol de expansión mínimo de un gráfico dado (puede haber varios MST, todos con el mismo peso de borde total, por supuesto) y llame al peso de borde máximo B. En nuestro ejemplo B = 8.

Cualquier árbol de expansión que también tenga un cuello de botella de B = 8 es un MBST. Pero puede no ser un MST (porque el peso total del borde es mayor que el mejor posible).

Por lo tanto, tome el MST de Wikipedia y modifíquelo (agregue / elimine algunos bordes) para que

sigue siendo un árbol de expansión, y
todavía no usa ningún peso> 8, aún
aumentas el peso total del borde

Por ejemplo, cambie solo el subárbol "a la izquierda" de Wikipedia MST (que consta de los pesos {2, 2, 3}) a {2, 3, 6}, aumentando así el peso total del borde en 4 sin cambiar el cuello de botella de 8. Bingo, has creado un MBST que no es un MST.