aula_grafos

Prévia do material em texto

Isomorfismos de Grafos,
Grafos Planares e
Árvores
Esdras Medeiros
– p. 1/25
Isomorfismo de Grafos
Os isomorfismos preservam adjacências entre
vértices.
– p. 2/25
Isomorfismo de Grafos
Definição 1 Dois grafos (N1, A1, g1) e (N2, A2, g2) são
isomorfos se existem funções f1 : N1 → N2 e
f2 : A1 → A2 tais que, para cada arco a ∈ A1,
g1(a) = x− y se, e somente se, g2[f2(a)] = f1(x)− f2(y).
e3
1
2
3
4
5
a1
a2
a3
a4
a5
a6
a7
a8
a
c
b
d
e
e5 e6e1
e4
e7
e8
e2
– p. 3/25
Isomorfismo de Grafos
Isomorfismo encontrado:
f1 : 1→ c f2 : a1 → e1
2→ e a2 → e4
3→ d a3 → e2
4→ b a4 → e3
5→ a a5 → e8
a6 → e7
a7 → e5
a8 → e6
– p. 4/25
Isomorfismo de Grafos
Teorema 1 Dois grafos simples (N1, A1, g1) e
(N2, A2, g2) são isomorfos se existe f1 : N1 → N2 onde
quaisquer n1, n2 ∈ N1 são adjacentes se, e somente
se, f(n1), f(n2) são adjacentes.
– p. 5/25
Isomorfismo de Grafos
Pode-se mostrar que grafos não são isomorfos
através de invariantes como:
• Número de nós;
• Número de arcos;
• Existência de arcos paralelos;
• Existência de laços;
• Existência de um nó com grau diferente;
• Conexidade;
• Existência de ciclos;
– p. 6/25
Isomorfismo de Grafos
Exemplo: Mostre que os grafos abaixo não são
isomorfos.
– p. 7/25
Grafos Planares
Definição 2 Um grafo é planar quando pode ser
representado em uma folha de papel, de modo que
seus arcos se intersectem apenas em nós.
O grafo à esquerda é planar pois é isomorfo ao grafo
à direita que é planar. Em grafos planares além de
nós e arcos também há regiões planares . No caso
acima existem 4 regiões.
– p. 8/25
Grafos Planares-Fórmula de Euler
Em todo grafo planar vale a fórmula de Euler
N − A+ R = 2, onde N é o número de vértices, A é o
número de arestas e R é o número de regiões
divididas no plano pelo grafo. Exemplo:
N = 13, A = 19 e R = 8. Logo 13− 19 + 8 = 2.
– p. 9/25
Grafos Planares-Fórmula de Euler
Demonstração: Façamos indução sobre o número de
arcos A.
I) A = 1.
(a) (b)
II)Suponha que seja válido para uma grafo qualquer
com K arcos.
III)Vamos provar que vale para um grafo qualquer com
K + 1 arcos.
– p. 10/25
Grafos Planares-Fórmula de Euler
Temos dois casos:
Caso 1: O grafo tem um nó de grau 1.
Apagando temporariamente o arco e o nó vale
N −K +R = 2.
Colocando de volta o arco e o nó vale
(N + 1)− (k + 1) +R = 2
– p. 11/25
Grafos Planares-Fórmula de Euler
Caso 2: O grafo não tem nós de grau 1.
Apagando temporariamente o arco vale N −K +R = 2.
Colocando de volta o arco vale N − (k+1)+ (R+1) = 2.
– p. 12/25
Grafos Planares - Duas
Desigualdades
Desigualdade 1:
Temos que em qualquer grafo vale
2A ≥ 3R
usando que N − A+ R = 2, temos
2A ≥ 3(2−N + A) = 6− 3N + 3A
2A ≤ 3N − 6
Fato importante: O número de de arestas é linear em
relação ao número de nós.
– p. 13/25
Grafos Planares - Duas
Desigualdades
Desigualdade 2:
Em grafos sem ciclos de comprimento 3 vale
2A ≥ 4R
usando que N − A+ R = 2, temos
2A ≥ 4(2−N + A) = 8− 4N + 4A
A ≤ 2N − 4
Com isso podemos mostrar a impossibilidade de
resolver o problema da água, luz e telefone.
– p. 14/25
Grafos Planares - Duas
Desigualdades
Observe o grafo abaixo:
Nesse grafo A = 9, N = 6 e não há ciclos de
tamanho 3. Logo não satisfaz a desigualdade 2
A ≤ 2N − 4 pois 9 > 2(6)− 4.
– p. 15/25
Árvores
Definição 3 Uma árvore é um grafo conexo acíclico
com um nó especial, denominado raiz da árvore.
Exemplos:
r
– p. 16/25
Árvores-Terminologia
T2
raiz
R
R3R2R1
• T2 é sub-árvore
• R é nó pai de R1, R2 e R3.
• R1, R2 e R3 são nós filhos de R.
– p. 17/25
Árvores-Terminologia
• A profundidade de um nó em uma árvore é o
comprimento do caminho da raiz ao nó.
• A profundidade (altura ou nível) de uma árvore
é a maior profundidade dos nós na árvore.
• Uma folha é um nó sem filhos.
• Nós internos são nós que não são folhas.
• Floresta é um grafo acíclico não necessariamente
conexo
– p. 18/25
Árvores binárias
Definição 4 Em uma árvore binária cada nó tem no
máximo dois filhos, filho esquerdo e filho direito.
• Uma árvore estritamente binária é uma árvore
binária em que cada nó tem 0 ou 2 filhos.
• Uma árvore binária cheia é uma árvore em que
se um nó tem alguma sub-árvore vazia então ele
está no último nível.
• Uma árvore completa é aquela em se n é um nó
com algumas de sub-árvores vazias, então n se
localiza no penúltimo ou no último nível.
Portanto, toda árvore cheia é completa e estritamente
binária.
– p. 19/25
Árvores binárias
Exemplos:
CheiaEstritamente Binaria Completa
– p. 20/25
Árvores binárias-Aplicações
Fluxo Organizacional:
Computacao
Reitor
Presidente
Vice−Reitor
AdministrativoAcademico
Vice−Reitor
Diretor 
Humanas
Diretor Diretor
Saude
Diretor
Ciencias Engenharias
Chefe
Ciencia
Computacao
Coordenador
Ciencia
Computacao
Professor
Ciencia
– p. 21/25
Árvores binárias-Aplicações
Diretórios:
– p. 22/25
Árvores binárias-Aplicações
Expressões Algébricas:
32 y
+
x
*
−
A expressão correspondente é (2 + x)− (y ∗ 3).
– p. 23/25
Lendo arquvos em C
Abrindo um arquivo:
#include <stdio.h>
int main()
{
FILE *fp;
fp = fopen ("MEU_ARQUIVO", "r");
if (fp == NULL) {
printf ("Houve um erro ao abrir o arquivo.\n");
return 1;
}
printf ("Arquivo MEU_ARQUIVO criado com sucesso.\n");
fclose (fp);
return 0;
}
– p. 24/25
Lendo arquvos em C
Lendo letra por letra:
#include <stdio.h>
int main(){
FILE *entrada, *saida;
int letra;
int str[100];
int i=0;
entrada = fopen("arquivo1", "r"); //abre para leitura!
while((letra = fgetc(entrada)) != EOF){ //le arquivo1
str[i] = letra; //armazena string no vetor str
i++;
}
fclose(entrada);
}
– p. 25/25
	Isomorfismo de Grafos
	Isomorfismo de Grafos
	Isomorfismo de Grafos
	Isomorfismo de Grafos
	Isomorfismo de Grafos
	Isomorfismo de Grafos
	Grafos Planares
	Grafos Planares-Fórmula de Euler
	Grafos Planares-Fórmula de Euler
	Grafos Planares-Fórmula de Euler
	Grafos Planares-Fórmula de Euler
	Grafos Planares - Duas Desigualdades
	Grafos Planares - Duas Desigualdades
	Grafos Planares - Duas Desigualdades
	Árvores
	Árvores-Terminologia
	Árvores-Terminologia
	Árvores binárias
	Árvores binárias
	Árvores binárias-Aplicações
	Árvores binárias-Aplicações
	Árvores binárias-Aplicações
	Lendo arquvos em C
	Lendo arquvos em C