Sea G sea un árbol de mínimo alcance de un grafo completo. Sea e sea la arista de máximo peso en G . Me gustaría probar que dado cualquier otro árbol de expansión G′ de este gráfico, siendo j la arista de peso máximo de G′ entonces w(e)≤w(j) .
Realmente no sé si esto es cierto, y no se me ocurre ningún contraejemplo que demuestre lo contrario.
¿Alguna sugerencia?
Lo que hay que tener en cuenta es la propiedad de corte del problema del árbol de expansión mínima (MST), es decir, cualquier arista {x,y} en un MST tiene un peso al menos tan pequeño como la arista con menor peso en el corte que separa x y y . Esto puede demostrarse fácilmente por contradicción.
En cualquier corte que incluya el borde e (es decir, separa sus dos vértices adyacentes), sabemos que e debe ser una arista con peso mínimo en este corte.
Cualquier árbol de expansión G′ debe contener al menos una arista en este corte.
Sea e′ sea un borde de este tipo. Sabemos que w(e′)≥w(e) También sabemos que w(j)≥w(e′) Así que.., w(j)≥w(e′)≥w(e)
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
