Grafos e Árvores

Prévia do material em texto

Caṕıtulo 5
Grafos - Parte I (Árvores)
Definição: Um grafo é uma tripla ordenada (N , A, g), onde N é um
conjunto não vazio de nós ou vértices, A é um conjunto de arestas e g
uma função que associa cada aresta a a um par não ordenado x− y de nós,
denominados extremidades de a.
Definição: Um grafo direcionado ou digrafo é uma tripla ordenada
(N , A, g), onde N é um conjunto não vazio de nós ou vértices, A é um
conjunto de arcos e g uma função que associa cada arco a a um par ordenado
(x, y) de nós, onde x é o ponto inicial e y é o ponto final de a.
5.1 Terminologia para grafos
• nós adjacentes: são extremidades de algum arco
• laço: uma aresta cujas extremidades são o mesmo nó
• arestas paralelas: arestas com as mesmas extremidades
• grafo simples: que não tem laços nem arestas paralelas
• nó isolado: não é adjacente de nenhum outro nó
• grau de um nó: número de arestas que se ligam ao nó
• grafo completo: grafo onde dois nós distintos quaisquersão adjacentes
16
• subgrafo de um grafo: um grafo cujos conjuntos de nós e arestas são
subconjuntos dos nós e arestas do grafo original, respectivamente, e
cujas extremidades de uma aresta são as mesmas do grafo original
• caminho: é uma seqüência alternada de nós e arestas n0, a0, n1, a1, . . . , ni, ai, ni+1,
onde as extremidades da aresta ai são ni e ni+1. Neste caso, diz-se que
ni+1 é acesśıvel a partir de n0.
• comprimento de um caminho: é o número de arestas que ele contém
• grafo conexo: existe um caminho de qualquer nó para qualquer outro
• ciclo: um caminho de um nó para ele mesmo tal que nenhum nó aparece
mais de uma vez
• grafo aćıclico: um grafo sem ciclos
• grafo bipartido: o conjunto de nós pode ser dividido em dois subcon-
juntos disjuntos não vazios N1 e N2, tais que dois nós são adjacentes
se, e somente se, um deles pertence a N1 e o outro pertence a N2.
• matriz de adjacência: matriz n × n, representando um grafo de n
nós, tal que aij = p se, e somente se, existem p arestas ligando os nós
ni e nj. Caso contrário, aij = 0
• lista de adjacência: lista encadeada com a mesma informação da
matriz de adjacência
5.2 Árvores
Uma árvore é um grafo conexo aćıclico com um nó especial, denominado
raiz da árvore
• profundidade de um nó: é o comprimento do caminho da raiz ao nó
(o nó raiz tem profundidade zero)
• profundidade de uma árvore (altura): é a maior profundidade dos
nós na árvore
• folha: nó sem filhos
17
• nós internos: todos os nós que não são folhas
• floresta: grafo aćıclico não necessariamente conexo
• árvore binária: cada nó tem, no máximo, dois filhos
• árvore binária cheia: todos os nós internos têm dois filhos e as folhas
estão à mesma altura
• árvore binária completa: árvore binária quase cheia (faltam folhas
mais à direita)
5.3 Algoritmos de percurso em árvores
• percorrer uma árvore significa ”visitar´´ todos os seus nós
• algoritmos de percurso são definidos de forma recursiva:
1. pré-ordem: (raiz, sub-árvores)
primeiro a raiz é visitada, depois as sub-árvores da esquerda para
a direita (em pré-ordem)
2. ordem simétrica: (sub-árvore, raiz, sub-árvore)
primeiro a sub-árvore mais à esquerda (em ordem simétrica), de-
pois a raiz e em seguida as sub-árvores à direita (em ordem simétrica)
3. pós-ordem: (sub-árvores, raiz)
primeiro as sub-árvores da esquerda para a direita (em pós-ordem)
e finalmente a raiz
• Aplicação: expressões algébricas podem ser representadas por árvores
binárias, onde um nó pai corresponde ao operador e os nós filhos aos
operandos. Diferentes percursos podem ser usados para avaliar tais
expressões, dando origem às diferentes notações: infixa, prefixa ou
polonesa e pós-fixa ou polonesa reversa
5.4 Aplicações de árvores
• Árvores de decisão: uma árvore de decisão é uma árvore na qual os
nós internos representam ações, os arcos representam os resultados de
uma ação e as folhas representam resultados finais
18
Exemplo: Quantos resultados são posśıveis de obter jogando-se 5 vezes
uma moeda, sem que ocorram 2 caras consecutivas?
• Teorema sobre a cota inferior para um algoritmo de busca:
qualquer algoritmo que resolva um problema de busca em uma lista
com n elementos comparando o elemento desejado x (chave) com os
elementos na lista, tem que fazer pelo menos dlog2 ne+ 1 comparações
no pior caso. Ou seja, um algoritmo de busca é limitado inferiormente
a Θ(log2 n).
• Teorema sobre a cota inferior para um algoritmo de ordenação:
qualquer algoritmo que ordena uma lista de n elementos comparando
pares de elementos na lista, tem que fazer pelo menos dlog2 n!e+1 com-
parações no pior caso. Ou seja, um algoritmo de ordenação é limitado
inferiormente a Θ(log2 n!) = Θ(nlog2 n).
• Códigos de Huffman: consiste em gerar um código de prefixo (o
código para um śımbolo nunca é o prefixo do código de qualquer outro
śımbolo) baseado na freqüência de ocorrência dos śımbolos. Para isso,
é constrúıda a árvore de Huffman, onde cada folha corresponde um
śımbolo, sendo que śımbolos menos freqüentes estão em folhas de maior
profundidade.
19
Exerćıcios (Árvores)
1. Prove que uma árvore com n nós tem n− 1 arcos (n ≥ 1).
2. Prove que Θ(log2 n!) = Θ(nlog2 n).
3. Prove que qualquer árvore binária com n nós tem altura d ≥ blog2 nc.
4. Prove que uma árvore binária de altura d tem, no máximo, 2d folhas.
5. Construa a árvore de Huffman para codificar os seguintes śımbolos e
suas freqüências relativas: a (48%), c (9%), g (12%), k (4%), p (17%),
? (10%). Em seguida, forneça o código de cada śımbolo.
6. Construa a árvore binária que representa a expressão (2+x)∗4 e avalie
esta expressão usando notação infixa, polonesa e polonesa reversa.
20