Mostrar que hay un mínimo árbol de expansión si todos los bordes tienen diferentes costos

Question

Mostrar que hay una única mínimo spanning tree (MST) en el caso de los bordes pesos son pares diferentes $(w(e)\neq w(f) \text{ for } e\neq f)$.

Pensé que la prueba se puede hacer, por ejemplo, por la contradicción, diciendo que tenemos $2$ diferentes MST lo que significa que en algún lugar fue posible elegir entre más bordes, por lo $w(e) = w(f)$$e\neq f$, contradicción. Al parecer, esto no es correcto.

¿Cómo podría usted demostrar que un grafo tiene un único MST si todas las aristas tienen distintos pesos?

Answer 1

Si $T_1$ $T_2$ son distintos árboles de expansión mínimos, y luego considerar la arista de peso mínimo que está contenida en uno solo de $T_1$ o $T_2$. Sin pérdida de generalidad, esta ventaja sólo aparece en $T_1$, y podemos llamar a $e_1$.

A continuación, $T_2 \cup \{ e_1 \}$ contiene un ciclo, y por lo tanto uno de los bordes de este ciclo, llame a $e_2$, no es en $T_1$.

Tenga en cuenta que $w ( e_1 ) < w ( e_2 )$ $T = T_2 \cup \{ e_1 \} \setminus \{ e_2 \}$ es un árbol de expansión. El peso total de $T$ es menor que el peso total de $T_2$, pero esto es una contradicción, ya que hemos supuesto que el $T_2$ es un mínimo árbol de expansión.

Answer 2

Una prueba de uso de propiedad ciclo:

Deje $G=(V,E)$ el gráfico original.

Supongamos que hay dos distintos Ha $T_1=(V,E_1)$$T_2=(V,E_2)$. Desde $T_1$ $T_2$ son distintos y tienen el mismo número de aristas, los conjuntos de $E_1-E_2$ $E_2-E_1$ no están vacías, por lo que $ \existe e\en E_1-E_2$.

Desde $e\notin E_2$, la adición de a $T_2$ crea un ciclo. Por ciclo de propiedad de los más caros del borde de este ciclo ( $e'$ ) no pertenecen a ninguna de MST. Pero

Si $e'=e$ $e'\in E_1$ (debido a $e\in E_1-E_2$)
Si $e'\neq e$ $e'\in E_2$

Ambos casos se contradice con el hecho de que $e'$ no está en ninguna MST.