53
edits
Changes
Jump to navigation
Jump to search
→Árvores de Extensão Mínima
== Árvores de Extensão Mínima ==
Essa sessão explica como usar o Maple para achar a árvore de extensão mínima de um grafo ponderado. Lembre-se que uma árvore de extensão mínima T de um grafo ponderado G é uma árvore de extensão de G com o mínimo peso de todas as árvores de extensão de G. Os dois algoritmos mais conhecidos para construção de árvores de extensão mínimas são chamados de algoritmo de Prim e algoritmo de Kruskal; nós iremos desenvolver procedures em Maple que implementam ambos os algoritmos aqui.
Iremos começar estudando o algoritmo de Prim. O algoritmo de Prim procede construindo uma árvore sucessivamente selecionando uma aresta de peso mínimo que extende essa árvore de seu atual conjunto de vértices. O pseudocódigo é o seguinte:
1. Comece a construir a árvore de extensão mínima T com a aresta de menor peso de todo o grafo.
2. Adicione a T a aresta de menor peso que é incidente ao vértice em T que não forma um circuito simples em T.
3. Repita o passo (2) até que nós tenhamos um total de n-1 arestas em T.
Para simplificar nossa implementação do algoritmo de Prim, primeiro criamos um procedure chamado de MinWeight, que determina a aresta de menor peso com exatamente um vértice em dado conjunto de vértices.
<pre>
MinWeight:=proc(G::graph, S::set)
local e, i, Candidates, Del, Min_Edge;
</pre>
Determine o conjunto de arestas adjacentes.
<pre>
if S=vertices(G) then Candidates:=edges(G)
else Candidates := incident(S,G); fi;
if Candidates = {} then RETURN(NULL) fi;
</pre>
Determine a aresta candidata de menor peso.
<pre>
Min_Edge:=Candidates[1];
for e in Candidates do
if eweight(Min_Edge,G) > eweight(e ,G) then
Min_Edge:=e;
fi;
od;
RETURN(Min_Edge);
end:
</pre>
O caso especial de todos os vértices de G está incluído para dar um ponto de partida convenient para o algoritmo de Prim. Nesse caso, nós simplesmente retornamos a aresta de G de menor peso. Em todos os outros casos, a busca é restrita a arestas emanando do subgrafo induzido pelos vértices especificados. A implementação depende do fato de que o procedure incidente ache todas as arestas e deixe um conjunto de vértices particular. Ainda, a eficiência geral do algoritmo pode ser melhorada analisando-se sistematicamente uma lista ordenada de arestas, ao invés de procurar por novos candidatos a cada passo.
Dado o procedure MinWeight, a real implementação do algoritmo de Prim é direto ao ponto. Primeiro inicializamos a árvore mínima ponderada T para ser a árvore com apenas uma aresta, sendo essa aresta a de menor peso. A cada passo adicionamos uma aresta de peso mínimo que seja incidente com a atual árvore T.
<pre>
Prim := proc(G::graph)
local i, VT, V, T, e;
new(T);
V := vertices(G);
</pre>
Adicione a aresta de menor peso.
<pre>
e := MinWeight(G,V);
addvertex(ends(e, G), T);
addedge(ends(e,G), T);
</pre>
Repita o laço até que todas as arestas n-1 sejam adicionadas a árvore.
<pre>
for i from 2 to nops(V)-1 do
e := MinWeight(G,vertices(T));
if e = NULL then ERROR(`no spanning tree`) fi;
</pre>
Adicione um novo vértice e uma nova aresta.
<pre>
addvertex(ends(e,G) minus vertices(T), T);
addedge(ends(e,G),weights=eweight(e,G),T);
od;
RETURN( eval(T) );
end:
</pre>
Nós retornamos eval(T) ao invés de apenas T, para se assegurar de que a própria árvore seja passada, e não apenas seu nome.
Para testar o procedure Prim, nós encontramos uma árvore de extensão mínima do grafo ponderado do Exemplo 1 da página 595 do texto. Você pode construir o grafo usando os comandos:
<pre>
new(City1):
addvertex(sf,chic,den,ny,atl,City1):
addedge( [sf,ny,sf,chic,sf,den,sf, atl],
weights=[2000,1200,900,2200], City1):
addedge( [den,chic,den,ny,den, atl],
weights=[1300,1600,1400], City1):
addedge( [chic,ny,chic,atl, atl, ny],
weights=[1000,700, 800], City1):
</pre>
Então, a árvore de extensão mínima é T1, dada por:
<pre>
T1 := Prim(City1):
</pre>
Essa árvore é melhor vista como uma árvore selecionando uma rai particula e então desenhando a árvore.
<pre>
draw(Tree(sf), spantree(T1,sf));
</pre>
O total peso de suas arestas pode ser computada como:
<pre>
total := 0:
for e in edges(T1) do
total := total + eweight(e,T1)
od:
total;
</pre>
O algoritmo de Kruskal constrói a árvore ponderada minima adicionando sucessivamente uma aresta de peso mínimo que não forma um circuito simples em nenhum dos fragmentos de árvore previamente construídos. O pseudocódigo para esse algoritmo é:
1. Ordene as arestas do grafo em ordem crescente.
2. Escolha a aresta de menor peso, e.
3. Se e cria um ciclo T quando adicionado, descarte e da lista e repita o passo (2).
4. Adicione e a árvore ponderada de peso mínimo T.
5. Repita o passo (2) até que a árvore tenha n-1 arestas.
Antes de podermos implementar o algoritmo de Kruskal, precisamos ser capazes de ordenar arestas. Como nas sessões anteriores, podemos fazer isso usando as rotinas de ordenação embutidas no Maple, dando um ótimo procedura para comparação de quaisquer duas arestas.
A rotina de comparação necessária aqui é sutilmente mais complicada que a de antes, pois ela deve usar o grafo em adição com os nomes das arestas dentro da comparação. Isso pode ser feito usando o procedure template, como pode se observar a seguir. Um grafo específico é substituído por um placeholder em um template.
<pre>
edgecompare := proc(G::graph)
subs(TESTG=eval(G) ,
proc(a,b)
if eweight(a,TESTG) <= eweight(b,TESTG) then
true else false fi;
end );
end:
</pre>
Chamando esse procedure em um grafo específico, como City1, nós criamos o procedure comparison customizado para esse grafo.
<pre>
comp1 := edgecompare(City1):
</pre>
Pode ser usado como
<pre>
comp1(e1,e2);
</pre>
Agora para ordenar a lista de arestas de City1 por peso, tudo que precisamos fazer é:
<pre>
edgelist := convert(edges(City1),list);
edgelist := sort(edgelist,comp1);
</pre>
Os pesos dessa lista ordenada estão em ordem crescente, como verificado mapeando o comando eweight na lista.
<pre>
map( eweight , edgelist , City1);
</pre>
Armados com essa rotina de ordenação, estamos quase prontos para implementar o algoritmo de Kruskal. A cada passo do algoritmo, temos uma aresta e, uma coleção de árvores T, formada por arestas de G, e G, e nós devemos determinar se a aresta e forma um ciclo. Isso é feito encontrando os componentes de T, e checando cada componente para ver se ambos os lados da aresta e estão no mesmo componente. Isso é feito pelo procedure:
<pre>
InComponent := proc(e,T::graph,G::graph)
local c,C;
C := components(T);
for c in C do
if ends(e,G) minus c = {} then
RETURN(true); fi;
od;
RETURN(false);
end:
</pre>
Ele faz uso do fato de que os comandos components representam cada componente por um conjunto de vértices.
Agora estamos prontos para implementar o algoritmo de Kruskal.
<pre>
Kruskal:=proc(G::graph)
local E,T,i,n,e;
E := convert( edges(G), list); # sort the edges
E := sort( E, edgecompare(G));
</pre>
comece a construir a floresta
<pre>
new(T); i := 0; n := nops(vertices(G)):
while i < n and E <> [] do
e := E[1];
if InComponent( e , T , G ) then
E := subs(e=NULL,E);
next;
fi;
</pre>
adicione uma nova aresta a floresta
<pre>
addvertex(ends(e,G),T);
addedge(ends(e,G),T);
i := i+1;
E := subs(e=NULL,E);
od;
eval(T); # the new tree
end:
</pre>
Esse algoritmo também pode ser testado na árvore City1, do exemplo 1 na página 595.
<pre>
T2 := Kruskal(City1):
draw(Tree(sf), spantree(T2,sf));
</pre>
== Computações e Explorações ==
