CC/EC/Mestrado Teoria dos Grafos UFES

Representação de Grafos

CC/EC/Mestrado Teoria dos Grafos UFES

Representação de Grafos

• Por diagrama: mais usual e mais fácil de visualização de aspectos topológicos– Percursos em grafos, adjacências, etc.

• Percepção de propriedades pode ser facilitada ou dificultada de acordo com o aspecto visual de um grafo– Isomorfismos, planaridade

• Representação visual: não adequada para o computador– Como armazenar a estrutura de um grafo?

CC/EC/Mestrado Teoria dos Grafos UFES

Representações mais usuais

• Lista de adjacência ou dicionário– Simples– Lista de listas de vértices– Cada lista: formada por um vértice e seus

adjacentes– Adequada na representação de grafos

esparsos– Ineficiente na busca de uma aresta no grafo

CC/EC/Mestrado Teoria dos Grafos UFES

Lista de adjacência - exemplo

1

2 3

4

1 2 4 •

1

2 4

1 3

3 •

4 •

3 •

2

1

3

4

a

e

b c

d

b c e •

a

a b

b

c •

d •

c •

b

a

c

d

e

d •

e •

a • c •

CC/EC/Mestrado Teoria dos Grafos UFES

Lista de adjacência

• A lista associada a um vértice pode ser vazia.

• Em grafos não orientados, pode-se evitar a repetição na representação de arestas adotando-se algum critério de ordenação.

CC/EC/Mestrado Teoria dos Grafos UFES

Matriz de Adjacência

• Seja G = (V,E)

• A = (aij), 1 ≤ i,j ≤ n

• aij = 1, quando {i,j} E

0, caso contrário

CC/EC/Mestrado Teoria dos Grafos UFES

Matriz de Adjacência

a

e

b c

d

0 1 1 0 1

1 0 1 1 0

1 1 0 1 1

0 1 1 0 0

1 0 1 0 0

a b c d e

a

b

c

e

d

CC/EC/Mestrado Teoria dos Grafos UFES

Matriz de Adjacência

Diagonal principal nula:

Matriz simétrica:

Número de 1´s na matriz = (grafo simples)

Valores nulos: ausência de arestas

Valores não nulos: presença de arestas ou arcos

grafos sem laços

grafo não orientado

2m

CC/EC/Mestrado Teoria dos Grafos UFES

Matriz de Incidência

• Seja G = (V,E)

• B = (bkl), 1 ≤ k ≤ n, 1 ≤ l ≤ m

• bkl = 1, quando o vértice k é incidente à

aresta l

0, caso contrário

CC/EC/Mestrado Teoria dos Grafos UFES

Matriz de Incidência

a

e

b c

d

{a,b} {a,c} {a,e} {b,c} {b,d} {c,d} {c,e}

1 1 1 0 0 0 0

1 0 0 1 1 0 0

0 1 0 1 0 1 1

0 0 0 0 1 1 0

0 0 1 0 0 0 1e

a

b

c

d

CC/EC/Mestrado Teoria dos Grafos UFES

Matriz de Incidência• Matriz esparsa de dimensão nxm• Exige muito espaço de armazenamento• Número de 1´s na matriz = 2m• Representa exatamente um grafo• Cada linha corresponde a um vértice• Cada coluna corresponde a uma aresta• Mais utilizada para representação de

hipergrafos e programação inteira envolvendo estruturas de grafos

CC/EC/Mestrado Teoria dos Grafos UFES

Questão

• Qual das representações computacionais de um grafo é a mais adequada?

CC/EC/Mestrado Teoria dos Grafos UFES

Exercícios• Considere o grafo G e construa:

– sua lista de adjacência

– sua matriz A de adjacência

– sua matriz B de incidência

– Calcule:

• O produto A2. O que significam os números na diagonal?

• O produto B.Bt.O que significam os números na diagonal? E fora da diagonal?

• Existe relação entre a matriz de adjacência de um grafo G e a matriz de adjacência do seu grafo complementar G?

a

b c

d

UFES

Percursos em um grafo

UFES

Definição

• Um percurso ou cadeia é uma seqüência de arestas sucessivamente adjacentes, cada uma tendo uma extremidade adjacente à anterior e a outra a subsequente (à exceção da primeira e da última)– Percurso fechado: a última aresta da

sucessão é adjacente a primeira;– Percurso aberto: caso contrário

UFES

Notação

• A sucessão é indicada por:– Vértices– Arestas– Vértices e arestas alternados

UFES

Exemplo

e

G

a

b

c

d

UFES

Comprimento de um percurso

• Número de arestas por ele utilizado (incluindo repetições)

• O que é o comprimento de um percurso em um grafo valorado?

UFES

Tipos de percurso

• Simples: não repete arestas

• Elementar: não repete vértices nem arestas (caminho)

• Ciclo: percurso simples e fechado

• Ciclo elementar: só há repetição do último vértice

• Uma corda é uma aresta que une dois vértices não consecutivos de um ciclo

UFES

Percurso abrangente

• Um percurso é abrangente a um dos conjuntos do grafo quando utiliza todos os elementos desse conjunto ao menos uma vez

• Euleriano

• Hamiltoniano

UFES

Exercícios• Indique percursos simples e não simples em G

1

• Indique percursos elementares em G2

• Todo percurso elementar é simples. Todo percurso simples é elementar? Explique.

• Indique um ciclo em G1 e um ciclo elementar em G

2

• Indique um caminho de comprimento 4 em G2 e um percurso de

comprimento 6 em G2

G2

a

b

G1

a

b c

d

e

ca b

d e 2