¿Hay un MST de G que no contenga el límite máximo ponderado?
Puede haber, pero no tiene que ser así. Considere un gráfico de 4 vértice de la siguiente manera:
[A]--{2}--[B]
| |
| |
{1} {3}
| |
| |
[C]-{50}--[D]
El árbol de expansión mínima consiste en el conjunto de aristas {CA, AB, BD}. El peso máximo del borde es 50, a lo largo de {CD}, pero no es parte del MST. Pero si G ya fuera igual a su propio MST, entonces obviamente tendría con su propio límite máximo.
¿cada MST de G contiene el borde ponderado mínimo?
Sí. Los MST tienen una propiedad de corte . Un corte es simplemente una partición de los vértices del gráfico en dos conjuntos disjuntos. Para cualquier corte que pueda hacer, si el peso de un borde en ese corte es más pequeño que los pesos de los otros bordes en el corte, entonces este borde pertenece a todos los MST en el gráfico. Debido a que garantizaste que los pesos de los bordes son distintos, también has garantizado que hay un borde que es más pequeño que todos los otros bordes.
Además, estoy más agradecido si alguien puede dar una pista de las cosas clave que debe tener en cuenta cuando se trata de tales preguntas MST.
Lo mejor que puede hacer es razonar sobre las cosas usando las propiedades de los MST en general, y tratar de construir contraejemplos específicos que, en su opinión, probarán su caso. Di un ejemplo de cada línea de razonamiento anterior. Debido a las propiedades de corte y ciclo, siempre puede determinar exactamente qué bordes se encuentran en un MST, por lo que puede probar sistemáticamente cada borde para determinar si está o no en el MST.