Teoria dos Grafos - Uma introdução

DefinicoesClassificacao

Conceitos relacionadosInter-relacoes e quantificacao de grafos

Inter-relacoes e caractersticas de vertices e arestasClassificacao de grafos quanto a suas caractersticas

Representacoes matriciais de grafosReferencias

Uma introducao a teoria dos grafos

Teoria dos GrafosUma Introducao

Claudia Cavalcante FonsecaOrientacao: Elisa Canete

Universidade Federal de Alagoas

20 de setembro de 2014

1 / 23





Topicos

1 DefinicoesPrimeiras DefinicoesExemplos

2 ClassificacaoQuanto a orientacaoQuanto ao valor

3 Conceitos relacionadosRedundanciasCaminhos

MedidasCiclos

4 Inter-relacoes e quantificacao de grafosSubgrafos

Quantificacao

5 Inter-relacoes e caractersticas de vertices e arestasRelacoes entre Arestas e verticesInter-relacoes e caractersticas de vertices

6 Classificacao de grafos quanto a suas caractersticasQuanto a qualidade dos caminhosQuanto a presenca de ciclosQuanto a disposicao das arestas

7 Representacoes matriciais de grafosMatriz de incidenciaMatriz de AdjacenciaO teorema das 4 cores

2 / 23





Primeiras DefinicoesExemplos

Primeiras Definicoes

Teoria dos Grafos

Estuda as relacoes entre objetos de um conjunto

Grafo

Um Grafo e uma dupla G(V ,A) de conjuntos tais que:

1 V = {V1,V2,V3, ...,Vm}, cujos elementos,chamados vertices, sao os objetos a seremestudados

2 A = {a1 = (Vi1,Vj1), a2 = (Vi2,Vj2), ...,an = (Vin,Vjn)} e o conjunto de pares de verticescujos elementos sao chamados arestas erepresentam as relacoes entre os vertices.

V1 V2

V3

V4V5

V6

V = {V1,V2,V3,V4,V5,V6}A = {(V1,V6), (V1,V2), (V1,V3), (V2,V3), (V2,V6),(V3,V4), (V3,V5)}

3 / 23





Primeiras DefinicoesExemplos

Exemplos

Figura: Exemplos de Grafos

4 / 23





Quanto a orientacaoQuanto ao valor

Grafo Nao Orientado

Nao Direcionado, Nao Orientado (ou simplesmenteGrafo)

Suas arestas sao duplas de vertices nao orientadas(Vi ,Vj ) = (Vj ,Vi )

Example

Rotas entre aeroportos, amizades no facebook.

A

B

C

D

E

5 / 23






Grafo Orientado

Direcionado, Orientado, Quiver ou Dgrafo

Suas arestas sao pares ordenados.Graficamente, possuem uma direcao associada.(Vi ,Vj ) 6= (Vj ,Vi )

Example

Links em websites, Seguidores no Twitter.

A

B

C

D

E

6 / 23






Grafo Ponderado

Grafo Ponderado ou Valorado

Um grafo munido de uma funcao (chamada custo)f : A R ou f : V R que a cada aresta ou verticerelaciona um numero real.

Example

Rotas entre cidades, passagens de aviao (Google Maps,O problema do caixeiro viajante).

A

B

C

D

E

2

2

3

5

2

3

7 / 23





RedundanciasCaminhos

Conceitos relacionados

Loop/Laco

Uma aresta (Vi ,Vj ) tal que Vi = Vj .Ex.: Um curto-circuito num circuito eletrico

A B

C

Arestas Paralelas

Duas arestas (U1,U2) e (V1,V2) tais que U1 = V1 eU2 = V2 ou U1 = V2 e U2 = V1.Ex.: A Via Expressa e a Av. Fernandes Lima.

AB

8 / 23






Caminhos

Caminho/Passeio

Uma sequencia de vertices e arestas intercalados da seguinteforma:V1, a1 = (V1,V2),V2, a2 = (V2,V3), ...,Vn1, an1 =(Vn1,Vn),Vn

