preguntas sobre esta prueba del Algoritmo de Prim/Kruskal

Question

¿Podría alguien ayudarme a entender las líneas 5, 6 y 7 de la siguiente prueba del algoritmo codicioso de Prim / Kruskal para encontrar el árbol de expansión mínimo?

Supongamos que cualquiera de los dos algoritmos produce un árbol T. Que exista otro árbol de expansión S con un peso total menor. Sea e una arista de menor peso que se encuentra en T pero no en S.

Si añadimos e a S, obtenemos un ciclo, a partir de las Definiciones Equivalentes para el Árbol.

5 - Este ciclo contiene una arista e' que está en S pero no en T, de lo contrario T no sería un árbol.

6 - Entonces, sustituimos e' en S por e de T, y obtenemos un nuevo árbol de expansión S'.

7 - Del método de construcción de T, se deduce que el peso de e no puede superar al de e'.

Así que el peso total de S' no supera el peso total de T. Además, S' tiene una arista más en común con T que S. Repetimos el procedimiento anterior, y cambiamos repetidamente aristas de S por aristas de T, y cada vez el peso del grafo intermedio no excede al de T. Así, el peso de T no excede al de S, contradiciendo la definición de S. Por lo tanto, T debe ser un árbol de mínima extensión.

Mis preguntas se refieren a los puntos 5, 6 y 7:
5 - Si T tiene e', ¿por qué no es un árbol?
6- ¿Por qué al sustituir e' por e se crea un nuevo árbol de expansión y no un nuevo grafo?
7- ¿Qué asegura que w(e) <= w(e')?

Gracias.

Answer 1

Línea $5$ : Es un ciclo. Si todas sus aristas están en $T$ , lo que significa que $T$ tiene un ciclo, y los árboles no tienen ciclos.

Línea $6$ : Un árbol de expansión es un gráfico.

Línea $7$ : Desde $e'$ no está en $T$ no se añadió porque sus dos vértices ya estaban conectados. Pero si $w(e)\gt w(e')$ entonces esta conexión no pudo haber sido a través de $e$ ya que $e$ no se habría añadido todavía, por lo que el ciclo (menos $e'$ ) constituiría una segunda conexión entre los dos vértices de $e'$ formando así un ciclo, mientras que $T$ es un árbol y no tiene ciclos.

Answer 2

Si T tiene cada e' en el ciclo, entonces en particular es tiene un ciclo. Los árboles no tienen ciclos. Por lo tanto, no sería un árbol.

Es un gráfico nuevo. El gráfico resulta ser un árbol. De hecho, como eligieron la arista de un ciclo, que tiene la propiedad de que cada vértice tiene grado 2, al quitar una arista no se separa ningún vértice. Por lo tanto, es un árbol que se extiende.

La línea 7 alude a la construcción de los árboles. No lo has incluido aquí, pero con toda probabilidad tiene un paso como "De las aristas disponibles E, elige e de mínimo peso y añádela al árbol". Probablemente sea un poco más complicado, pero es algo así.