Grafos e Árvores

Prévia do material em texto

Exercícios 
• Diga se os dois grafos apresentados são ou não 
isomorfos. Se forem, apresente a função que 
estabelece o isomorfismo entre eles; caso 
contrário, explique por quê. 
Resposta 
• São isomorfos e as funções que estabelecem o 
isomorfismo são: 
• 𝑓1: 1 → a 𝑓2: 𝑎1 → 𝑒2 
 2 → b 𝑎2 → 𝑒7 
 3 → c 𝑎3 → 𝑒6 
 4 → d 𝑎4 → 𝑒1 
 𝑎5 → 𝑒3 
 𝑎6 → 𝑒4 
 𝑎7 → 𝑒5 
Exercícios 
• Para cada um dos grafos a seguir determine se o 
grafo é planar (mostrando uma representação 
planar) ou não-planar (encontrando um subgrafo 
homeomorfo a 𝑘3,3 ou 𝑘5 
Resposta 
• O primeiro é planar por ter representação. 
 
Planar 
E este, é planar? 
Resposta 
• O primeiro é planar por ter representação. 
 
Planar 
E este, é planar? a ≤ 3n – 6 
10 ≤ 3(7) -6 
10 ≤ 15 verdade 
Resposta 
• O primeiro é planar por ter representação. 
 
Planar 
E este, é planar? a ≤ 3n – 6 
10 ≤ 3(7) -6 
10 ≤ 15 verdade 
 
a ≤ 2n – 4 
10 ≤ 2(7) – 4 
10 ≤ 10 
Resposta 
• O primeiro é planar por ter representação. 
 
Planar 
E este, é planar? a ≤ 3n – 6 
10 ≤ 3(7) -6 
10 ≤ 15 verdade 
 
a ≤ 2n – 4 
10 ≤ 2(7) – 4 
10 ≤ 10 verdade É planar! 
Então tem representação 
Resposta 
Árvores 
Árvores 
• As árvores são um tipo especial de grafos e são 
muito utilizadas na representação de dados. 
• Definição: Uma árvore é grafo conexo acíclico 
com um nó especial chamado raiz. 
• Uma árvore sem nenhum nó designado como 
raiz é conhecida como árvore sem raiz ou árvore 
livre. 
• Uma árvore pode ser construída recursivamente. 
• Um único vértice é uma árvore (este vértice é a raiz). Se 
T1, T2, ..., Tt são árvores disjuntas com raízes r1, r2,..., rt, 
o grafo formado pela ligação de um novo vértice r, por 
uma única aresta a cada uma dos vértices r1, r2,..., rt 
constitui uma árvore de raiz r. Os vértices r1, r2, ...,rt são 
filhos de r, e r é pai de r1, r2, ..., rt. 
• Como uma árvore é um grafo conexo, existe um caminho 
entre a raiz e todos os vértices da árvore; 
• Como a árvore é acíclica, este caminho é único. 
• A profundidade de um vértice em uma árvore é o 
comprimento do caminho da raiz até o vértice, em 
particular, a raiz tem profundidade 0. 
• A altura (profundidade) da árvore é a maior 
profundidade de todos seus vértices, em outras palavras, 
é o comprimento do maior caminho entre a raiz e um 
vértice. 
a. Qual a altura? 
b Qual o filho à esquerda do nó 2? 
c. Qual a profundidade do nó 5? 
• Como uma árvore é um grafo conexo, existe um caminho 
entre a raiz e todos os vértices da árvore; 
• Como a árvore é acíclica, este caminho é único. 
• A profundidade de um vértice em uma árvore é o 
comprimento do caminho da raiz até o vértice, em 
particular, a raiz tem profundidade 0. 
• A altura (profundidade) da árvore é a maior 
profundidade de todos seus vértices, em outras palavras, 
é o comprimento do maior caminho entre a raiz e um 
vértice. 
a. Qual a altura? 2 
b Qual o filho à esquerda do nó 2? 
c. Qual a profundidade do nó 5? 
• Como uma árvore é um grafo conexo, existe um caminho 
entre a raiz e todos os vértices da árvore; 
• Como a árvore é acíclica, este caminho é único. 
• A profundidade de um vértice em uma árvore é o 
comprimento do caminho da raiz até o vértice, em 
particular, a raiz tem profundidade 0. 
• A altura (profundidade) da árvore é a maior 
profundidade de todos seus vértices, em outras palavras, 
é o comprimento do maior caminho entre a raiz e um 
vértice. 
a. Qual a altura? 2 
b Qual o filho à esquerda do nó 2? 4 
c. Qual a profundidade do nó 5? 
• Como uma árvore é um grafo conexo, existe um caminho 
entre a raiz e todos os vértices da árvore; 
• Como a árvore é acíclica, este caminho é único. 
• A profundidade de um vértice em uma árvore é o 
comprimento do caminho da raiz até o vértice, em 
particular, a raiz tem profundidade 0. 
• A altura (profundidade) da árvore é a maior 
profundidade de todos seus vértices, em outras palavras, 
é o comprimento do maior caminho entre a raiz e um 
vértice. 
a. Qual a altura? 2 
b Qual o filho à esquerda do nó 2? 4 
c. Qual a profundidade do nó 5? 2 
• Um vértice sem filhos é chamado de folha; 
• os vértices que não são folhas são chamados de 
vértices internos ou nós internos. 
• Uma árvore binária com n nós possui n-1 arestas. 
• Uma floresta é qualquer grafo acíclico (não 
necessariamente conexo), portanto, uma floresta 
é uma coleção de árvores disjuntas 
 
• Uma árvore de interesse especial são as árvores binárias. 
• Em uma árvore binária, cada nó tem no máximo dois 
filhos. 
• Cada filho de um nó é chamado filho esquerdo ou filho 
direito. 
• Uma árvore binária cheia possui todos os nós internos 
com dois filhos e todas as folhas estão à mesma 
profundidade. 
 
Árvore binária Cheia 
• Uma árvore binária completa é uma árvore 
binária que é quase cheia. 
• O nível mais baixo da árvore vai se enchendo da 
esquerda para a direita mas pode ter folhas 
faltando. 
• Note que, embora uma árvore seja um grafo, uma 
árvore binária completa não é um grafo completo. 
 
Árvore binária Completa 
Aplicações 
• Árvores de decisão; 
• Árvore genealógica; 
• Fluxo organizacional (hierarquia em 
uma empresa); 
• Estrutura de arquivos e diretórios em 
um computador; 
• ... 
+ 
- 
+ 
* 
2 5 
3 
2 4 10 
* 
(((2*5)+3)-2) + (4*10) 
Percursos em Árvores 
• Percorrer uma árvore significar visitar 
todos os seu nós 
• Considerando árvores binárias, temos as 
seguintes estratégias mais comuns de 
percurso: 
– Pré-ordem (raiz, esquerda, direita) 
– Ordem simétrica (esquerda, raiz, direita) 
– Pós-ordem (esquerda, direita, raiz) 
Exemplo 
• Pré-ordem (raiz, esquerda, direita) 
– a, b, d, e, c, f, h, i, g 
• Ordem simétrica (esquerda, raiz, 
direita) 
– d, b, e, a, h, f, i, c, g 
• Pós-ordem (esquerda, direita, raiz) 
– d, e, b, h, i, f, g, c, a 
a 
b 
d e 
h i 
f 
c 
g 
• As estratégias de percurso não são exclusivas das 
árvores binárias, podemos usá-las em árvores com mais 
de dois filhos por nó. 
Exercício 
• Na árvore a seguir, qual seria a ordem que os nós 
seriam escritos para os percursos, pré-ordem (raiz, 
esquerda, direita), ordem simétrica (esquerda, raiz, 
direita), pós-ordem (esquerda, direita, raiz). 
 
 
• Pré-ordem: 
– a, b, d, i, e, f, c, g, j, k, h 
 
• Ordem Simétrica: 
– i, d, b, e, f, a, j, g, k, c, h 
 
– Pós-ordem 
– i, d, e, f, b, j, k, g, h, c, a 
Exercício 
• Esboce uma figura para cada uma das seguintes 
árvores: 
– Árvore com 5 nós e altura 1 
– Árvore binária cheia de altura 2 
– Árvore de altura 3 onde cada nó de profundidade i 
tem i + 1 filhos. 
• Desenhe a árvore que representa a expressão 
[ (2 * x – 3 * y ) + 4 * z ] + 1 
Exercício 
• Esboce uma figura para cada uma das seguintes 
árvores: 
– Árvore com 5 nós e altura 1 
– Árvore binária cheia de altura 2 
– Árvore de altura 3 onde cada nó de profundidade i 
tem i + 1 filhos. 
Exercício 
• Esboce uma figura para cada uma das seguintes 
árvores: 
– Árvore com 5 nós e altura 1 
– Árvore binária cheia de altura 2 
– Árvore de altura 3 onde cada nó de profundidade i 
tem i + 1 filhos. 
Exercício 
• Esboce uma figura para cada uma das seguintes 
árvores: 
– Árvore com 5 nós e altura1 
– Árvore binária cheia de altura 2 
– Árvore de altura 3 onde cada nó de profundidade i 
tem i + 1 filhos. 
Desenhe a árvore que 
representa a expressão 
[ (2 * x – 3 * y ) + 4 * z ] + 1