Caminho Elementar/Caminho

Um caminho cujo conjunto de vertices nao possui elementosrepetidos.

Caminho Simples/Trajeto

Um caminho cujo conjunto de arestas nao possui elementosrepetidos.

A B

C

D E

F

G

9 / 23






Medidas em caminhos

Comprimento de um caminho

Quantidade de arestas de um caminho

Custo de um caminho

Em um grafo ponderado, o custo do caminho e a soma doscustos das arestas

A B

C

D E2

25

2

3

F

1

3

G

3

2

2

6

10 / 23






Caminhos: Ciclos

Ciclo

Um caminho cujo primeiro vertice coincide com o ultimo.

Example

Ciclos de comprimento igual a 1 sao lacos.

Example

Ciclos simples ou Circuitos sao ciclos de caminhos simplescom comprimento maior ou igual a 3.

A B

CD E2

2 5

2

3

F

1

3

G

3

2

2

6

11 / 23





SubgrafosQuantificacao

Subgrafos

Subgrafo de um grafo G(VG ,AG )

E um grafo H(VH ,AH) tal que VH VG e AH AG

Subgrafo induzido de um grafo G(VG ,AG )

E um grafo H(VH ,AH), subgrafo de G(VG ,AG ), tal queA,B VH , (A,B) AH (A,B) AG

A B

C

DE

F

G H

I

J

a b

c

d

e

f

g

h

i

j

k

12 / 23





SubgrafosQuantificacao

Dimensao e Ordem

Dimensao de um grafo G

Quantidade de arestas pertencentes a G

Ordem de um grafo G

Quantidade de vertices pertencentes a G

A B

E

H

J

13 / 23





Relacoes entre Arestas e verticesInter-relacoes e caractersticas de vertices

Relacoes entre arestas e vertices

Extremidades de uma aresta

Cada um dos dois vertices que pertencem a aresta.

Arestas incidentes a um vertice A VGArestas tais que A e uma de suas extremidades.

A

BC

D

EF

H

J

14 / 23






Inter-relacoes e caractersticas de vertices

Grau ou valencia de um vertice

Quantidades de arestas incidentes a ele.

A soma dos graus dos vertices de um grafo G(VG ,AG ) com VG = {V1,V2, ...,Vn} e

dada por:n

i=1grau(Vi ) = 2dim(G).

Example

Vertices de grau 0 e 1 sao chamados, respectivamente, isolados e folha.

Example

Lema do aperto de maos

A

B

C

D

E

F

H

J

15 / 23






Inter-relacoes e caractersticas de vertices

Vertices adjacentes

Vertices U e V tais que existe uma aresta (U,V ) ou (V ,U)

Example

O subgrafo induzido que contem todos os vertices adjacentes ao vertice V echamado Adjacencia ou Vizinhanca de V .

A

B

C

D

E

F

H

J

16 / 23





Quanto a qualidade dos caminhosQuanto a presenca de ciclosQuanto a disposicao das arestas

Tipos de Grafos

Grafo Simples

Grafo nao direcionado, sem lacos e sem arestas paralelas.

A B

C

D

E

F

H

J

Grafo Completo

Grafo simples em que ha todas as arestas possveisA B

E

H

J

17 / 23






Tipos de Grafos

Grafo Cclico

Def 1.: Grafo formado por, apenas, um cicloDef 2.: Grafo que possui, pelo menos, um ciclo.

A B

E

H

J

Grafo Acclico

Nao possui ciclosA B

D

E

H

J

18 / 23






Tipos de Grafos

Arvore

Grafo simples, acclico e conexo

A B

C

D

E

F

G

H

J

Grafo Plano

Grafo cujas arestas nao se cruzam

Example

Problema das 4 cores

A B

C

D

EE

F

H

J

19 / 23





Matriz de incidenciaMatriz de AdjacenciaO teorema das 4 cores

Matriz de incidencia

