Árvores geradoras mínimas

Questões-guia:

1. O que é uma árvore geradora mínima?  O que pode ser aproveitado da teoria sobre árvores geradoras mínimas se estivermos procurando uma árvore geradora máxima?
2. Como funciona o algoritmo genérico?  Como encontrar uma aresta segura?
3. Para que serve a estrutura de union-find?  Como funciona?
4. Como funciona o algoritmo de Kruskal?  Qual é sua complexidade?  Dá para pará-lo antes?  Isto modifica sua complexidade de pior caso?  Você pararia antes?
5. Para que servem heaps binários?  Como funcionam?  Que outros algoritmos os usam?
6. Como funciona o algoritmo de Prim?  Qual é sua complexidade com heaps binários?  Por que não aparece uma chamada de DECREASE-KEY nele?
7. O que poderia ser usado em lugar de heaps binários no algoritmo de Prim?  Como isto afetaria a complexidade?  Esta solução afetaria outros algoritmos, p.ex., os citados na questão 5?

Exercícios:

1. Ache uma árvore geradora mínima com o LEMON no exemplo usado no Cormen na seção 23.2.  Dica: use a função kruskal.
2. Exercício 23.1-11 do Cormen.
3. Exercício 23.2-4 do Cormen, só a primeira pergunta.
4. Exercício 23.2-5 do Cormen, só a primeira pergunta.