Matemática Discreta - Árvores Medidas
Uma árvore geradora de um grafo não direcionado conectado $ G $ é uma árvore que inclui, no mínimo, todos os vértices de $ G $. Um gráfico pode ter muitas árvores abrangentes.
Exemplo
Árvore de alcance mínimo
Uma árvore geradora com peso atribuído menor ou igual ao peso de cada árvore geradora possível de um gráfico ponderado, conectado e não direcionado $ G $, é chamada de árvore geradora mínima (MST). O peso de uma árvore geradora é a soma de todos os pesos atribuídos a cada aresta da árvore geradora.
Exemplo
Algoritmo de Kruskal
O algoritmo de Kruskal é um algoritmo guloso que encontra uma árvore de abrangência mínima para um gráfico ponderado conectado. Ele encontra uma árvore daquele gráfico que inclui todos os vértices e o peso total de todas as arestas da árvore é menor ou igual a todas as árvores geradoras possíveis.
Algoritmo
Step 1 - Organize todas as arestas do gráfico $ G (V, E) $ dado em ordem crescente de acordo com seu peso de aresta.
Step 2 - Escolha a menor aresta ponderada do gráfico e verifique se ela forma um ciclo com a árvore geradora formada até o momento.
Step 3 - Se não houver ciclo, inclua esta aresta na árvore de abrangência, caso contrário, descarte-a.
Step 4 - Repita a Etapa 2 e a Etapa 3 até que $ (V-1) $ número de arestas sejam deixadas na árvore geradora.
Problem
Suponha que queremos encontrar a árvore de abrangência mínima para o seguinte gráfico G usando o algoritmo de Kruskal.
Solution
A partir do gráfico acima, construímos a seguinte tabela -
Edge No. | Par de vértices | Peso da borda |
---|---|---|
E1 | (a, b) | 20 |
E2 | (a, c) | 9 |
E3 | (de Anúncios) | 13 |
E4 | (b, c) | 1 |
E5 | (estar) | 4 |
E6 | (b, f) | 5 |
E7 | (c, d) | 2 |
E8 | (d, e) | 3 |
E9 | (d, f) | 14 |
Agora vamos reorganizar a tabela em ordem crescente em relação ao peso da borda -
Edge No. | Par de vértices | Peso da borda |
---|---|---|
E4 | (b, c) | 1 |
E7 | (c, d) | 2 |
E8 | (d, e) | 3 |
E5 | (estar) | 4 |
E6 | (b, f) | 5 |
E2 | (a, c) | 9 |
E3 | (de Anúncios) | 13 |
E9 | (d, f) | 14 |
E1 | (a, b) | 20 |
Como obtivemos todas as 5 arestas na última figura, paramos o algoritmo e esta é a árvore geradora mínima e seu peso total é $ (1 + 2 + 3 + 5 + 9) = 20 $.
Algoritmo de Prim
O algoritmo de Prim, descoberto em 1930 pelos matemáticos Vojtech Jarnik e Robert C. Prim, é um algoritmo ganancioso que encontra uma árvore geradora mínima para um gráfico ponderado conectado. Ele encontra uma árvore daquele gráfico que inclui todos os vértices e o peso total de todas as arestas da árvore é menor ou igual a todas as árvores geradoras possíveis. O algoritmo de Prim é mais rápido em gráficos densos.
Algoritmo
Inicialize a árvore geradora mínima com um único vértice, escolhido aleatoriamente no gráfico.
Repita as etapas 3 e 4 até que todos os vértices sejam incluídos na árvore.
Selecione uma aresta que conecte a árvore a um vértice que ainda não está na árvore, de modo que o peso da aresta seja mínimo e a inclusão da aresta não forme um ciclo.
Adicione a aresta selecionada e o vértice que ela conecta à árvore.
Problem
Suponha que queremos encontrar a árvore de abrangência mínima para o seguinte gráfico G usando o algoritmo de Prim.
Solution
Aqui começamos com o vértice 'a' e prosseguimos.
Esta é a árvore geradora mínima e seu peso total é $ (1 + 2 + 3 + 5 + 9) = 20 $.