MO640 - Exercícios - Para 2004-10-06

1. Representação textual de árvores PQ: para nós P, use (P <lista de filhos>); para nós Q, use (Q <lista de filhos>); e para folhas, simplesmente o nome da folha.  Faça a representação textual das árvores das figuras 3 e 4 do artigo de Booth e Leuker.
   1. Figura 3: (P A B C (Q D (P E F) (Q (P G H) I (P J K))))
   2. Figura 4: (P B (Q (Q (P H G) I (P J K)) (P E F) D) C A)

2. Calcule a norma da árvore PQ da figura 3 do artigo de Booth e Leuker.

   Segundo o artigo, a norma de uma árvore PQ se calcula da seguinte forma: NORM(T) = Número de nós Q + Número de nós cujo pai é P.
   Portanto, para a árvore da figura 3, a norma é NORM(T)=2+10=12.



3. Uma árvore PQ genérica tem k nós internos, com aridades a₁, a₂, ..., a_k.  Encontre uma igualdade envolvendo k, os a_i's, e m = |U|.

   k + m = 1 + (a₁+a₂+...+a_k).
   O termo a esquerda indica o número de vértices do grafo, e (a₁+a₂+...+a_k) representa o número de arestas do grafo.