Problema com arvore geradora

SUMÁRIO
1.0 – Introdução.............................................................................................................2
2.0 –. Fundamentação Teórica .....................................................................................3
2.1 – Problema da Árvore Geradora Mínima ................................................................4
2.1.1 – Árvore ....................................................................................................4
2.1.2 – Geradora ................................................................................................5
2.1.3 – Mínima ...................................................................................................6
3.0 – Algoritmo para o Problema da AGM ...................................................................7
3.1 – Algoritmo de Kruskal ...........................................................................................8
3.2 – Algoritmo de Prim ................................................................................................8
4.0 – Problema da AGM-MO ........................................................................................9
Conclusão.....................................................................................................................12
Referencial Teórico.....................................................................................................13

1.0 – Introdução

2.0 –. Fundamentação Teórica
Uma empresa possui escritórios espalhados pela cidade e pretende construir uma linha privada de comunicação entre esses escritórios. Para cada par de escritórios v e w pode ser possível ou não uma ligação direta de comunicação (cabos físicos ligando os dois escritórios). Nos casos em que é possível, admita- se conhecido o custo (positivo) cvw da efetiva construção dessa linha de comunicação. A empresa pretende identificar quais são as linhas de