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
a
c
b
d
e
4
•
4
4
•
3
3
•
1
1
2
2
1
3
3
2
4
1
a
b
c
b
a
c
c
a
b
d
b
c
e
a
•
c
•
e
•
d
d
•
•
•
e
•
•
•
E se for um digrafo?
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
a
b
c
d
e
a
0
1
1
0
1
b
1
0
1
1
0
c
1
1
0
1
1
d
0
1
1
0
0
e
1
0
1
0
0
c
b
d
e
CC/EC/Mestrado
Teoria dos Grafos
UFES
Matriz de Adjacência
a
a
b
c
d
e
a
0
1
1
0
1
b
1
0
1
1
0
c
1
1
0
1
1
d
0
1
1
0
0
e
1
0
1
0
0
c
b
d
e
CC/EC/Mestrado
Teoria dos Grafos
UFES
Matriz de Adjacência
Diagonal principal nula: grafos sem laços
grafo não orientado
Matriz simétrica:
Número de 1´s na matriz = 2m (grafo
simples)
Valores nulos: ausência de arestas
Valores não nulos: presença de arestas ou
arcos
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,b} {a,c} {a,e} {b,c} {b,d} {c,d} {c,e}
a
c
b
d
e
CC/EC/Mestrado
a
1
1
1
0
0
0
0
b
1
0
0
1
1
0
0
c
0
1
0
1
0
1
1
d
0
0
0
0
1
1
0
e
0
0
1
0
0
0
1
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:
a
c
b
–
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?
d
Existe relação entre a matriz de adjacência de um grafo G e a
matriz de adjacência do seu grafo complementar G?
CC/EC/Mestrado
Teoria dos Grafos
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
G
a
c
e
b
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 G1
• Indique percursos elementares em G2
• Todo percurso elementar é simples. Todo percurso simples é
elementar? Explique.
• Indique um ciclo em G1 e um ciclo elementar em G2
• Indique um caminho de comprimento 4 em G2 e um percurso de
comprimento 6 em G2
G1
b
d
a
c
a
d
b
c
e
G22
e
UFES