53
edits
Changes
Jump to navigation
Jump to search
no edit summary
<pre>
IsTree(T1); IsTree(complete(3));
</pre>
==='''Árvores com raiz'''===
Até esse ponto, nós lidamos apenas com árvores sem raiz. Podemos usar o comando Maplespantree para mudar uma árvore sem raiz em uma árvore com raiz. Ele faz isso atualizando os conjuntos de ancestrais e filhas (descendentes) para cada vértice, para refletir a estrutura da spanning tree.
Para usar o comando spantree, devemos selecionar o vértice e formar uma spanning tree com esse vértice como raiz, direcionando todas as arestas na árvore em direção a raiz. (Estudaremos spanning trees mais tarde nesse capítulo. Geralmente, o comando spantree pega um grafo conexo indireto G e um vértice v e constrói uma spanning tree de G usando v como a raiz, direcionando todas as arestas em direção a v.) Por exemplo, podemos transformar a árvore T1 em uma árvore com raiz, tomando a como sua raiz e utilizando o comando:
<pre>
T2:=spantree(T1, a):
</pre>
Podemos facilmente observar relações entre vértices de uma árvore utilizando comandos embutidos no Maple. Entre os comandos que são úteis para isso estão daughter, ancestor, neighbours e departures. O comando daughter encontra os filhos de um vértice em uma árvore com raiz, e o comando ancestor do Maple encontra o vértice pai de um vértice em uma árvore com raiz. Os comandos neighbors e departures agem de maneira similar, determinando os filhos de um vértice em uma árvore com raiz.
Para ilustrar o uso de alguns desses comandos no Maple, podemos determinar relações de árvores como pais, filhos, ancestrais e descendentes de vértices específicos. Por exemplo, podemos encontrar os filhos do vértice a na árvore T2, usando o comando:
<pre>
daughter(a, T2);
</pre>
Para achar o pai de d na árvore T2, usamos o comando:
<pre>
ancestor(d, T2);
</pre>
Agora representamos um procedure que encontra todos os descendentes, ancestrais e irmãos de um vértice particular em uma árvore com raiz. Esse procedure, chamado Family, pode ser descrito usando o seguinte pseudo-código:
1. Para encontrar todos os ancestrais, usamos o comando ancestor do Maple até não haverem mais ancestrais (ex: quando atingimos o vértice raiz).
2. Para achar todos os descendentes, usamos o comando daughter repetidamente até não haverem mais descendentes(ex: quando todas as folhas de um vértice forem atingidas).
3. Para se achar todos os irmãos de um vértice v, primeiros encontramos o ancestral de v, chamado w; os irmãos de v são descendentes de outro w de v.
Uma implementação desse procedure é como a seguinte:
<pre>
Family := proc(v::name,G::graph)
local Temp, Ancestors, Descendants, Siblings;
Ancestors := ancestor(v,G);
Temp := ancestor(v,G);
while not (Temp = {}) do
Ancestors := Ancestors union Temp;
Temp := ancestor(Ancestors,G);
od;
Descendants := daughter(v,G);
Temp := daughter(v,G);
while not (Temp = {}) do
Descendants := Descendants union Temp;
Temp := daughter(Descendants,G);
od;
Siblings := daughter(ancestor(v, G), G) minus v;
[Ancestors,Siblings,Descendants];
end:
</pre>
Agora iremos construir uma árvore mais larga, chamada T3 que é a árvore mostrada na Página 5433 do texto, e então iremos executar o novo procedure criado em um de seus vértices.
<pre>
new(T3):
addvertex(A,B,C,D,E,F,G,H,I,J,K,L,M,N,T3):
addedge( [A,B],[A,J],[A,K],[B,C],[B,E],[B,F],
[C,D],[F,G],[F,I],[G,H],[K,L],[L,M],[L,N], T3):
draw(Tree(A),T3);
</pre>
Os descentendes do vértice B são obtidos pelo comando:
<pre>
Bfamily := Family(B,T3); Bfamily[3];
</pre>
A seguir, determinamos o conjunto de vértices internos (galhos) e folhas de uma árvore com raiz. Lembre-se que um v é um vértice interno de uma árvore com raiz se v tiver filhos, e que v é o vértice folha de uma árvore com raiz se v não tiver filhos. Em outras palavras, em qualquer árvore com raiz não trivial (ex:.uma árvore com raiz que é mais do que apenas um vértice raiz), as folhas são essas com gráu de vértice 1, e os vértices internos são vértices com grau maior que 1.
Sabendo disso, podemos usar o comando Maplevdegree para determinar o conjunto de folhas e o conjunto de vértices internos dada uma árvore com raiz.
<pre>
Leaves:=proc(T::graph, root::name)
select( proc(x,T) evalb( vdegree(x,T) < 2 ) end,
vertices(T) minus root , T );
end:
Internal:=proc(T::graph, root::name)
select( proc(x,T) evalb( vdegree(x,T) > 1 ) end,
vertices(T) minus root , T );
end:
Leaves(T2, a); Internal(T2,a);
</pre>
Agora iremos discutir como encontrar o maior número de filhos de um vértice interno de uma árvore com raiz. Lembre-se que se m é esse número, a árvore é chamada de árvore m-ária. Também iremos descrever como determinar se uma árvore m-ária é balanceado. Lembre-se que uma árvore é balanceada se todas as folhas estão no nível h ou h-1 se uma árvore tem um total de h níveis, onde o nível do vértice é a distância do caminho único from da raiz até tal vértice.
Para utilizar o Maple para determinar se uma árvore é uma árvore m-ária, podemos simplesmente olhar a sequencia de graus do vértice, tomando em conta que para todos os vértices exceto a raiz, o grau de tal vértice é um a mais que o número de descendentes. Isso pode ser feito usando o comando vdegree no Maple. Para determinar se uma árvore é balanceada, podemos usar a estrutura de armazenamento interno de uma árvore em Maple. Iremos utilizar do fato de que o Maple armazena o nível do vértice em uma árvore como o peso do vértice para esse vértice. Por exemplo, se v é um vértice que está no nível 3 de uma árvore, então podemos extrair essa informação usando o comando vweight no vértice v.
Esaa técnica é formalizade pelo seguinte procedure no Maple:
<pre>
ArityBalanced:=proc(G::graph, Root::name)
local Leaf_Depth, V, Max_Children, is_balanced,i;
V:=vertices(G); Leaf_Depth:={};
is_balanced:=false;
for v in V do
if (not (v = Root)) and (vdegree(v,G)=1) then
Leaf_Depth:=Leaf_Depth union vweight(v, G);
fi;
od;
if nops(Leaf_Depth) > 2 then
printf(`The tree is not balanced`);
elif nops(Leaf_Depth) = 1 then
printf(`The tree is balanced`);
is_balanced:=true;
elif nops(Leaf_Depth) = 2
and abs(Leaf_Depth[1] - Leaf_Depth[2]) > 1 then
printf(`The tree is not balanced`);
else
printf(`The tree is balanced %a`, Leaf_Depth );
is_balanced:=true;
fi;
Max_Children:=maxdegree(G)-1;
if vdegree(Root, G) > Max_Children then
Max_Children:=vdegree(Root, G);
fi;
printf(`The arity of the tree is %d`, Max_Children);
[Max_Children, is_balanced];
end:
</pre>
<pre>
ArityBalanced(T3, A):
</pre>
Agora iremos utilizar o procedure ArityBalanced para verificar a fórmula na página 541 do texto para árvore m-árias cheias. Isto é, iremos construir um procedure para computar o número de vértices internos e folhas de dada árvore m-ária, e comparar essas quantidades como esboçado no teorema 3 e teorema 4 da página 541 do texto. O procedure chamado TheoremVerify utilizará:
<pre>
TheoremVerify:=proc(G::graph, Root::name)
local internal, m, leaves, n, i, V, is_full_tree;
V:=vertices(G);
n:=nops(V);
i:=0; internal:=0; leaves:=0;
is_full_tree:=true;
</pre>
Use o procedure ArityBalanced para determinar o número de argumentos
<pre>
m:=ArityBalanced(G, Root)[1];
while is_full_tree and i<n do
i:=i+1;
</pre>
Se não houverem filhos do vértice, ele é uma folha
<pre>
if nops(daughter(V[i], G)) = 0 then
leaves:=leaves+1;
</pre>
Se o número de filhos não for m, então não é uma árvore completa
<pre>
elif not (nops(daughter(V[i],G)) = m) then
printf(`The tree is not a full tree`);
is_full_tree:=false;
</pre>
O vértice atual é um vértice interno
<pre>
else
internal:=internal+1;
fi;
od;
if is_full_tree then
printf(`Vertices count is %d`, n);
printf(`Computed count (m*i+1) is %d`, m*internal + 1);
printf(`Leaf count is %d`, leaves);
printf(`Computed count ((m-1)*i + 1) is %d`,
(m-1)*internal+1);
fi; NULL;
end:
</pre>
Utilizaremos o procedure TheoremVerify para verificar os teoremas 3 e 4 do texto em uma árvore 3-ária completa.
<pre>
new(Full1):
addvertex(A,2,3,4,5,6,7,8,9,10, Full1):
addedge(A,2, A,3, A,4, 2,5, 2, 6, 2,7,
4,8, 4,9, 4,10, Full1):
</pre>
<pre>
TheoremVerify(Full1, A);
</pre>
