Arvores

Cap´ıtulo 2 Arvores Defini¸ c˜ ao 29. Uma Arvore ´e um grafo simples, conexo e aciclico. Exemplo 9. A figura 2.1 ´e um exemplo duma ´arvore:

´ Figura 2.1: Arvore

´ Defini¸ c˜ ao 30. Arvore com raiz ´e uma ´arvore com um vertice particular designado raiz. Exemplo 10. A figura 2.2 mostra um exemplo duma ´arvore vom raiz: e(raiz) g

b

f

d

i a

c

j

´ Figura 2.2: Arvore com raiz

26

h

´ Sicuaio e Lu ´ cia Ginger USTM Tome

2.1

Propriedades das arvores

Teorema 10. Seja T um grafo simples com n vertices. As quatro afirma¸c˜ oes s˜ao equivalentes: (a) T ´e uma arvore. (b) T ´e conexo e n˜ao cont´em circuitos. (c) T ´e conexo e tem n − 1 arestas. (d) T n˜ao cont´em ciclos e tem n − 1 arestas. Defini¸ c˜ ao 31. Seja T uma arvore com raiz, v0 raiz de T . Suponhamos que x, y e z s˜ao vertices pertencentes a T e que (v0 , v1 , . . . , vn ) ´e um caminho pertencente a T. Ent˜ ao (a) vn−1 ´e o pai de vn . (b) v0 , . . . , vn−1 s˜ ao antepassados de vn . (c) vn ´e filho de vn−1 . (d) Se x ´e antepassado de y, ent˜ao y ´e um descendente de x. (e) Se x e y s˜ ao filhos de z, ent˜ao x e y s˜ao irm˜aos. (f ) Se x n˜ ao tem filho, x ´e um vertice terminal (ou folha). (g) Se x n˜ ao ´e um vertice terminal, x ´e um vertice interno. Exemplo 11. Na ´arvore com raiz da figura 2.2, (a) o pai de i ´e g. (b) os antepassados de j s˜ao i, g e e. (c) os filhos de e s˜ ao b, d, f e g. (d) os descendentes de g s˜ ao h, i e j. (e) b, d, f e g s˜ao irm˜aos. (f ) a, d, f , c, j e h s˜ao vertices terminais. (g) b, i e g s˜ao vertices internos. Defini¸ c˜ ao 32. Uma ´ arvore bin´ aria ´e uma ´arvore com raiz na qual cada vertice tem ou um filho a esquerda, um filho a direita, um filho a esquerda e a direita, ou nenhum filho. Uma arvore bin´ aria completa ´e uma arvore bin´aria na qual todos os vertices tem ou um filho a direita e a esquerda ou nenhum filho. Exemplo 12. Os grafos da figura 2.3 s˜ ao exemplos de arvores bin´arias. A arvore bin´aria T2 ´e uma arvore binaria completa pois cada vertice tem ou um filho a direita e um filho a esquerda, ou n˜ao tem nenhum filho. Na arvore bin´aria T1 , os vertices b, c e d s˜ao filhos a esquerda e g, e, h e f s˜ ao filhos a direita. 27

´ Sicuaio e Lu ´ cia Ginger USTM Tome a g

b e

c

h f

d (T1 )

(T2 ) ´ Figura 2.3: Arvores bin´arias

2.2

´ Arvores com pesos

Defini¸ c˜ ao 33. Seja T uma ´arvore com raiz. Se cada folha de T estiver associado com um numero real, diremos que T ´e uma ´ arvore com pesos. Cada n´ umero real associado com as folhas de T chama-se peso. Se T tiver n folhas e n n´ıveis, ter´a respectivamente w1 , w2 , . . . , wn pesos e li , (i = 1, 2, . . . , n) comprimento da raiz at´e a folha wi . Chama-se peso duma arvore W (T ) ao somatorio dos produtos dos pesos da folhas pelos seus niveis, isto ´e: W (T ) =

n X

wi · li .

i=1

