Ejemplo de gráfico con dos MSP diferentes mediante el Algoritmo de Prim?

Question

El otro día hablaba del algoritmo de Prim y del algoritmo de Kruskal para encontrar árboles de extensión mínima y empezamos a preguntarnos sobre las condiciones en las que serían posibles múltiples MSP.

Rápidamente se nos ocurrió y demostramos el hecho (aparentemente famoso) de que el etiquetado único de los bordes conduce a un MSP único.

Sin embargo, nos preguntamos si era posible crear un grafo en el que el algoritmo de Prim creara al menos dos MSP diferentes si partía de vértices distintos con la condición añadida de que en ningún momento se viera obligado a hacer "una elección", es decir, a elegir entre dos aristas disponibles que tuvieran el mismo peso.

Creíamos que no, pero no podíamos demostrarlo ni presentar un contraejemplo.

Answer 1

No: la única manera en que el algoritmo de Prim puede terminar encontrando múltiples árboles de extensión mínima es si tiene que romper un empate entre dos aristas con igual peso.

Para ver esto, dejemos $G$ sea cualquier gráfico ponderado (conectado). Sea $G'$ sea una modificación de $G$ en el que añadimos un pequeño desplazamiento $\epsilon_i$ al peso de la $i^{\text{th}}$ borde. Cada $\epsilon_i$ debe ser mucho menor que la diferencia entre dos pesos de arista distintos, y el $\epsilon_i$ deberían ser todos diferentes.

Con esta construcción, $G'$ tiene un único árbol de expansión mínima, ya que todos los pesos de sus aristas son distintos. Por lo tanto, el algoritmo de Prim sólo puede producir una salida posible para $G'$ .

Ahora ejecuta el algoritmo de Prim en paralelo en $G$ y $G'$ partiendo del mismo vértice. Una de dos cosas debe suceder:

1. El árbol de expansión encontrado por el algoritmo de Prim es el mismo para ambos grafos. Si esto ocurre a partir de cada vértice, significa que el algoritmo de Prim siempre encuentra el mismo árbol de expansión para $G$ - ya que ciertamente siempre encuentra el mismo árbol de expansión para $G'$ .

2. Partiendo de algún vértice, el árbol de expansión encontrado para $G$ es diferente del árbol de expansión encontrado para $G'$ . Para que esto ocurra, debe haber un paso en el que el $\epsilon_i$ ajustes en $G'$ ha marcado la diferencia. Como los ajustes son mucho más pequeños que la diferencia entre los pesos de los bordes distintos, sólo pueden marcar la diferencia cuando, en $G$ elegimos entre dos aristas de igual peso.

Para decirlo de otra manera: si se es coherente con la forma de romper los vínculos entre los bordes (que es lo que el $\epsilon_i$ ) entonces se obtiene el mismo árbol de expansión sin importar dónde se comience.