Isomorﬁsmos de Grafos, Grafos Planares e Árvoresesdras/matdisc/aula_grafos.pdf · 2008-06-13 · Teorema 1 Dois grafos simples (N1,A1,g1) e ... Grafos Planares-Fórmula de Euler

Isomorfismos de Grafos,Grafos Planares e

Árvores

Esdras Medeiros

– p. 1/25

Isomorfismo de Grafos

Os isomorfismos preservam adjacências entrevértices.

– p. 2/25


Definição 1 Dois grafos (N1, A1, g1) e (N2, A2, g2) sãoisomorfos se existem funções f1 : N1 → N2 ef2 : 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

a2a3

a4

a5

a6a7

a8

a

c

b

de

e5 e6e1

e4

e7

e8

e2

– p. 3/25


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


Teorema 1 Dois grafos simples (N1, A1, g1) e(N2, A2, g2) são isomorfos se existe f1 : N1 → N2 ondequaisquer n1, n2 ∈ N1 são adjacentes se, e somentese, f(n1), f(n2) são adjacentes.

– p. 5/25


Pode-se mostrar que grafos não são isomorfosatravé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


Exemplo: Mostre que os grafos abaixo não sãoisomorfos.

– p. 7/25

Grafos Planares

Definição 2 Um grafo é planar quando pode serrepresentado em uma folha de papel, de modo queseus arcos se intersectem apenas em nós.

O grafo à esquerda é planar pois é isomorfo ao grafoà direita que é planar. Em grafos planares além denós e arcos também há regiões planares . No casoacima existem 4 regiões.

– p. 8/25

Grafos Planares-Fórmula de Euler

Em todo grafo planar vale a fórmula de EulerN − A + R = 2, onde N é o número de vértices, A é onúmero de arestas e R é o número de regiõesdivididas no plano pelo grafo. Exemplo:

N = 13, A = 19 e R = 8. Logo 13 − 19 + 8 = 2.– p. 9/25


Demonstração: Façamos indução sobre o número dearcos A.I) A = 1.

(a) (b)

II)Suponha que seja válido para uma grafo qualquercom K arcos.

III)Vamos provar que vale para um grafo qualquer comK + 1 arcos.

– p. 10/25


Temos dois casos:Caso 1: O grafo tem um nó de grau 1.

Apagando temporariamente o arco e o nó valeN − K + R = 2.

Colocando de volta o arco e o nó vale(N + 1) − (k + 1) + R = 2

– p. 11/25


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 - DuasDesigualdades

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 emrelação ao número de nós.

– p. 13/25


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 deresolver o problema da água, luz e telefone.

– p. 14/25


Observe o grafo abaixo:

Nesse grafo A = 9, N = 6 e não há ciclos detamanho 3. Logo não satisfaz a desigualdade 2A ≤ 2N − 4 pois 9 > 2(6) − 4.

– p. 15/25

Árvores

Definição 3 Uma árvore é um grafo conexo acíclicocom um nó especial, denominado raiz da árvore.Exemplos:

r

– p. 16/25

Árvores-Terminologia

T2

raizR

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 é ocomprimento 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 nomáximo dois filhos, filho esquerdo e filho direito .

• Uma árvore estritamente binária é uma árvorebinária em que cada nó tem 0 ou 2 filhos.

• Uma árvore binária cheia é uma árvore em quese um nó tem alguma sub-árvore vazia então eleestá no último nível.

• Uma árvore completa é aquela em se n é um nócom algumas de sub-árvores vazias, então n selocaliza no penúltimo ou no último nível.

Portanto, toda árvore cheia é completa e estritamentebiná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−ReitorAdministrativoAcademico

Vice−Reitor

Diretor Humanas

Diretor DiretorSaude

DiretorCiencias Engenharias

ChefeCienciaComputacao

CoordenadorCienciaComputacao

ProfessorCiencia

– p. 21/25

Árvores binárias-AplicaçõesDiretó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

Documents

Isomorﬁsmos de Grafos, Grafos Planares e Árvoresesdras/matdisc/aula_grafos.pdf · 2008-06-13 · Teorema 1 Dois grafos simples (N1,A1,g1) e ... Grafos Planares-Fórmula de Euler