Exemplo 13. As ´arvores da figura 2.4 s˜ao exemplos de grafos com pesos. As folhas da ´arvore

4 9

7

7

6

2

6

4

9

7

9 7

2

(T2 )

7

6 4

(T1 )

7

2 (T3 )

´ Figura 2.4: Arvore com pesos T1 tem pesos 2, 4, 6, 7, 7 e 9. Assim, o peso w1 = 2, w2 = 4, w3 = 6, w4 = 7, w5 = 7 e w6 = 9. Os n´ıveis das folhas s˜ao l1 = 3, l2 = 1, l3 = 3, l4 = 2, l5 = 1 e l6 = 2. Ent˜ao o peso da arvore T1 ´e: W (T1 ) =

6 X

wi · li = 2 · 3 + 4 · 1 + 6 · 3 + 7 · 2 + 7 · 1 + 9 · 2 = 67.

i=1

28

´ Sicuaio e Lu ´ cia Ginger USTM Tome Para a ´arvore T2 temos W (T2 ) =

6 X

wi · li = 90.

i=1

E para a ´arvore T3 temos W (T3 ) =

6 X

wi · li = 88.

i=1

2.2.1

Algor´ıtimo de Huffman

Dada uma lista L = (w1 , w2 , . . . , wn ) de pelo menos dois numeros n˜ao negativos, e queremos construir uma arvore bin´aria com pesos T com os membros de L como pesos, de tal maneira que o peso W (T ) da arvore seja o m´ınimo poss´ıvel. Chamaremos tal arvore T de ´ arvore bin´ aria ´ optima para os pesos w1 , w2 ,. . . ,wn . O algor´ıtimo recurssivo seguinte resolve o problema, produzindo uma ´arvore bin´aria ´optima T (L). Huffman(List) {Input: Uma lista L = (w1 , w2 , . . . , wn ) de numeros n˜ao negativos, n ≥ 2 } {Output: Uma ´arvore bin´aria ´optima T (L) para L} Se n = 2 ent˜ao T (L) ´e uma ´arvore com 2 folhas, de pesos w1 e w2 caso contr´ario procurar dois membros (elementos) de L, diremos u e v. Seja L0 uma lista obtida de L pela remo¸ca˜o de u e v e inser¸c˜ao de u + v. Recur para L0 e de T (L) para Huffman(L0 ) pela substitui¸c˜ao de uma folha de peso u + v em Huffman(L0 ) por uma subarvore com duas folhas de pesos u e v. return T (L). Exemplo 14. Considere os pesos 2, 4, 6, 7, 7, 9. Primeiro o algor´ıtimo repetidamente combina os dois pesos menores para obter uma nova sequencia mais curta pela substitui¸c˜ ao destes pela sua soma. Execu¸c˜ ao do algor´ıtimo Huffman(2,4,6,7,7,9) substituir 2 e 4 por 2 + 4 e Huffman(6,6,7,7,9) substituir 6 e 6 por 6 + 6 e Huffman(7,7,9,12) substituir 7 e 7 por 7 + 7 e Huffman(9,12,14) substituir 9 e 12 por 9 + 12 e Huffman(14,21) que constr´ oi a primeira ´arvore na figura 2.5 que representa o 29

´ Sicuaio e Lu ´ cia Ginger USTM Tome

7

7

9 6 2

4

´ Figura 2.5: Arvore com peso m´ınimo resultado da ´arvore da execu¸c˜ ao do algor´ıtimo de Huffman: Exemplo 15. Vamos encontrar uma arvore bin´aria ´optima com pesos 2,3,5,7,10,13,19. Vamos repetidamente combinar os dois menores pesos para obter as sequencias de pesos 2,3,5,7,10,13,19 → 5,5,7,10,13,19 → 7,10,10,13,19 → 10,13,17,19 → 17,19,23 → 23,36.A figura 2.6 mostra o resultado da ´arvore da execu¸c˜ ao do algor´ıtimo de Huffman:

