Preciso da sua ajuda para provar o seguinte:
G=(V,E) é um gráfico conectado não direcionado com pesos não negativos nas bordas. Deixei T ser um MST de G e T" ser uma árvore de abrangência G (não um mínimo), por isso sustenta que Weight(T") > Weight(T). Prove que o peso da borda mais quente do T" não é menor que o peso da borda mais pesada T.
Não sei bem como abordar isso, se deixarmos e(u,v) - heaviest edge on T e e"(u",v") - heaviest edge on T" e se olharmos para o corte definido por (u,u") podemos usar o algoritmo de Kruskal e mostrar que e" não foi escolhido para estar em T ou algo nessa direção ...
Obrigado,
Respostas:
4 para resposta № 1Suponha o contrário - existe uma ponderadagráfico não direcionado com uma árvore de abrangência mínima T e uma árvore de abrangência T ", de modo que a borda mais pesada de T seja mais pesada que a borda mais pesada de T", ou seja, a borda mais pesada de T é mais pesada que cada borda em T ". Considere o corte induzido pela exclusão da aresta mais pesada h de T. Como T "está conectado, alguma aresta em T" cruza esse corte. Se adicionarmos essa aresta a T - h, obteremos uma árvore de abrangência mais leve que T, que é uma árvore de abrangência mínima. Contradição.
1 para resposta № 2
Eu tomaria outra direção. Para simplificar, deixe todos os pesos das arestas serem distintos, para que o MST seja único. Considere a aresta mais pesada e no MST, e a maneira como o algoritmo Kruskal constrói esse MST. Acontece que a última aresta adicionada é a aresta mais pesada no MST resultante.
Agora observe a situação antes de adicionar a última borda. Temos uma floresta composta por duas árvores. Como estamos seguindo o algoritmo Kruskal, atualmente não há maneiras mais baratas do que e para conectar essas duas árvores. Portanto, qualquer borda entre eles em qualquer outra árvore de abrangência tem peso pelo menos tão grande quanto e tem.
Bordas de peso igual requerem algum cuidado, ou talvez uma idéia inteligente, para serem manuseadas adequadamente.