Neste tutorial, você aprenderá sobre a árvore geradora e a árvore geradora mínima com a ajuda de exemplos e figuras.
Antes de aprendermos sobre árvores geradoras, precisamos entender dois gráficos: gráficos não direcionados e gráficos conectados.
Um gráfico não direcionado é um gráfico no qual as arestas não apontam em nenhuma direção (ou seja, as arestas são bidirecionais).
Gráfico não direcionado
Um grafo conectado é um grafo no qual sempre há um caminho de um vértice para qualquer outro vértice.
Gráfico Conectado
Spanning tree
Uma árvore geradora é um subgráfico de um grafo conectado não direcionado, que inclui todos os vértices do grafo com um número mínimo possível de arestas. Se um vértice estiver perdido, então não é uma árvore estendida.
As arestas podem ou não ter pesos atribuídos a elas.
O número total de árvores abrangentes com nvértices que podem ser criadas a partir de um gráfico completo é igual a .n(n-2)
Se tivermos n = 4, o número máximo de árvores abrangentes possíveis é igual a . Assim, 16 árvores abrangentes podem ser formadas a partir de um grafo completo com 4 vértices.44-2 = 16
Exemplo de uma árvore de expansão
Vamos entender a árvore de abrangência com os exemplos abaixo:
Deixe o gráfico original ser:
Gráfico normal
Algumas das árvores abrangentes possíveis que podem ser criadas a partir do gráfico acima são:
A spanning tree 
Uma spanning tree 
Uma spanning tree 
Uma spanning tree 
Uma spanning tree 
Uma spanning tree
Árvore de alcance mínimo
Uma árvore geradora mínima é uma árvore geradora na qual a soma do peso das arestas é a menor possível.
Exemplo de uma árvore de expansão
Vamos entender a definição acima com a ajuda do exemplo abaixo.
O gráfico inicial é:
Gráfico ponderado
As árvores abrangentes possíveis do gráfico acima são:
Spanning tree mínimo - 1 
Spanning tree mínimo - 2 
Spanning tree 
mínimo - 3 Spanning tree mínimo - 4
A árvore de abrangência mínima das árvores de abrangência acima é:
Árvore de abrangência mínima
A árvore de abrangência mínima de um gráfico é encontrada usando os seguintes algoritmos:
- Algoritmo de Prim
- Algoritmo de Kruskal
Aplicativos de Spanning Tree
- Protocolo de roteamento de rede de computadores
- Análise de Cluster
- Planejamento da Rede Civil
Aplicativos de árvore de abrangência mínima
- Para encontrar caminhos no mapa
- Projetar redes como redes de telecomunicações, redes de abastecimento de água e redes elétricas.
