Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 13 - Coggle Diagram
Mapa Mental 13
Capítulo 9: "
Greedy Technique
".
Seção 9.1: "
Prim's Algorithm
".
Tomando como base um problema com várias aplicações práticas:
Sendo fornecidos \(n\) pontos, conecte-os na forma mais barata possível para que haja um caminho entre cada par de pontos.
Os pontos podem ser representados pelos vértices do grafo, as conexões pelas suas arestas, e o custo das conexões pelos pesos das arestas.
E então podemos colocar isso como o problema da árvore geradora mínima:
Uma árvore geradora de um grafo conexo não direcionado é seu subgrafo acíclico conexo.
Se tal grafo possuir pesos associados às suas arestas, uma árvore geradora mínima é sua árvore geradora do menor peso, em que este é definido como a soma de todos os pesos em suas arestas.
Se tentássemos construir essa árvore por busca exaustiva, teríamos dois problemas:
Para grafos densos, o número de árvores geradoras cresce exponencialmente com o tamanho do grafo.
1 more item...
Gerar todas as árvores geradoras para um grafo fornecido não é fácil.
2 more items...
Existem aplicações diretas para todos os tipos de redes, como de comunicação, computador, transporte, e elétrica, já que ele fornece a maneira mais barata de realizar as conexões.
Seção 9.2: "
Kruskal's Algorithm
".
Esse algoritmo também gera sempre uma solução ótima para o problema da árvore geradora mínima.
Ele trata a árvore geradora mínima de um grafo conexo com peso \(G=(V, E)\) como um subgrafo acíclico com \(|V|-1\) arestas para a qual a soma dos pesos da arestas é o menor.
Com isso, ele constrói a árvore geradora mínima como uma sequência em expansão de subgrafos que são sempre acíclicos, mas não necessariamente conexos nas etapas intermediárias do algoritmo.
O algoritmo inicia ordenando as arestas do grafo em ordem não decrescente de seus pesos.
Então, começando com o subgrafo vazio ele escaneia a lista ordenada, adicionando o próximo elemento nela ao atual subgrafo se tal adição não criar um ciclo e pulando-o se criar.
Pseudocódigo do algoritmo de
Kruskal
:
\(E_T ← ∅; ecounter ← 0\)
\(k ← 0\)
while
\(ecounter < |V | − 1\)
do
\(k ← k + 1\)
if
\(E_T ∪ (e_{i_k})\) is acyclic
\(E_T ← E_T ∪ (e_{i_k}); \ ecounter ← ecounter + 1\)
return
\(E_T\)
Usando uma interpretação diferente do algoritmo de
Kruskal
:
As operações do algoritmo podem ser consideradas como uma progressão através de uma série de florestas contendo todos os vértices de um determinado grafo e algumas de suas arestas.
2 more items...