arvore geradora minima

Problema da Árvore
Geradora Mínima
The Minimum Spanning Tree
Problem
Fernando Nogueira

Árvore Geradora Mínima

1

O Problema da Árvore Geradora Mínima (The Minimum Spanning
Tree Problem)
Considere uma rede não-direcionada (grafo), conectada e associado a cada arco uma distância (custo, tempo, etc) nãonegativa. O objetivo é encontrar o caminho mais curto de tal maneira que os arcos forneçam um caminho entre todos os pares de nós.
Exemplos de Aplicações:
1)Projeto de redes de telecomunicação (redes de computadores, redes de fibra-ótica, redes de telefonia, redes de televisão a cabo, etc). 2)Projeto de rodovias, ferrovias, etc.
3)Projeto de redes de transmissão de energia.
Fernando Nogueira

Árvore Geradora Mínima

2

Conceito Fundamental Envolvido
Uma rede com n nós requer somente n-1 arcos para fornecer um caminho entre cada par de nós.
Os n-1 arcos devem formar uma Árvore Geradora. O problema então é encontrar a Árvore Geradora com o menor comprimento total.
O problema parte do princípio que existe apenas os nós de uma rede. Os arcos são “arcos potenciais”.

Fernando Nogueira

Árvore Geradora Mínima

3

Exemplo 1 (contra-exemplo)

A figura acima não é uma Árvore Geradora porque os nós O, A,
B e C não estão conectados aos nós D, E e T. Aqui existe, 2
Árvores Geradoras.

Fernando Nogueira

Árvore Geradora Mínima

4

Exemplo 2 (contra-exemplo)

A figura acima gera uma rede, porém não é uma árvore porque existe 2 ciclos (O-A-B-C e D-E-T).

Fernando Nogueira

Árvore Geradora Mínima

5

Exemplo 3

A figura acima é uma Árvore Geradora (não há ciclos, todo par de nós está conectado e existe 6 (n-1) arcos para 7 (n) nós. Está rede é uma solução viável, porém não é ótima (não é uma Árvore
Geradora Mínima). Existe outra configuração desta rede que fornece menor distância total.
Fernando Nogueira

Árvore Geradora Mínima

6

Algoritmo
1) Selecionar qualquer nó e conectá-lo (isto é, adicionar