Dado un grafo con pesos de borde distinto y un ST no mínimo, existe siempre otro ST de menor peso total que diferencia solamente por un borde

Question

Tengo que demostrar que, si todos los pesos del borde de un gráfico están distintos, dada una expansión árbol $T$ que es no un MST, allí siempre existe un % de árbol abarcador $T'$de menor peso total, % s.t. $T'$diferencia de $T$ sólo por un borde.

Empecé razonamiento de esta pregunta, pero no es útil para mi caso y no puedo pasar.

Answer 1

Considere la posibilidad de un árbol de expansión $E$ y la etiqueta de sus bordes $e_1$, $\ldots$,$e_n$. Considere ahora un árbol de expansión $F$. Entonces existe un etiquetado de los bordes de $F$ $\ $ $f_1$, $\ldots$, $f_n$ de modo que los siguientes son todavía árboles de expansión (uso un intercambio lema como para dos bases de un espacio vectorial):

$$(e_1, e_2, \ldots, e_{n-1},e_n) \\ (e_1, e_2, \ldots, e_{n-1},f_n)\\ (e_1, e_2, \ldots, f_{n-1}, f_n)\\ \ldots \\ (e_1, f_2, \ldots, f_{n-1}, f_n)\\ (f_1, f_2, \ldots, f_{n-1}, f_n)$$

Supongamos ahora que $E$ se obtiene mediante el algoritmo voraz: $e_1$ es de mínimo peso, $e_2$ es de un mínimo de peso para que $e_1$, $e_2$ no forman ciclos, $e_3$ es de un mínimo de peso para que $e_1$, $e_2$, $e_3$ no forman ciclos, y así sucesivamente, hasta el $e_n$. A partir de lo anterior, podemos concluir que $w(e_i) \le w(f_i)$ todos los $i$. Desde $F$ es arbitrario, llegamos a la conclusión de que $E$ es un mínimo de árbol.

Supongamos ahora que $F$ sí no es un mínimo de árbol. Luego de algunos $i$ tenemos una desigualdad estricta $w(e_i) < w(f_i)$. Deje $i$ el más pequeño índice para que esto suceda. Supongamos ahora que todos los bordes tienen pesos diferentes. Entonces tenemos $e_1= f_1$, $\ldots$,$e_{i-1} =f_{i-1}$. Por lo tanto el árbol de $(e_1, \ldots, e_{i-1}, f_{i}, \ldots, f_n)$ $F$ y el árbol de $(e_1, \ldots, e_{i-1}, e_i, f_{i+1}, \ldots, f_n)$ es obtenida a través de ella mediante el intercambio de la orilla $e_i$ con un borde de mayor peso $f_i$.