Aula04_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 4
Representação de Grafos
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Representação de Grafos
Representação de Grafos
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
A representação 
omputa
ional de um grafo (ou digrafo) deve usar uma
estrutura que:
■ 
orresponde de forma úni
a a um grafo dado;
■ pode ser armazenada e manipulada em um 
omputador.
A representação grá�
a de um grafo através do diagrama de pontos e
linhas não satisfaz a segunda 
ondição a
ima.
Vamos dis
utir a seguir algumas estruturas que satisfazem estes dois
ritérios.
Considere um grafo G(V,A) 
om n vérti
es e m arestas.
Matriz de Adja
ên
ia
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
É uma matriz n× n, denotada por X = [xij] e de�nida 
omo:
xij =
{
1 se existe uma aresta entre os vérti
es vi e vj,
0 
aso 
ontrário.
Observações:
■ É ne
essário fazer uma rotulação nos vérti
es de G.
■ A 
omplexidade em termos de espaço de memória de um algoritmo
que use uma matriz de adja
ên
ia para armazenar o grafo é O(n2).
■ Qualquer tipo de grafo pode ser armazenado nesta estrutura?
Não!
Apenas grafos que não possuam arestas paralelas.
Matriz de Adja
ên
ia
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
É uma matriz n× n, denotada por X = [xij] e de�nida 
omo:
xij =
{
1 se existe uma aresta entre os vérti
es vi e vj,
0 
aso 
ontrário.
Observações:
■ É ne
essário fazer uma rotulação nos vérti
es de G.
■ A 
omplexidade em termos de espaço de memória de um algoritmo
que use uma matriz de adja
ên
ia para armazenar o grafo é O(n2).
■ Qualquer tipo de grafo pode ser armazenado nesta estrutura? Não!
Apenas grafos que não possuam arestas paralelas.
Exemplo
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Observações
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
■ As entradas ao longo da diagonal prin
ipal de X são todas nulas se,
e somente se, o grafo não possui laços. Quando há um laço em um
vérti
e vi temos xii = 1.
Se o grafo é simples, o grau de um vérti
e é dado pela soma dos
elementos de sua linha (ou 
oluna) 
orrespondente.
Permutações de linhas e das 
olunas 
orrespondentes impli
am em
uma reordenação dos vérti
es. Portanto dois grafos simples e
são isomorfos se, e somente se, , onde é
uma matriz de permutação.
Dado uma matriz qualquer simétri
a e binária, sempre é
possível 
onstruir um grafo 
om vérti
es tal que .
Quantos elementos diferentes de zero esta matriz possui?
Observações
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
■ As entradas ao longo da diagonal prin
ipal de X são todas nulas se,
e somente se, o grafo não possui laços. Quando há um laço em um
vérti
e vi temos xii = 1.
■ Se o grafo é simples, o grau de um vérti
e é dado pela soma dos
elementos de sua linha (ou 
oluna) 
orrespondente.
Permutações de linhas e das 
olunas 
orrespondentes impli
am em
uma reordenação dos vérti
es. Portanto dois grafos simples e
são isomorfos se, e somente se, , onde é
uma matriz de permutação.
Dado uma matriz qualquer simétri
a e binária, sempre é
possível 
onstruir um grafo 
om vérti
es tal que .
Quantos elementos diferentes de zero esta matriz possui?
Observações
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
■ As entradas ao longo da diagonal prin
ipal de X são todas nulas se,
e somente se, o grafo não possui laços. Quando há um laço em um
vérti
e vi temos xii = 1.
■ Se o grafo é simples, o grau de um vérti
e é dado pela soma dos
elementos de sua linha (ou 
oluna) 
orrespondente.
■ Permutações de linhas e das 
olunas 
orrespondentes impli
am em
uma reordenação dos vérti
es. Portanto dois grafos simples G1 e G2
são isomorfos se, e somente se, X(G2) = R
−1X(G1)R, onde R é
uma matriz de permutação.
Dado uma matriz qualquer simétri
a e binária, sempre é
possível 
onstruir um grafo 
om vérti
es tal que .
Quantos elementos diferentes de zero esta matriz possui?
Observações
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
■ As entradas ao longo da diagonal prin
ipal de X são todas nulas se,
e somente se, o grafo não possui laços. Quando há um laço em um
vérti
e vi temos xii = 1.
■ Se o grafo é simples, o grau de um vérti
e é dado pela soma dos
elementos de sua linha (ou 
oluna) 
orrespondente.
■ Permutações de linhas e das 
olunas 
orrespondentes impli
am em
uma reordenação dos vérti
es. Portanto dois grafos simples G1 e G2
são isomorfos se, e somente se, X(G2) = R
−1X(G1)R, onde R é
uma matriz de permutação.
■ Dado uma matriz qualquer Q ∈ Rn×n simétri
a e binária, sempre é
possível 
onstruir um grafo G 
om n vérti
es tal que X(G) = Q.
Quantos elementos diferentes de zero esta matriz possui?
Observações
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
■ As entradas ao longo da diagonal prin
ipal de X são todas nulas se,
e somente se, o grafo não possui laços. Quando há um laço em um
vérti
e vi temos xii = 1.
■ Se o grafo é simples, o grau de um vérti
e é dado pela soma dos
elementos de sua linha (ou 
oluna) 
orrespondente.
■ Permutações de linhas e das 
olunas 
orrespondentes impli
am em
uma reordenação dos vérti
es. Portanto dois grafos simples G1 e G2
são isomorfos se, e somente se, X(G2) = R
−1X(G1)R, onde R é
uma matriz de permutação.
■ Dado uma matriz qualquer Q ∈ Rn×n simétri
a e binária, sempre é
possível 
onstruir um grafo G 
om n vérti
es tal que X(G) = Q.
■ Quantos elementos diferentes de zero esta matriz possui?
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
■ Um grafo G é des
onexo 
om dois 
omponentes G1 e G2 se, e
somente se,
X(G) =
[
X(G1) 0
0 X(G2)
]
.
O que representa a matriz ? Os elementos ,
representam o número de 
aminhos distintos de 
omprimento 2 entre
os vérti
es e . De fato:
e existe um 
aminho se , e o 
aminho é dado por
.
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
■ Um grafo G é des
onexo 
om dois 
omponentes G1 e G2 se, e
somente se,
X(G) =
[
X(G1) 0
0 X(G2)
]
.
■ O que representa a matriz B = X2? Os elementos bij, i 6= j,
representam o número de 
aminhos distintos de 
omprimento 2 entre
os vérti
es vi e vj. De fato:
bij =
n∑
k=1
xikxkj = xi1x1j + xi2x2j + . . .+ xinxnj
e existe um 
aminho se xik = xkj = 1, e o 
aminho é dado por
{i, (i, k), k, (k, j), j}.
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Teorema 1. Seja X a matriz de adja
ên
ia de um grafo simples G.
Então a ij-ésima entrada de Xr é o numero de passeios diferentes de
omprimento r entre os vérti
es vi e vj .
Corolário 2. Em um grafo 
onexo, a distân
ia entre dois vérti
es e
, , é se, e somente se, é o menor inteiro para o qual a
-ésima entrada em é não-nula.
Corolário 3. Se é a matriz de adja
ên
ia de um grafo 
om
vérti
es, e
então é des
onexo se, e somente se, existe ao menos uma entrada na
matriz que é igual a zero.
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Teorema 4. Seja X a matriz de adja
ên
ia de um grafo simples G.
Então a ij-ésima entrada de Xr é o numero de passeios diferentes de
omprimento r entreos vérti
es vi e vj .
Corolário 5. Em um grafo 
onexo, a distân
ia entre dois vérti
es vi e
vj, i 6= j, é k se, e somente se, k é o menor inteiro para o qual a
ij-ésima entrada em Xk é não-nula.
Corolário 6. Se é a matriz de adja
ên
ia de um grafo 
om
vérti
es, e
então é des
onexo se, e somente se, existe ao menos uma entrada na
matriz que é igual a zero.
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Teorema 7. Seja X a matriz de adja
ên
ia de um grafo simples G.
Então a ij-ésima entrada de Xr é o numero de passeios diferentes de
omprimento r entre os vérti
es vi e vj .
Corolário 8. Em um grafo 
onexo, a distân
ia entre dois vérti
es vi e
vj, i 6= j, é k se, e somente se, k é o menor inteiro para o qual a
ij-ésima entrada em Xk é não-nula.
Corolário 9. Se X é a matriz de adja
ên
ia de um grafo 
om n
vérti
es, e
Y = X +X2 +X3 + . . .+Xn−1,
então G é des
onexo se, e somente se, existe ao menos uma entrada na
matriz Y que é igual a zero.
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
É possível utilizar esta estrutura para armazenar digrafos?
Sim. Dado um digafo D(V,A) 
om n vérti
es e sem arestas paralelas,
de�nimos
xij =
{
1 se existe uma aresta dire
ionada do vérti
e vi para o vérti
e vj ,
0 
aso 
ontrário.
Exemplo
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Observações
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
■ Neste 
aso a matriz só será simétri
a se o digrafo for simétri
o.
■ O grau de saída do vérti
e vi é dado pela soma dos elementos da
linha i.
■ O grau de entrada do vérti
e vi é dado pela soma dos elementos da
oluna i.
■ Se X é a matriz de adja
ên
ia de um digrafo D, então a sua
transposta X⊤ é a matriz de adja
ên
ia do digrafo obtido pela
inversão da orientação das arestas de D.
Matriz de In
idên
ia
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
Seja G um grafo 
om n vérti
es e m arestas. Sua matriz de in
idên
ia é
uma matriz de ordem n×m, denotada por A = [aij ], de�nida 
omo
xij =
{
1 se a aresta aj é in
idente no vi,
0 
aso 
ontrário.
Observações:
■ É ne
essário fazer uma rotulação nos vérti
es e nas arestas de G.
■ A 
omplexidade em termos de espaço de memória de um algoritmo
que use uma matriz de adja
ên
ia para armazenar o grafo é O(nm).
■ Qualquer tipo de grafo pode ser armazenado nesta estrutura?
Não!
Apenas grafos que não possuam arestas laço.
Matriz de In
idên
ia
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
Seja G um grafo 
om n vérti
es e m arestas. Sua matriz de in
idên
ia é
uma matriz de ordem n×m, denotada por A = [aij ], de�nida 
omo
xij =
{
1 se a aresta aj é in
idente no vi,
0 
aso 
ontrário.
Observações:
■ É ne
essário fazer uma rotulação nos vérti
es e nas arestas de G.
■ A 
omplexidade em termos de espaço de memória de um algoritmo
que use uma matriz de adja
ên
ia para armazenar o grafo é O(nm).
■ Qualquer tipo de grafo pode ser armazenado nesta estrutura? Não!
Apenas grafos que não possuam arestas laço.
Exemplo
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
Observações
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
■ Como 
ada aresta é in
idente em exatamente dois vérti
es, 
ada
oluna de A(G) possui exatamente dois 1's.
■ O número de 1's em 
ada linha é igual ao grau do vérti
e
orrespondente.
■ Uma linha de 0's representa um vérti
e isolado.
■ Arestas paralelas 
orrespondem a 
olunas idênti
as.
■ Um grafo G é des
onexo 
om dois 
omponentes G1 e G2, então
A(G) =
[
A(G1) 0
0 A(G2)
]
.
■ Dois grafos G1 e G2 são isomorfos se, e somente se, suas matrizes
de in
idên
ia A(G1) e A(G2) diferem apenas por permutações de
linhas e 
olunas.
■ Quantos elementos diferentes de zero esta matriz possui?
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
É possível utilizar esta estrutura para armazenar digrafos?
Sim. Com uma pequena modi�
ação, uma vez que ao dizer que uma
aresta in
ide em um vérti
e é ne
essário espe
i�
ar se ela 
onverge para
ou diverge para este vérti
e.
Seja D um digrafo 
om n vérti
es e m arestas e sem arestas laço. Sua
matriz de in
idên
ia A = [aij] ∈ R
n×m
é de�nida 
omo
xij =


1 se a aresta aj diverge do vérti
e vi,
−1 se a aresta aj 
onverge para o vérti
e vi,
0 
aso 
ontrário.
Exemplo
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
As duas representações dadas (matrizes de adja
ên
ia e de in
idên
ia)
são importantes porque elas fa
ilitam a re
uperação de uma série de
informações a respeito de um grafo.
Por exemplo o grau de um vérti
e, determinar se dois vérti
es são
adja
entes, entre outras.
No entanto elas não valem para qualquer grafo dado, e demandam muito
espaço de memória: O(n2) e O(nm) para armazenar apenas 2m
elementos diferentes de zero.
É possível en
ontrar formar mais e�
ientes de armazenamento de dados.
É bom salientar no entanto que a melhor maneira de armazenar um
grafo ou digrafo vai depender do algoritmo a ser implementado.
Lista de Arestas
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
O digrafo (ou grafo) G é representado por dois vetores m-dimesionais
F = (f1, f2, . . . , fm) e H = (h1, h2, . . . , hm).
Cada elemento destes vetores re
ebe o rótulo de um vérti
e, de modo
que a i-ésima aresta diverge do vérti
e fi e 
onverge para o vérti
e hi.
Qual é o espaço ne
essário para esta estrutura? O(2m).
Exemplo
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Lista de su
essores
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
Quando a razão m/n não é muito alta, é 
onveniente usar uma lista de
su
essores.
Para isto de�nimos n vetores. Cada vetor é asso
iado a um vérti
e.
O primeiro elemento do vetor k é o vérti
e vk e os demais elementos são
os vérti
es adja
entes ao vérti
e vk (em um digrafo, os vérti
e que estão
ligados ao vérti
e k por um 
aminho de 
omprimento 1).
Supondo que dmed é o grau médio (ou grau de saída médio), o espaço de
memória ne
essário para esta estrutura é O(ndmed).
Exemplo
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Exer
í
io
Representação de Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
■ Construa a lista de arestas e a lista de su
essores para o grafo abaixo.
■ Es
reva um algoritmo para transformar a matriz de in
idên
ia de um
grafo (ou digrafo) na matriz de adja
ên
ias. Codi�que o algoritmo na
sua linguagem de programação favorita. Teste 
om grafos de diversas
densidades. Qual é a 
omplexidade 
omputa
ional do seu algoritmo?
	Representação de Grafos
	
	Matriz de Adjacência
	Exemplo
	Observações
	
	
	
	Exemplo
	Observações
	Matriz de Incidência
	Exemplo
	Observações
	
	Exemplo
	
	Lista de Arestas
	Exemplo
	Lista de sucessores
	Exemplo
	Exercício