Árvores

Esse capítulo é dedicado aos aspectos computacionais do estudo das árvores. Árvores são um tipo específico de grafo, que são conectados grafos simples que não tem circuitos simples.

O código Maple nesse capítulo assume que você está usando uma versão atualizada do Maple Network Package. Essas melhorias afetam principalmente a exibição das árvores. Em particular, o comando draw foi atualizado para se entender como desenhar árvores com raiz. Para testar se você está utilizando a versão correta, carregue o pacote networks e rode a versão comando, como em:

with(networks): version();

Se esse comando não produzir uma descrição da versão, então vocês está utilizando a versão errada. Uma versão apropriada pode ser encontrada no site ftp: http://www.mhhe.com/math/advmath/rosen/r5/instructor/maple.html junto com instruções de instalação.

Primeiro, nós iremos discutir como representar, desenhar, e trabalhar com árvores usando o Maple. Especificamente, nós iremos descrever como representar e construir árvores e derivar características básicas sobre árvores em Maple. Nós iremos demonstrar como utilizar o Maple para desenhar árvores.Nós iremos demonstrar como resolver vários problemas, onde árvores fazem um papel importante usando Maple, como procurando e construindo códigos prefixos, usando uma implementação específica do algoritmo de Huffman. Nós iremos descrever como usar o Maple para fazer diferentes métodos de percorrer árvore, onde o percurso é a visita dos vértices da árvore em uma ordem pré-definida. Então nós iremos discutir como esses percursos se relacionam com o tópico de organização. Continuamos mostrando como usar o Maple para criar spanning trees de grafos. Então, nós iremos mostrar como usar o Maple como resolver vários problemas utilizando backtracking. Finalmente, iremos mostrar como encontrar spanning trees de peso mínimo de grafos ponderados usando Maple.

Introdução à Árvores

Para começar, iremos demonstrar como construir árvores em Maple. Dada uma árvore sem raiz, nós podemos construir essa árvore em Maple assim como faríamos com qualquer grafo. Nós também iremos dar um procedure que usa algumas capacidades embutidas do Maple que determinam se um grafo específico é uma árvore.

Antes de entrar na implementação, há dois pontos importantes que devem ser mencionados. Primeiro, notamos que o Maple difere da terminologia de texto, no senso que o Maple refere-se a simples ciclos, quando o texto se refere a simples circuitos. O segundo ponto que vale mencionar é de que uma árvore sem raiz é um grafo simples que não tem ciclos simples. Estruturalmente falando, uma árvore com raiz é exatamente a mesma coisa que uma árvore sem raiz, com a propriedade adicional de que há um vértice específico chamado de raiz, que é visto como o ponto inicial de uma árvore. Em termos de implementação Maple, representamos árvores sem raiz como grafos, e criamos árvores sem raiz a partir de árvores sem raiz utilizando comandos Maple como spantree, que serão abordados posteriormente, especificando um nó desejado para uma árvore sem nó.

Outro tipo importante de árvore é a árvore ordenada, que é uma árvore com raiz onde os filhos de um vértice ordenados de alguma maneira como 1st, 2nd,...,m-th filhos se houverem m filhos de um dado vértice. Nós iremos fazer uso do peso dos vértices para determinar a ordem dos filhos de um vértice específico. Esse tipo de árvore irá aparecer posteriormente, mas é importante distinguir árvores sem raiz, com raiz e desordenadas, e árvores com raiz e ordenadas.

Como primeiro exemplo, iremos discutir árvores sem raiz. Criamos uma árvore exatamente da mesma maneira que criamos um grafo, usando o pacote networks do Maple. Como nosso primeiro exemplo, iremos criar uma árvore simples em 4 vértices.

with(networks):
new(T1): addvertex(a,b,c,d,f,g,T1):
addedge(a,b,a,c,a,d,b,f,b,g, T1):
draw(Tree(a),T1);

Suponha que fomos dados um grafo e se foi pedido para determinar se ele é ou não uma árvore. Pela definição de árvores, precisamos verificar as 3 seguintes propriedades:

1.O grafo é conectado.

2. O grafo é simples.

3. O grafo não tem ciclos.

Usando Maple, essas propriedades são facilmente verificadas. Em particular, podemos determinar se um grafo é conectado em Maple usando o comandoscomponents, que retorna uma coleção de conjuntos de vértices, onde cada conjunto nessa coleção contém os vértices de um componente conexo do grafo. Podemos determinar se um grafo é simples usando o comando Maple gsimp, que retorna a árvore simples por baixo de um multigrafo, e então comparando o número de arestas da árvore por baixo do grafo original. Isso nos leva até o procedure IsSimple.

IsSimple := proc(G::graph) local H;
    H := networks[duplicate](G); 
    if nops(edges(gsimp(H))) = nops(edges(G)) then true
    else false fi;
end:

Note que não devemos simplificar G por si só, pois tal simplificação é um processo irreversível.

Para testar conectividade, utilizamos o procedure IsConnected

IsConnected := proc(G::graph) 
evalb(nops(components(G)) = 1) end:

Podemos determinar se um grafo tem ou não ciclos utilizando o comando cyclebase do Maple que retorna um conjunto de ciclos, ou circuitos simples, que formam uma base de todos os ciclos (circuitos simples) no grafo dado; se o cyclebase não tiver ciclos, o grafo não tem ciclos. Isso, junto com os dois testes anteriores pode ser usado para testar se um grafo é uma árvore.

IsTree:=proc(G::graph)
  if not (IsConnected(G) and IsSimple(G)) then 
    RETURN(false); fi;
  if cyclebase(G) = {} then RETURN(true);
  else RETURN(false); fi;
end:

Se você preferir, pode substituir o teste cycle base test nesse procedure por um que verifica se o número de arestas é um a menos que o número de vértices.

Agora estamos prontos para usar o procedure IsTree para determinar se alguns grafos particulares são árvores;

IsTree(T1);  IsTree(complete(3));

Á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:

T2:=spantree(T1, a):

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:

daughter(a, T2);

Para achar o pai de d na árvore T2, usamos o comando:

ancestor(d, T2);

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:

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:

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.

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);

Os descentendes do vértice B são obtidos pelo comando:

Bfamily := Family(B,T3);  Bfamily[3];

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.

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);

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:

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:

ArityBalanced(T3, A):

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á:

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;

Use o procedure ArityBalanced para determinar o número de argumentos

  m:=ArityBalanced(G, Root)[1];
  while is_full_tree and i<n do
    i:=i+1;

Se não houverem filhos do vértice, ele é uma folha

    if nops(daughter(V[i], G)) = 0 then
       leaves:=leaves+1;

Se o número de filhos não for m, então não é uma árvore completa

    elif not (nops(daughter(V[i],G)) = m) then
       printf(`The tree is not a full tree`);
       is_full_tree:=false;

O vértice atual é um vértice interno

    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:

Utilizaremos o procedure TheoremVerify para verificar os teoremas 3 e 4 do texto em uma árvore 3-ária completa.

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):

TheoremVerify(Full1, A);