Explicação

Árvores são grafos conexos que não podem ter circuitos. Em particular, estes grafos não podem ter arestas paralelas nem lacetes.

Tendo um grafo $G$ , chamam-se árvores abrangentes a subgrafos de $G$ que sejam árvores e contenham todos os seus vértices.

Exemplo


Grafo 1	Grafo 2	Grafo 3	Grafo 4

O grafo 1 acima representa uma árvore. Já os grafos 3 e 4 são árvores abrangentes do grafo 2.

Para encontrar todas as árvores abrangentes podes utilizar o método de árvore de probabilidades.

Exemplo

Ao utilizar este método, desenha-se num grafo os possíveis caminhos a seguir. Posteriormente, aplica-se o mesmo processo iniciando em cada um dos vértices restantes.

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Modelos de grafos: Árvores e algoritmo de Krustal

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Modelos de grafos: Árvores e algoritmo de Krustal

Nota que no grafo da esquerda, começando em $\text{A}$ , tens três hipóteses de vértices adjacentes. Escolhendo um deles, ficas com dois restantes e depois apenas um. Assim, o número de árvores abrangentes começando em $A$ é ${3\times2\times1=6}$ , como representado na árvore de probabilidades à direita. Como podes começar em $4$ vértices diferentes, o número total de árvores abrangentes é de $6\times4=24$ .

Caso o grafo seja uma árvore com peso atribuído às suas arestas, a árvore abrangente cuja soma dos pesos das arestas seja mínima passa a denominar-se árvore abrangente de custo mínimo.

Exemplo


Grafo A	Grafo B

O grafo B é uma árvore abrangente de custo mínimo do grafo A.

Algoritmo de Kruskal

Tendo um grafo ponderado $G$ como referência, o algoritmo de Kruskal permite construir uma árvore abrangente de custo mínimo. O raciocínio é que deves selecionar arestas por ordem crescente do seu peso, sem formar circuitos.

Procedimento

1.	Seleciona a aresta de menor peso;
2.	Seleciona a aresta de menor peso seguinte, verificando que não forma um circuito. Caso isso aconteça, esta é descartada;
3.	Repete ambos os passos até serem visitados todos os vértices. As arestas selecionadas formam a árvore abrangente de custo mínimo.

Nota: Sempre que houver duas ou mais arestas com igual peso, podes selecioná-las por uma ordem ao acaso.

Exemplo

Para se obter o grafo B, selecionou-se a aresta de menor peso, $\text{HJ}$ , de peso $2$ , seguida de $\text{KI}$ , cujo peso é $5$ . Por fim, escolheu-se a aresta $\text{HK}$ , com peso $7$ , verificando-se que todos os vértices tinham sido visitados.

Assim, a árvore abrangente de custo mínimo tem peso total de $2+7+5=14$ .