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 $.