– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 1

Teoria dos Grafos

Aula 2 – Definições, Conceitos Básicos e Representação Interna de Grafos

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 2

Definições

• Dois tipos de elementos:– Vértices ou nós.– Arestas.

v3

v2v4v1

v5 v6

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 3

Grafo Simples

• G = (V, E)• V é um conjunto finito não-vazio de

vértices.• E é um conjunto finito de arestas.• Se e Є E, é um conjunto da forma:

– e = { v, w} = vw = wv, onde v,w Є V.

• e é incidente a v e w.• v e w são adjacentes ou vizinhos.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 4

Grafo Simples

v3

v2v4v1

v5 v6

e1

V = {v1, v2, v3, v4, v5, v6}

E = {v1v2, v1v3, v2v3, v2v4, v2v5, v3v4}

e1 é incidente a v2 e v5

v1, v3, v4 e v5 são adjacentes a v2

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 5

Graus de Vértices• Grau de um vértice v (deg(v)) é o número

de arestas que incidem em v.– Vértice ímpar.– Vértice par.– Vértice isolado.

• Um grafo é regular (k-regular) se todos os seus vértices tem o mesmo grau (k).

• Seqüência de graus de um grafo consiste em escrever em ordem crescente os graus de seus vértices.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 6

Graus de Vértices

v3

v2v4v1

v5 v6

e1

v6 é um vértice isolado. deg(v6) = 0

v2 é um vértice par. deg(v2) = 4

v5 é um vértice ímpar. deg(v5) = 1

Seqüência de graus = 0, 1, 2, 2, 3, 4

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 7

Outros Tipos de Grafos• Pseudo-grafos:

– Multigrafos.– Grafos com auto-laços.

• Grafos dirigidos.• Não existe terminologia padronizada.

Vamos usar o termo grafo para representar grafos finitos, não dirigidos, com auto-laços e múltiplas arestas.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 8

v3

v2v4v1

v5 v6

e1

Auto-laço

Multigrafo

deg(v4) = 4deg(v3) = 5

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 9

Proposições Importantes• A partir do conceito de adjacência e graus

de vértices.• Prova é intuitiva.• Como conseqüência: número de vértices

ímpares é par.

Proposição de Euler: ∑i=1

n

deg vi =2∣E∣

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 10

v3

v2v4v1

v5 v6

Σ deg(vi) = 2 + 4 + 3 + 2 + 1 + 0 = 12 = 2 x 6

№ de vértices ímpares = 2 = v3 e v5

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 11

Isomorfismo de Grafos

• Dois grafos são isomórficos:– São essencialmente iguais.– Correspondência entre os vértices e arestas.

• Sejam G1= (V1, E1) e G2 = (V2, E2):– G1 ≈ G2, se existir uma bijeção f: V1 → V2:

• Se vw é uma aresta de E1, então f(v)f(w) é aresta de E2.

• Toda aresta em E2 tem a forma de f(v)f(w) para alguma aresta vw єE1.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 12

Isomorfismo de Grafos

u v w

x y z

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 13

Isomorfismo de Grafos

u v w

x y z

f(u) = azul, f(v) = roxo, f(w) = vermelhof(x) = verde, f(y) = amarelo, f(z) = rosa

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 14

Isomorfismo de Grafos

• Isomorfismo preserva:– Simetria: G1 ≈ G2 ↔ G2 ≈ G1.– Reflexividade: G ≈ G.– Transitividade: G1 ≈ G2 e G2 ≈ G3 → G1 ≈ G3.

• Proposições válidas se G1 ≈ G2:– G1 e G2 têm o mesmo número de vértices.– G1 e G2 têm a mesma seqüência de graus.– G1 e G2 têm o mesmo número de arestas.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 15

Subgrafos

• G1 = (V1, E1) é subgrafo de G2 = (V2, E2) sss:– V1 é subconjunto de V2; e,– E1 é subconjunto de E2.

• Subgrafos podem ser obtidos através da remoção de arestas e vértices.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 16

Subgrafos

u w

x y z

u v w

x y z

u v w

x y z

G1 G2 G3

G2 = G1 \ {uz}G3 = G1 \ {v}

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 17

Grafos Completos e nulos

• Grafo nulo é aquele em que E = Ø.• Um grafo simples é completo se qualquer

par de vértices distintos é adjacente.– Grafo completo de n vértices é dito Kn.

K3

K4

K5

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 18

Grafos Bipartidos

• Grafo bipartido é aquele em que V pode ser dividido em dois subconjuntos disjuntos não vazios V1 e V2.– Cada aresta conecta um vértice de V1 e um