10

13

19 7 5 2

3

´ Figura 2.6: Arvore com peso m´ınimo

2.2.2

Codigos de Huffman

Defini¸ c˜ ao 34. Seja T uma ´arvore bin´aria. Se a cada filho a esquerda for associado um digito zero e digito um a cada filho a direita . A cada sequencia de digitos da raiz at´e as folhas denomina-se Codigo Prefixo Exemplo 16. O conjunto {000, 0100, 0101, 110, 11100, 11101} repesenta o codigo prefixo gerado pela arvore bin´aria da figura 2.7. 30

´ Sicuaio e Lu ´ cia Ginger USTM Tome

0

1

0

0

1

1

0

0

1

0 0

1 0

1

´ Figura 2.7: Arvore bin´aria com Codigo Prefixo Defini¸ c˜ ao 35. Seja T uma ´arvore bin´aria com peso m´ınimo. O codigo prefixo formado por T denomina-se C´ odigo de Huffman. Exemplo 17. Consideremos um alfabeto que consiste das letras a, v, e, r, y, o, z, p que tem frequencias correspondentes a = 30, v = 5, e = 25, r = 16, y = 4, o = 8, z = 3, p = 9. Vamos determinar uma ´arvore m´ınima representada pela figura 2.8 para o alfabeto e o codigo prefixo (c´ odigo de Huffman) correspondente ´e: a = 11, v = 1000, e = 01, r = 101, y = 10011, o = 000, z = 10010, e p = 001. Podemos codificar a mensagem: ”arvore”, mapeando cada caracter pelo respectivo codigo, assim

25 8

30

9

16 5 3

4

´ Figura 2.8: Arvore bin´aria m´ınima temos o codigo seguinte da palavra arvore: 11101100000010101. Para descodificar o c´odigo 001101000100011, vamos percorrer os caracteres da esquerda para a direita comparando com os codigos prefixos das letras (alfabeto), assim para o codigo dado teremos a seguinte mensagem: ”prova”. 31

´ Sicuaio e Lu ´ cia Ginger USTM Tome

2.3

Spanning Trees

Defini¸ c˜ ao 36. Uma ´arvore T ´e uma ´ arvore geradora dum grafo G se T ´e um subgrafo de G que cont´em todos os vertices de G. Exemplo 18. Teorema 11. Um grafo G tem uma arvore geradora se e somente se G for conexo.

2.4

Minimal Spanning Trees

Defini¸ c˜ ao 37. Seja G um grafo com pesos. Uma ´ arvore geradora m´ınima de G ´e uma arvore geradora de G com peso m´ınimo. Exemplo 19.

2.4.1

Algoritmo de Prim

{input: Um grafo conexo com pesos} {ouput: Um conjunto E de arestas de uma arvore geradora m´ınima.} E=∅ Escolher w ∈ V (G) e V := {w} while V 6= V (G) do Escolher uma aresta {u, v} em E(G) de peso m´ınimo com u ∈ V e v ∈ V (G) − V. Colocar {u, v} em E e v em V. return E. Exemplo 20.

2.4.2

Algoritmo de Kruskal

{input: Um grafo conexo com pesos G, com arestas listadas na ordem crescente} {ouput: Um conjunto E de arestas de uma arvore geradora m´ınima para G.} E=∅ 32

´ Sicuaio e Lu ´ cia Ginger USTM Tome For j = 1 to |E(G)| do S If (E {ej } ´e aciclico) then Colocar ej em E return E. Exemplo 21.

2.5

Percurso de Arvores

2.5.1

Preorder

2.5.2

Inorder

2.5.3

Postorder

33

Cap´ıtulo 3 Automatos, Gramaticas, e Linguagens 3.1

Circuitos sequenciais e Maquinas de estados finitos

3.2

Automatos de estados finitos

3.3

Linguagens e Gram´ aticas

3.4

Automatos finitos indeterminados

3.5

Rela¸c˜ ao entre automatos e Linguagens

34