Cap4 TG geradora e busca

Prévia do material em texto

TEORIA DOS GRAFOS
Prof. Bernardo Caldas
bcaldasbc@gmail.com
12/03/2018 1Teoria dos Grafos
• “Por menor que seja seu tempo de estudo, ESTUDE.”
• “Não tenha medo de crescer lentamente, tenha medo 
apenas de ficar parado.”
12/03/2018 2Teoria dos Grafos
• “Você deve estudar para “aprender” e “não” para passar de 
ano.”
• “Eu só sei que nada sei.” - Sócrates
• Minha meta é formar pensadores.
Índice
• Árvore geradoras de grafos
• Busca em profundidade e largura
• Algoritmos de caminho crítico 
• Acessibilidade• Acessibilidade
12/03/2018 3Teoria dos Grafos
Árvore geradora
• Uma árvore geradora para um grafo conexo é uma árvore sem raiz cujo
conjunto de nós coincide com o conjunto de nós do grafo e cujos arcos são,
alguns dos, arcos do grafo.
• Uma árvore geradora cuja soma dos pesos de seus arcos seja menor do que
em qualquer outra situação é chamada de árvore geradora mínima.
• Um método para obter uma árvore geradora de mínimo é o algoritmo de
Prim.
12/03/2018 4Teoria dos Grafos
Árvore geradora
Uma possível árvore geradora.
12/03/2018 5Teoria dos Grafos
Uma árvore geradora mínima.
Árvore geradora
• Pseudocódigo para árvore geradora mínima:
– Colocar um nó arbitrário no conjunto IN;
– Para cada nó z não pertencente a IN, guardar a distância– Para cada nó z não pertencente a IN, guardar a distância
mínima d[z] entre z e qualquer nó em IN;
– Incluir sucessivamente os demais nós em IN, em que o
próximo nó a ser incluído é um que não pertença a IN e cuja
distância d[z] seja mínima;
– O arco tendo essa distância mínima fará parte da árvore
geradora.
12/03/2018 6Teoria dos Grafos
Árvore geradora 
• Encontrar a árvore geradora mínima do grafo.
x
2
83
1
12/03/2018 7Teoria dos Grafos
21
71046
4
13
3
y
1
Árvore geradora
• IN = {1} adotar arbitrariamente.
• Distância dos nós adjacentes de IN
– 1 p/x = 3 (menor vai para lista IN)
– 1 p/3 = 6
x
2
83
1
71046
– 1 p/3 = 6
• IN = { 1, x}
12/03/2018 8Teoria dos Grafos
71046
4
13
3
y
1
Árvore geradora
• IN = {1, x}
• Distância dos nós adjacentes de IN
– x p/2 = 8
– x p/y = 10
x
2
83
1
71046
– x p/y = 10
– x p/3 = 4 (menor vai para lista IN)
– 1 p/3 = 6
• IN = { 1, x, 3}
12/03/2018 9Teoria dos Grafos
71046
4
13
3
y
1
Árvore geradora
• IN = {1, x, 3}
• Distância dos nós adjacentes de IN
– 3 p/y = 3
– 3 p/4 = 1 (menor vai para lista IN)
x
2
83
1
71046
– 3 p/4 = 1 (menor vai para lista IN)
– x p/2 = 8
• IN = { 1, x, 3, 4}
12/03/2018 10Teoria dos Grafos
71046
4
13
3
y
1
Árvore geradora
• IN = {1, x, 3, 4}
• Distância dos nós adjacentes de IN
– 4 p/y = 1 (menor vai para lista IN)
– 4 p/2 = 7
x
2
83
1
71046
– 4 p/2 = 7
– x p/2 = 8
• IN = { 1, x, 3, 4, y}
12/03/2018 11Teoria dos Grafos
71046
4
13
3
y
1
Árvore geradora
• IN = {1, x, 3, 4, y}
• Distância dos nós adjacentes de IN
– x p/2 = 8
– 4 p/2 = 7 (menor vai para lista)
x
2
83
1
71046
– 4 p/2 = 7 (menor vai para lista)
• IN = { 1, x, 3, 4, y, 2}
12/03/2018 12Teoria dos Grafos
71046
4
13
3
y
1
Árvore geradora
• Qual a árvore
geradora do
grafo mínima?
• IN = {a}
• a->b=1; a->d=4
• IN = {a,b}
• a->d=4; b->d=6; b->e=4; b->c=2
• IN = {a,b,c}
• a->d=4; b->d=6; b->e=4; c->e=5; c->f=6
12/03/2018 13Teoria dos Grafos
• a->d=4; b->d=6; b->e=4; c->e=5; c->f=6
• IN = {a,b,c,d}
• d->e=3; d->g=4; b->e=4; c->e=5; c->f=6
• IN = {a,b,c,d,e}
• d->g=4; e->g=7; e->f=8
• IN = {a,b,c,d,e,g}
• g->f=3; e->f=8; c->f=6
• IN = {a,b,c,d,e,g,f}
Árvore geradora
• Qual a árvore
geradora do
grafo mínima?
6
1
172
• IN = {1}
• 1->6=172; 1->5=123; 1->2=404; 1->3
=1120; 1->4=844
• IN = {1, 5}
• 1->6=172; 1->2=404; 1->3=1120; 1->4
=844; 5->6=47; 5->4=21547
12/03/2018 14Teoria dos Grafos
5
404
1
4
2
3
592
987
1120
844 215
123
321
186
=844; 5->6=47; 5->4=215
• IN = {1, 5, 6}
• 1->2=404; 1->3=1120; 1->4=844; 5-
>4=215; 6-4=321
• IN = {1, 5, 6, 4}
• 1->2=404; 1->3=1120; 4->3=186
• IN = {1, 5, 6, 4, 3}
• 1->2=404; 3->2=592; 4->2=987
• IN = {1,5,6,4,3,2}
Algoritmos de percurso
• Os percursos em grafos tratam de como explorar
um grafo de forma sistemática.
• Encontrar um caminho que passa por cada nó
pelo menos uma vez, mas pode visitar um nópelo menos uma vez, mas pode visitar um nó
mais de uma vez se não o escrever de novo,
podendo.
• Dois algoritmos generalizam o percurso em
qualquer grafo simples e conexo, a busca em
profundidade e busca em largura.
12/03/2018 15Teoria dos Grafos
Algoritmos de percurso
Busca em profundidade
• Começar em um nó arbitrário a do grafo, marcar
esse nó como tendo sido visitado e escrever esse
nó.
• Percorrer um caminho saindo de a, visitando e
escrevendo os nós, indo tão longe quantoescrevendo os nós, indo tão longe quanto
possível até não existirem nós que ainda não
forem visitados nesse caminho.
• Voltar pelo caminho explorando, em cada nó,
quaisquer caminhos laterais, até voltar,
finalmente, para a.
12/03/2018 16Teoria dos Grafos
Algoritmos de percurso
Busca em profundidade
• Aplicar a busca em
profundidade no grafo.
• Em uma busca em
profundidade, vá o mais longe
possível, depois suba
a
ib e
12/03/2018 17Teoria dos Grafos
profundidade, vá o mais longe
possível, depois suba
voltando, pegando qualquer
caminho não percorrido na
descida.
• As escolhas dos nós serão
feitas por ordem alfabética.
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Iniciar em a (arbitrário)
• L = {a}
• Escolher um nó adjacente a a
(b, e, h, i)
a
ib e
12/03/2018 18Teoria dos Grafos
(b, e, h, i)
– => selecionar b
• Iniciar em b
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Iniciar em b
• L = {a, b}
• Escolher um nó adjacente a b
(c)
a
ib e
12/03/2018 19Teoria dos Grafos
(c)
– => selecionar c
• Iniciar em c
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Iniciar em c
• L = {a, b, c}
• Escolher um nó adjacente a c
(e,d,f)
a
ib e
12/03/2018 20Teoria dos Grafos
(e,d,f)
– => selecionar d (ordem alfab.)
• Iniciar em d
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Iniciar em d
• L = {a, b, c, d}
• Escolher um nó adjacente a d
( f, g)
a
ib e
12/03/2018 21Teoria dos Grafos
( f, g)
– => selecionar f (ordem alfab.)
• Iniciar em f
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Iniciar em f
• L = {a, b, c, d, f}
• Escolher um nó adjacente a f
(g)
a
ib e
12/03/2018 22Teoria dos Grafos
(g)
– => selecionar g
• Término em g
• L = { a, b, c, d, f, g}
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Voltar a partir de g (sair dos laços)
• Escolher um nó adjacente a c
(e)
– Selecionar e
a
ib e
12/03/2018 23Teoria dos Grafos
– Selecionar e
• Iniciar em e
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Iniciar em e
• L = {a, b, c, d, f, g, e}
• Escolher um nó adjacente a e
(h, j)
a
ib e
12/03/2018 24Teoria dos Grafos
(h, j)
– => escolher h (ordem alfab.)
• Iniciar em h
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Iniciar em h
• L = {a, b, c, d, f, g, e, h}
• Escolher um nó adjacente a h
(i, j, k)
a
ib e
12/03/2018 25Teoria dosGrafos
(i, j, k)
– => escolher i (ordem alfab.)
• Iniciar em i
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Iniciar em i
• L = {a, b, c, d, f, g, e, h, i}
• Escolher um nó adjacente a i (k)
– => escolher k
a
ib e
12/03/2018 26Teoria dos Grafos
– => escolher k
• Termino em k
• L = { a, b, c, d, f, g, e, h, i, k}
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em profundidade
• Voltar a partir de k (sair dos laços)
• Escolher um nó adjacente a h
(j)
– h para j (não visitado)
a
ib e
12/03/2018 27Teoria dos Grafos
– h para j (não visitado)
• Selecionar J
• L = {a, b, c, d, f, g, e, h, i, k, j}
• Terminar em J
• Voltar para a
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• Na busca em largura, começar em
um nó arbitrário a, procurar, a
partir de a, todos os nós
adjacentes, depois os nós
adjacentes a esses e assim por
a
ib e
12/03/2018 28Teoria dos Grafos
adjacentes a esses e assim por
diante, quase como círculos
concêntricos de ondas em um
pequeno lago.
• A figura mostra os primeiros nós
visitados na busca em largura
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
a
ib e
h
Distância 0 - a
Distância 1 – b, e, h, i
12/03/2018 29Teoria dos Grafos
fd
g
c
h
j k
Distância 2 – c, j, k
Distância 3 – d, f
Distância 4 - g
Algoritmos de percurso
Busca em largura
• Aplicar a busca em
largura no grafo.
a
ib e
12/03/2018 30Teoria dos Grafos
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { } vazia
• Iniciar em a
• F = {a}
a
ib e
12/03/2018 31Teoria dos Grafos
• F = {a}
• Procurar nós adjacentes a a
– => b, e, h, i
• F = { a, b, e, h, i}
• F = { a, b, e, h, i} remover a
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i}
• Procurar nós adjacentes a b
– => c
a
ib e
12/03/2018 32Teoria dos Grafos
– => c
• F = { a, b, e, h, i, c}
• F = { a, b, e, h, i, c} remover b
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c}
• Procurar nós adjacentes a e
– => j
a
ib e
12/03/2018 33Teoria dos Grafos
– => j
• F = { a, b, e, h, i, c, j}
• F = { a, b, e, h, i, c, j} remover e
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c, j}
• Procurar nós adjacentes a h
– => k
a
ib e
12/03/2018 34Teoria dos Grafos
– => k
• F = { a, b, e, h, i, c, j, k}
• F = { a, b, e, h, i, c, j, k} remover h
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c, j, k}
• Procurar nós adjacentes a i
– => nenhum nó novo na fila
a
ib e
12/03/2018 35Teoria dos Grafos
– => nenhum nó novo na fila
• F = { a, b, e, h, i, c, j, k}
• F = { a, b, e, h, i, c, j, k} remover i
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c, j, k}
• Procurar nós adjacentes a c
– => d, f
a
ib e
12/03/2018 36Teoria dos Grafos
– => d, f
• F = { a, b, e, h, i, c, j, k, d, f}
• F = { a, b, e, h, i, c, j, k, d, f} remover c
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c, j, k, d, f}
• Procurar nós adjacentes a j
– => nenhum nó novo na fila
a
ib e
12/03/2018 37Teoria dos Grafos
– => nenhum nó novo na fila
• F = { a, b, e, h, i, c, j, k, d, f}
• F = { a, b, e, h, i, c, j, k, d, f} remover j
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c, j, k, d, f}
• Procurar nós adjacentes a k
– => nenhum nó novo na fila
a
ib e
12/03/2018 38Teoria dos Grafos
• F = { a, b, e, h, i, c, j, k, d, f}
• F = { a, b, e, h, i, c, j, k, d, f} remover k
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c, j, k, d, f}
• Procurar nós adjacentes a d
– => f; g
a
ib e
12/03/2018 39Teoria dos Grafos
• F = { a, b, e, h, i, c, j, k, d, f, g}
• F = { a, b, e, h, i, c, j, k, d, f, g} remover d
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c, j, k, d, f, g}
• Procurar nós adjacentes a f
– => nenhum nó novo na fila
a
ib e
12/03/2018 40Teoria dos Grafos
• F = { a, b, e, h, i, c, j, k, d, f, g}
• F = { a, b, e, h, i, c, j, k, d, f, g} remover f
ib
fd
g
c
e
h
j k
Algoritmos de percurso
Busca em largura
• F = { a, b, e, h, i, c, j, k, d, f, g}
• Procurar nós adjacentes a g
– => nenhum nó novo na fila
• F = { a, b, e, h, i, c, j, k, d, f, g}
a
ib e
12/03/2018 41Teoria dos Grafos
• F = { a, b, e, h, i, c, j, k, d, f, g}
• F = { a, b, e, h, i, c, j, k, d, f, g} remover g
• F = { a, b, e, h, i, c, j, k, d, f, g}
• F = { a, b, e, h, i, c, j, k, d, f, g}
ib
fd
g
c
e
h
j k
Algoritmo de caminho mínimo
• Para um grafo simples conexo e com pesos positivos, então,
existe um caminho entre dois nós quaisquer x e y.
• Como encontrar um caminho com peso mínimo? Como o
peso representa, muitas vezes, a distância, esse problema
ficou conhecido como problema do caminho mínimo.ficou conhecido como problema do caminho mínimo.
• Em 1959, Dijkstra fez a publicação de um algoritmo para
resolver esse problema.
• Inúmeras aplicações: redes de computadores, telefonia,
caixeiro viajante, etc...é um algoritmo clássico
12/03/2018 42Teoria dos Grafos
Algoritmo de caminho mínimo
• O algoritmo de Dijkstra soluciona o problema
do caminho mais curto num grafo dirigido ou
não dirigido com arcos de pesos não
negativos.negativos.
• A google desenvolveu o algoritmo A*
12/03/2018 43Teoria dos Grafos
Algoritmo de caminho mínimo Dijkstra
• O grafo e a matriz de adjacência modificada
x
83
12/03/2018 44Teoria dos Grafos
2
83
1
71046
4
13
3
y
1
Algoritmo de caminho mínimo Dijkstra
• Fase de inicialização
x
83
12/03/2018 45Teoria dos Grafos
2
83
1
71046
4
13
3
y
1
Infinito -> não existe arco de x para 4.
x -> é o predecessor de todos os nós, 
exceto do nó x.
Identificar todos os nós adjacentes a x.
Iniciar em qualquer nó.
Algoritmo de caminho mínimo Dijkstra
• Procurar entre os valores de d o nó
não pertencente a IN de distância
mínima => d[1] = 3
• Colocar o nó 1 em IN
• Recalcular os valores de d para os nós
restantes 2, 3, 4, y => d[z]
x
• p = 1 (nó inserido)
• IN = {x, 1}
• D[z]=min(d[z], d[p]+A[p,z])
• D[2]=min(8, 3+A[1, 2]) = min(8, 3+inf)=8
• D[3]=min(4, 3+A[1, 3]) = min(4, 3+6) = 4
• D[4]=min(inf, 3+A[1, 4])=min(inf, inf)=inf
D[y]=min(10, 3+A[1, y])=min(10, inf)=10
12/03/2018 46Teoria dos Grafos
2
83
1
71046
4
13
3
y
1
• D[y]=min(10, 3+A[1, y])=min(10, inf)=10
• Não houve mudança nos valores de d, não
existe distâncias menor para ir para 1 de x.
Algoritmo de caminho mínimo Dijkstra
• Procurar entre os valores de d o nó
não pertencente a IN de distância
mínima => d[3] = 4
• Colocar o nó 3 em IN
• Recalcular os valores de d para os nós
restantes 2, 4, y => d[z]
x
• p = 3 (nó inserido)
• IN = {x, 1, 3}
• D[z]=min(d[z], d[p]+A[p,z])
• D[2]=min(8, 4+A[3, 2]) = min(8, 4+inf)=8
• D[4]=min(inf, 4+A[3, 4])=min(inf, 4+1)=5
• Atualizar s[4]=3
D[y]=min(10, 4+A[3, y])=min(10, 4+3)=7
12/03/2018 47Teoria dos Grafos
2
83
1
71046
4
13
3
y
1
• D[y]=min(10, 4+A[3,y])=min(10, 4+3)=7
• Atualizar s[y]=3
• Foi encontrado distância menor de x aos
nós 4 e y.
Posição anterior Após atualização
Algoritmo de caminho mínimo Dijkstra
• Procurar entre os valores de d o nó
não pertencente a IN de distância
mínima => d[4] = 5
• Colocar o nó 4 em IN
• Recalcular os valores de d para os nós
restantes 2, y => d[z]
x
• p = 4 (nó inserido)
• IN = {x, 1, 3, 4}
• D[z]=min(d[z], d[p]+A[p,z])
• D[2]=min(8, 5+A[4, 2]) = min(8, 5+7)=8
• D[y]=min(7, 5+A[4, y])=min(7, 5+1)=6
• Atualizar s[y]=4
Foi encontrado distância menor de x ao nó y.
12/03/2018 48Teoria dos Grafos
2
83
1
71046
4
13
3
y
1
• Foi encontrado distância menor de x ao nó y.
Posição anterior Após atualização
Algoritmo de caminho mínimo Dijkstra
• Procurar entre os valores de d o nó
não pertencente a IN de distância
mínima => d[y] = 6
• Colocar o nó y em IN
• Recalcular os valores de d para os nós
restantes 2 => d[z]
x
• p = y (nó inserido)
• IN = {x, 1, 3, 4, y}
• D[z]=min(d[z], d[p]+A[p,z])
• D[2]=min(8, 6+A[4, y])=min(8, 6+inf)=8
• Com a entrada de y o algoritmo termina
• A distância de y para x = 6
A sequencia é: y, 4, 3, x (inversa)
12/03/2018 49Teoria dos Grafos
2
83
1
71046
4
13
3
y
1
• A sequencia é: y, 4, 3, x (inversa)
Algoritmo de caminho mínimo 
Bellman-Ford
• Outro algoritmo para encontrar os caminhos mínimos a
partir de um único nó para todo os outros em um grafo é o
algoritmo de Bellman-Ford.
• Ao contrário do algoritmo de Dijkstra, que guarda um
conjunto de nós cujo caminho mínimo de qualquerconjunto de nós cujo caminho mínimo de qualquer
comprimento arbitrário já foi determinado, o algoritmo de
Bellman-Ford executa uma série de cálculos procurando
encontrar caminhos mínimos, sucessivamente, de
comprimento 1, comprimento 2 e assim em diante, até ao
máximo de comprimento n-1.
• Os pesos podem ser negativos e apresenta um tempo
maior de execução em relação ao algoritmo de Dijksta.
12/03/2018 50Teoria dos Grafos
Algoritmo de caminho mínimo 
Bellman-Ford
• Calcular o caminho mínimo para o grafo dirigido usando
Bellman-Ford do nó a ao nó f.
• Iniciar em a
• O peso de a é zero;
12/03/2018 51Teoria dos Grafos
3
5
-2
10
1
72a
b
c
d
e
f2
3
• O peso de a é zero;
• Calcular as distâncias
dos nós acessíveis a a;
• De a->b=0+5=5
• De a->c=0+-2=-2
0
Algoritmo de caminho mínimo 
Bellman-Ford
5
12/03/2018 52Teoria dos Grafos
3
5
-2
10
1
72a
b
c
d
e
f2
3
0
-2
5
passo 1 passo 2 passo 3
a a, 0
b a, 5
c a, -2
d inf
e inf
f inf
Algoritmo de caminho mínimo 
Bellman-Ford
5->0
• Calcular as distâncias dos
nós acessíveis a b;
• De b->d=5+1=6
• Ajustando b
• De b->d=0+1=16->1
12/03/2018 53Teoria dos Grafos
3
5
-2
10
1
72a
b
c
d
e
f2
3
0
-2
5->0 • De b->d=0+1=1
• Calcular as distância do nós
acessíveis a c;
• De c->b=-2+2=0 (é menor
que 5, ajustar b)
• De c->e=-2+3=1
6->1
Algoritmo de caminho mínimo 
Bellman-Ford
0 1
12/03/2018 54Teoria dos Grafos
3
5
-2
10
1
72a
b
c
d
e
f2
3
0
-2
0
1
1
passo 1 passo 2 passo 3
a a, 0 a, 0
b a, 5 c, 0
c a, -2 a, -2
d a,inf b, 1
e a,inf c, 1
f a,inf a,inf
Algoritmo de caminho mínimo 
Bellman-Ford
0 1
• Calcular as distâncias dos
nós acessíveis a d;
• De d->f=1+3=4
• De d->c=1+2=3 é maior
que -2, manter
12/03/2018 55Teoria dos Grafos
3
5
-2
10
1
72a
b
c
d
e
f2
3
0
-2
0
1
1 que -2, manter
• De d->e=1+7=8 é maior
que 1, manter
• Calcular as distância do nós
acessíveis a e;
• De e->f=1+10=11 é maior
que de d->f=4
Algoritmo de caminho mínimo 
Bellman-Ford
0 1 passo 1 passo 2 passo 3
a a, 0 a, 0 a, 0
12/03/2018 56Teoria dos Grafos
3
5
-2
10
1
72a
b
c
d
e
f2
3
0
-2
0
1
1
4
a a, 0 a, 0 a, 0
b a, 5 c, 0 c, 0
c a, -2 a, -2 a, -2
d a,inf b, 1 b, 1
e a,inf c, 1 c, 1
f a,inf a,inf d, 4
Acessibilidade
• Em um grafo direcionado, o nó nj será
acessível do nó ni se existir um caminho de ni
para nj.
12/03/2018 57Teoria dos Grafos
• Se A for a matriz booleana de adjacência de
um grafo direcionado G com n nós e sem
arcos paralelos, então A(m)[i,j]=1 se e somente
se existir um caminho de comprimento m do
nó ni para o nó nj .
Acessibilidade
• Seja G o grafo direcionado apresentado na
figura e sua matriz de acessibilidade.
12/03/2018 58Teoria dos Grafos
Acessibilidade
• Produto entre as matrizes
X =>
A A
12/03/2018 59Teoria dos Grafos
• A11 = 0*0 + 1*0 + 0*1 + 0*0 + 0*1 = 0
• A12 = 0*1 + 1*0 + 0*0 + 0*0 + 0*0 = 0
• A13 = 0*0 + 1*1 + 0*0 + 0*0 + 0*1 = 1
• A14 = 0*0 + 1*0 + 0*1 + 0*0 + 0*0 = 0
• A15 = 0*0 + 1*0 + 0*0 + 0*0 + 0*0 = 0
• A21 = 0*0 + 0*0 + 1*1 + 0*0 + 0*1 = 1
• ......
A
Acessibilidade
12/03/2018 60Teoria dos Grafos
• Existe um caminho de comprimento 2 de 2 para 1, pois
A(2)[2,1]=1 (caminho 2-3-1).
• Existe um caminho de comprimento 4 de 5 para 2, pois
A(4)[5,3]=1 (caminho 5-3-1-2-3)
Acessibilidade
• Para calcular A(2)[i,j], escreva duas cópias de A, uma ao
lado da outra. Use um dedo da mão esquerda para
percorrer a linha i da matriz à esquerda ao mesmo
tempo o dedo da mão direita para percorrer a coluna j
da matriz à direita. O valor será 1 se e somente se
12/03/2018 61Teoria dos Grafos
da matriz à direita. O valor será 1 se e somente se
ambos os dedos encontram um número 1 ao mesmo
tempo.
• Não tente calcular produtos matriciais sem colocar as
duas matrizes uma ao lado da outra; VOCÊ
CERTAMENTE COMETERÁ UM ERRO.
Acessibilidade
• Produto entre matrizes
12/03/2018 62Teoria dos Grafos
Obrigado
Bernardo Caldas
12/03/2018 63Teoria dos Grafos