vértice de V2.

• Grafo bipartido completo: cada um dos elementos de V1 é adjacente a cada um dos elementos de V2.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 19

Grafos Bipartidos

u v w

x y z

K3,3

V1 = {u, v, w}V2 = {x, y, z}

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 20

Complemento de um Grafo

• Seja G um grafo simples:– G é complemento de G se:

• V = V; e,• Dois vértices são adjacentes em G se e somente se

eles não são adjacentes em G.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 21

Representação de Grafos

• Representação gráfica:– Útil na prática.– Não é adequada para representar internamente

(em um computador) dados sobre a estrutura de grafos.

• Várias formas de representar um grafo:1) Listas de Adjacência.2) Matriz de Adjacência.3) Matriz de Incidência.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 22

Listas de Adjacência

• Consiste de um array Adj de |V| listas, um para cada vértice de V.

• Para cada u em V, Adj[u] consiste de todos os vértices de G adjacentes a u.

• Vértices armazenados de forma arbitrária na lista.

• Também pode ser utilizada no caso de grafos dirigidos.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 23

Exemplo

1

3

45

2 52

51

42

23

41

3 4

5

2

1

2

3

4

5

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 24

Exemplo

1 3

54

2 42

5

56

2

4

1

2

3

4

5

6

66

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 25

Lista de Adjacência• Forma compacta de representar grafos

esparsos.• Se G é um grafo dirigido, a soma dos

tamanhos de todas as listas de adjacências é |V|.

• O(V + E).• Utilizada com outras tipos de grafos.• Ineficiente para determinar se vw está no

grafo.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 26

Matriz de Adjacência• Requer que os vértices sejam numerados

arbietrariamente de 1, 2, ..., |V|.

• Matriz A= (aij), de ordem |V| x |V|:

– aij = 1, se (i, j) Є E

– aij = 0, caso contrário

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 27

Exemplo

1

3

45

2

0 1 0 0 11 0 1 1 1

0 1 1 0 10 1 0 1 0

1 1 0 1 0

1 2 3 4 512345

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 28

Exemplo

1 3

54

2

6

0 1 0 1 0 00 0 0 0 1 0

0 1 0 0 0 00 0 0 0 1 1

0 0 0 1 0 0

1 2 3 4 5 6 123456 0 0 0 0 0 1

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 29

Matriz de Adjacência• Preferível em grafos pequenos.• Requer apenas um bit por entrada.• Válido também com outros tipos de grafos.

Exemplo: grafos ponderados.• O(V2).

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 30

Matriz de Incidência• Matriz B= (b

ij), de ordem |V| x |E|:

– bij = 1, se vértice v

i e aresta e

j forem incidentes

– bij = 0, caso contrário

1

3

45

2

1 1 0 0 0 0 00 1 1 0 1 1 0

0 0 0 1 1 0 10 0 0 0 0 1 1

1 0 1 1 0 0 0

1 2 3 4 5 6 712345

e1

e2

e3

e4

e5

e6

e7

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 31

Matriz de Incidência• No caso de grafos dirigidos:

e21 3

54

2

6

0 1 0 1 0 0 0 00 -1 -1 1 0 0 0 0

-1 0 1 0 -1 0 0 00 0 0 0 1 1 0 0

0 0 0 -1 1 -1 0 0

1 2 3 4 5 6 7 8 123456 0 0 -1 0 0 0 0 0

e1 e3

e5

e4 e6 e7

e8

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 32

Verificando Isomorfismo

• Sejam A1 e A

2 as matrizes de adjacência de

G1 e G

2. Se G

1 e G

2 são isomórficos:

– PA2PT = A

1

– P é uma matriz de permutação.

Teorema: Dois Grafos são isomórficos sss seus vértices podem ser rotulados de tal forma que as correspondentes matrizes de adjacências são iguais.

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 33

Exemplo

v1 v4

v2 v3

u1 u3

u2 u4

G1 G2

0 1 0 11 0 1 00 1 0 11 0 1 0

A1=

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

A2=

– . Teoria dos Grafos Prof Jorge Figueiredo 2 - Aula 34

Exemplo

1 0 0 00 0 0 10 1 0 00 0 1 0

P =

Se fizermos: u1 → v

1; u

2 → v

3; u

3 → v

4; u

4 →v

2.

Teorema: Dois Grafos rotulados G1 e G

2, com respectivas

matrizes A1 e A

2, são isomórficos sss A

2 = PA

1PT, para

alguma matriz de permutação P.