Acho que encontrei um contraexemplo para a questão 6:
Escolha um grafo que é apenas um ciclo e seja T a árvore geradora que não contém a aresta mais barata. A aresta mais barata (a que sobrou) vai ser escolhida em todos os passos do algoritmo e assim não é sobra uma árvore geradora no final.
Um exemplo concreto.:
Vértices:
A B C
Arestas:
A-B, custo 2
B-C, custo 2
A-C, custo 1
Arvore geradora escolhida:
A-B-C
O algoritmo:
A-B -> corte = ({A},{B C}) -> substituir por A-C
B-C -> corte = ({A B},{C}) -> substituir por A-C
A mesma aresta é escolhida nas duas vezes e por isso não obtemos uma árvore.
Não sei se entendi direito. Mas a questão e que iteramos o processo com a nova árvore.
No seu caso, você começa com a árvore A-B-C e troca
A-B por A-C, ficando com a árvore B-C-A. Agora a única
aresta fora da árvore não é a mais barata (no corte em que retiramos B-C, tem o mesmo custo que B-C e no corte que retiramos A-C é mais cara do A-C).
No seu caso, você começa com a árvore A-B-C e troca
A-B por A-C, ficando com a árvore B-C-A. Agora a única
aresta fora da árvore não é a mais barata (no corte em que retiramos B-C, tem o mesmo custo que B-C e no corte que retiramos A-C é mais cara do A-C).
Na questão 18, o que é a distância entre dois conjuntos de vértices?
Na questão 9, é Find em tempo constante e Union em log(V) mesmo ou é o contrário?
É isso mesmo.