Considere um grafo G(VG ,AG ) com n vertices e m arestas.

Matriz de incidencia

Matriz n m tal que cada elemento aij indica se a j-esima aresta incide sobre o i-esimo vertice.

Example

A

B

D

C

b

c

d

a

e

f

a b c d e fA 1 1 1 0 0 0B 0 0 1 0 0 0C 0 0 0 1 1 1D 0 1 0 1 1 0

20 / 23






Matriz de Adjacencia

Considere um grafo G(VG ,AG ) com n vertices V = v1, v2, ..., vn e m arestas.

Matriz de Adjacencia

Matriz n n tal que aij = 1 se a aresta (vi , vj ) e aij = 0 caso isto nao ocorra.Obs.: No caso de grafos ponderados e sem arestas paralelas, aij pode indicar o peso da aresta existente.

Example

A

B

D

CA B C D

A 1 1 0 1B 1 0 1 0C 0 1 0 1D 1 0 1 0

21 / 23






Quantas cores, no mnimo, se usa para pintar qualquer mapa continental no mundo?

Qual o numero cromatico destegrafo?

E B

D

F

A

C

Relacao entre o numero cromatico e os autovalores da matriz deadjacencia:

1 maxmin

x 1 + max

Sua matriz de adjacencia:

0 1 0 0 1 11 0 1 0 0 10 1 0 1 0 10 0 1 0 1 11 0 0 1 0 11 1 1 1 1 0

Polinomio Caracterstico: 6 104 103 + 102 + 8 5Autovalores:1.6180,1.6180,1.4495, 0.6180, 0.6180, 3.4495max = 3.4495;min = 1.61803.1319 x 4.4495 x = 4

22 / 23





Referencias

Aderito, A. (n.d.), As pontes de konigsberg - universidade de coimbra. URLhttp://www.mat.uc.pt/~alma/escolas/, [Online; accessed 13-setembro-2014].

Malta, G. H. S. (n.d.), Grafos no ensino medio: uma insercao possvel. URLhttp://www.lume.ufrgs.br/handle/10183/14829, [Online; accessed 13-setembro-2014].

Wikipedia (2014a), Four color theorem wikipedia, the free encyclopedia. URLhttp://en.wikipedia.org/w/index.php?title=Four_color_theorem&oldid=625252562, [Online; accessed13-September-2014].

Wikipedia (2014b), Problema do caixeiro-viajante wikipedia, a enciclopedia livre. URLhttp://pt.wikipedia.org/w/index.php?title=Problema_do_caixeiro-viajante&oldid=39653933,[Online; accessed 13-setembro-2014].

Wikipedia (2014c), Teoria dos grafos wikipedia, a enciclopedia livre. URLhttp://pt.wikipedia.org/w/index.php?title=Teoria_dos_grafos&oldid=40001418, [Online; accessed13-setembro-2014].

23 / 23

http://www.mat.uc.pt/~alma/escolas/http://www.lume.ufrgs.br/handle/10183/14829http://en.wikipedia.org/w/index.php?title=Four_color_theorem&oldid=625252562http://pt.wikipedia.org/w/index.php?title=Problema_do_caixeiro-viajante&oldid=39653933http://pt.wikipedia.org/w/index.php?title=Teoria_dos_grafos&oldid=40001418

DefiniesPrimeiras DefiniesExemplos

ClassificaoQuanto orientaoQuanto ao valor

Conceitos relacionadosRedundnciasCaminhos

Inter-relaes e quantificao de grafosSubgrafosQuantificao

Inter-relaes e caractersticas de vrtices e arestasRelaes entre Arestas e vrticesInter-relaes e caractersticas de vrtices

Classificao de grafos quanto a suas caractersticasQuanto qualidade dos caminhosQuanto presena de ciclosQuanto disposio das arestas

Representaes matriciais de grafosMatriz de incidnciaMatriz de AdjacnciaO teorema das 4 cores

Documents

Teoria dos Grafos - Uma introdução