Introdução aos Grafos

Prévia do material em texto

24/06/2018
1
Estruturas de Dados
Grafos
Prof. Luciana R. Cardoso
Grafos - Introdução 
Prof. Luciana R. Cardoso
2
 Muitas aplicações em computação necessitam
considerar conjunto de conexões entre pares de
objetos:
 Existe um caminho para ir de um objeto a outro
seguindo as conexões?
 Qual é a menor distância entre um objeto e outro
objeto?
 Quantos outros objetos podem ser alcançados a
partir de um determinado objeto?
 Existe um tipo abstrato chamado grafo que é
usado para modelar tais situações.
24/06/2018
2
Grafos - Introdução 
 Alguns exemplos de problemas práticos que podem
ser resolvidos através de uma modelagem em grafos:
 Ajudar máquinas de busca a localizar informação
relevante na Web.
 Descobrir os melhores casamentos entre posições
disponíveis em empresas e pessoas que aplicaram
para as posições de interesse.
 Descobrir qual é o roteiro mais curto para visitar as
principais cidades de uma região turística.
 Etc.
Prof. Luciana R. Cardoso
3
Grafos - Exemplos
 Transporte aéreo
 objeto: cidades
 relacionamento: vôo comercial entre duas cidades
Prof. Luciana R. Cardoso
4
24/06/2018
3
Grafo - Definição
 “Um grafo é um conjunto de pontos, chamados
vértices, conectados por linhas, chamadas de
arestas” .
 Abstração que permite codificar relacionamentos
entre pares de objetos.
 Que objetos?
 Qualquer um! Ex. pessoas, cidades, empresas, países, páginas
web, filmes, etc...
 Que relacionamentos?
 Qualquer um! Ex. amizade, conectividade, produção, língua
falada, etc.
Prof. Luciana R. Cardoso
5
Grafo - Definição
 Muitas situações do mundo real podem ser
convenientemente representadas por meio
de um diagrama consistindo de um conjunto
de pontos e de linhas que ligam alguns pares
desses pontos. Por exemplo, os pontos
poderiam representar centros de
comunicação e, neste caso, as linhas
denotariam os links entre os centros. Tal
abstração matemática faz surgir o conceito
de grafos.
Prof. Luciana R. Cardoso
6
24/06/2018
4
Grafo - Definição
Prof. Luciana R. Cardoso
7
Grafos - Exemplos
 Web
 objeto: páginas web
 relacionamento: link de uma pagina para outra
Prof. Luciana R. Cardoso
8
24/06/2018
5
Grafos – Conceitos Básicos
Prof. Luciana R. Cardoso
9
Grafos – Conceitos Básicos
 Grafo: conjunto de vértices e arestas.
 Vértice: objeto simples que pode ter nome e outros
atributos.
 Aresta: conexão entre dois vértices.
Prof. Luciana R. Cardoso
10
Notação: G = (V;A)
– G: grafo
– V: conjunto de vértices
– A: conjunto de arestas
24/06/2018
6
Grafos – Conceitos Básicos
 Suponha que existam seis sistemas computacionais
(A, B, C, D, E, e F) interconectados entre si da
seguinte forma:
Prof. Luciana R. Cardoso
11
•Esta informação pode ser representada por este diagrama,
chamado de grafo.
•Este diagrama identifica unicamente um grafo.
Como aprender a modelar grafos?
 Estudando problemas existentes
 abstrair o problema real
 solucionar o problema no domínio grafos
Prof. Luciana R. Cardoso
12
Algoritmos em grafos!
24/06/2018
7
Transporte Aéreo
 Perguntas interessantes?
 Voos entre todas as cidades?
 Que tem voos?
 Menor número de voos entre duas cidades?
Prof. Luciana R. Cardoso
13
Algoritmos para responder!
Poder da Abstração
 Muitos problemas resolvidos com o mesmo
algoritmo (solução) em cima da abstração!
Prof. Luciana R. Cardoso
14
24/06/2018
8
Terminologia
 Cada aresta está associada a um conjunto de um ou
dois vértices, chamados nós terminais.
 Extremidade de uma aresta: vértice da aresta.
 Função aresta–extremidade: associa aresta a
vértices.
 Laço (Loop): aresta somente com nó terminal.
 Arestas paralelas: arestas associadas ao mesmo
conjunto de vértices.
 Uma aresta é dita conectar seus nós terminais.
Prof. Luciana R. Cardoso
15
Terminologia
 Dois vértices que são conectados por uma aresta são
chamados de adjacentes.
 Um vértice que é nó terminal de um laço é dito ser
adjacente a si próprio.
 Uma aresta é dita ser incidente a cada um de seus
nós terminais.
 Duas arestas incidentes ao mesmo vértice são
chamadas de adjacentes.
 Um vértice que não possui nenhuma aresta incidente
é chamado de isolado.
 Um grafo com nenhum vértice é chamado de vazio.
Prof. Luciana R. Cardoso
16
24/06/2018
9
Terminologia
Prof. Luciana R. Cardoso
17
Terminologia
 Definição 1
 Um Grafo G = (V, E) consiste em V, um conjunto não vazio
de vértices (ou nós), e E, um conjunto de arestas. Cada aresta tem
um ou dois vértices associados a ela, chamados de suas
extremidades.
 Dizemos que uma aresta liga ou conecta suas extremidades.
Prof. Luciana R. Cardoso
18
24/06/2018
10
Terminologia
 Definição 2
 Um Grafo orientado (ou dígrafo) (V, E) consiste em V,
um conjunto não vazio de vértices (ou nós), e E, um conjunto
de arestas. E cada aresta orientada está associada a um par
ordenado de vértices. É dito que aresta orientada associada ao
par ordenado (u, v) começa em u e termina em v.
Prof. Luciana R. Cardoso
19
Terminologia
 Tipos:
 Grafo Simples: cada aresta conecta dois vértices
diferentes {u, v}.
 Multigrafos: arestas múltiplas: várias arestas conectadas
ao mesmo vértices. Multiplicidade m.
 Laços: Arestas que conectam um vértices a si mesmo.
Prof. Luciana R. Cardoso
20
24/06/2018
11
Grafos Direcionados
 Um grafo direcionado G é um par (V;A), onde V é um conjunto
finito de vértices e A é uma relação binária em V .
 Um grafo dirigido ou digrafo ou direcionado G consiste de
dois conjuntos finitos:
 1. Vértices V (G)
 2. Arestas dirigidas E(G), onde cada aresta é associada a um
par ordenado de vértices chamados de nós terminais. Se a
aresta e é associada ao par (u, v) de vértices, diz-se que e é
a aresta dirigida de u para v.
 Podem existir arestas de um vértice para ele mesmo, chamadas
de self-loops (ciclos).
Prof. Luciana R. Cardoso
21
Grafos Direcionados
 Para cada grafo dirigido, existe um grafo simples
(não dirigido) que é obtido removendo as direções
das arestas, e os loops.
Prof. Luciana R. Cardoso
22
24/06/2018
12
Grafos Não Direcionados
 Um grafo não direcionado G é um par (V;A), onde o
conjunto de arestas A é constituído de pares de
vértices não ordenados.
 As arestas (u; v) e (v; u) são consideradas como uma única
aresta. A relação de adjacência é simétrica.
 Self-loops não são permitidos.
Prof. Luciana R. Cardoso
23
Versão Direcionada de um Grafo Não 
Direcionado
 A versão direcionada de um grafo não direcionado G =
(V;A) é um grafo direcionado G’ = (V’;A’) onde (u; v) A’
sse (u; v) A.
 Cada aresta não direcionada (u; v) em G é substituída por
duas arestas direcionadas (u; v) e (v; u)
 Em um grafo direcionado, um vizinho de um vértice u é
qualquer vértice adjacente a u na versão não direcionada de
G.
Prof. Luciana R. Cardoso
24


24/06/2018
13
Versão Não Direcionada de um Grafo 
Direcionado
 A versão não direcionada de um grafo direcionado G
= (V;A) é um grafo não direcionado G’ = (V’;A’) onde
(u; v) A’ sse u v e (u; v) A.
 A versão não direcionada contém as arestas de G
sem a direção e sem os self-loops.
 Em um grafo não direcionado, u e v são vizinhos se
eles são adjacentes.
Prof. Luciana R. Cardoso
25
  
Grau de um Vértice
 Em grafos não direcionados:
 O grau de um vértice é o número de arestas que incidem nele.
exceto que um laço em um vértice contribui duas vezes ao
grau daquele vértice.
 Um vértice de grau zero é dito isolado ou não conectado.
 O grau de um vértice v é indicado por gr(v).
Prof.Luciana R. Cardoso
26
24/06/2018
14
Grau de um Vértice
 Seja G um grafo e um vértice v de G. O grau de v,
denominado grau(v) (deg(v)), é igual ao número de
arestas que são incidentes a v, com uma aresta que
seja um laço contada duas vezes. O grau total de G é
a soma dos graus de todos os vértices de G.
 Ex.: O vértice 1 tem grau 2 e o vértice 3 é isolado.
Prof. Luciana R. Cardoso
27
Quais são os graus
dos vértices nos
grafos da figura?
Grau de um Vértice
 Em grafos direcionados
 O grau de um vértice é o número de arestas que saem dele
(out-degree) mais o número de arestas que chegam nele (in-
degree).
 Ex.: O vértice 2 tem in-degree 2, out-degree 2 e grau
4.
Prof. Luciana R. Cardoso
28
24/06/2018
15
Grau de um Vértice
 Exemplo: Seja o grafo G. Determine o grau de cada vértice e
o grau total de G.
 grau(v1) = 0, já que não existe aresta incidente a v1, que é um vértice
isolado.
 grau(v2) = 2, já que e1 e e2 são incidentes a v2.
 grau(v3) = 4, já que e1, e2 e e3 são incidentes a v3, sendo que e3
contribui com dois para o grau de v3.
 Grau de G = grau(v1) + grau(v2) + grau(v3) = 0 + 2 + 4 = 6
 Grau de G = 2 × número de arestas de G, que é 3, ou seja,
cada aresta contribui com dois para o grau total do grafo.
Prof. Luciana R. Cardoso
29
Grau de um Vértice
 Corolário: O grau total de um grafo é par.
 É possível ter um grafo com quatro vértices de graus
1, 1, 2, e 3? Não. O grau total deste grafo é 7, que é
um número ímpar.
 É possível ter um grafo com quatro vértices de graus
1, 1, 3, e 3? Sim. Exemplos:
Prof. Luciana R. Cardoso
30
24/06/2018
16
Grau de um Vértice
 É possível ter um grafo com 10 vértices de graus 1, 1,
2, 2, 2, 3, 4, 4, 4, e 6?
 Não. Duas formas de provar:
 1. Este grafo supostamente possui três vértices de grau ímpar,
o que não é possível.
 2. Este grafo supostamente possui um grau total = 29, o que
não é possível.
Prof. Luciana R. Cardoso
31
Caminho entre Vértices
 Um caminho de comprimento k de um vértice x a
um vértice y em um grafo G = (V;A) é uma sequência
de vértices (v0, v1, v2, ... , vk) tal que x = v0 e y = vk, e
(vi-1, vi) A para i = 1, 2,..., k.
 O comprimento de um caminho é o número de
arestas nele, isto é, o caminho contém os vértices v0,
v1;, v2, ... , vk e as arestas (v0, v1); (v1, v2), ... , (vk-1, vk).
Prof. Luciana R. Cardoso
32

24/06/2018
17
Caminho entre Vértices
 Se existir um caminho c de x a y então y é
alcançável a partir de x via c.
 Um caminho é simples se todos os vértices do
caminho são distintos.
 Ex.: O caminho (0; 1; 2; 3) é simples e tem
comprimento 3. O caminho (1; 3; 0; 3) não é simples.
Prof. Luciana R. Cardoso
33
Ciclos 
 Em um grafo direcionado:
 Um caminho (v0, v1, v2, ... , vk) forma um ciclo se v0 = vk e o
caminho contém pelo menos uma aresta.
 O ciclo é simples se os vértices v1, v2, ... , vk são distintos.
 O self-loop é um ciclo de tamanho 1.
 Dois caminhos (v0, v1, v2, ... , vk) e (v’ 0, v’1, ... , v’k) formam o
mesmo ciclo se existir um inteiro j tal que v’i = v(i+j) mod k para i
= 0, 1, ... , k - 1.
Prof. Luciana R. Cardoso
34
24/06/2018
18
Ciclos 
 Em um grafo direcionado:
 Ex.: O caminho (0, 1, 2, 3, 0) forma um ciclo. O caminho(0, 1,
3, 0) forma o mesmo ciclo que os caminhos (1, 3, 0, 1) e (3, 0, 1,
3).
Prof. Luciana R. Cardoso
35
Ciclos 
 Em um grafo não direcionado:
 Um caminho (v0, v1, v2, ... , vk) forma um ciclo se v0 = vk e o
caminho contém pelo menos três arestas.
 O ciclo é simples se os vértices v1, v2, ... , vk)são distintos.
 Ex.: O caminho (0; 1; 2; 0) é um ciclo.
Prof. Luciana R. Cardoso
36
24/06/2018
19
Componentes Conectados
 Um grafo não direcionado é conectado se cada par de
vértices está conectado por um caminho.
 Os componentes conectados são as porções
conectadas de um grafo.
 Um grafo não direcionado é conectado se ele tem
exatamente um componente conectado.
 Ex.: Os componentes são: {0, 1, 2} , {4, 5} e {3}.
Prof. Luciana R. Cardoso
37
Componentes Fortemente Conectados
 Um grafo direcionado G = (V;A) é fortemente
conectado se cada dois vértices quaisquer são
alcançáveis a partir um do outro.
 Os componentes fortemente conectados de
um grafo direcionado são conjuntos de vértices sob a
relação “são mutuamente alcançáveis”.
 Um grafo direcionado fortemente conectado
tem apenas um componente fortemente conectado.
Prof. Luciana R. Cardoso
38
24/06/2018
20
Componentes Fortemente Conectados
 Ex.: {0, 1, 2, 3}, {4} e {5} são os componentes
fortemente conectados, {4, 5} não o é pois o vértice 5
não é alcançável a partir do vértice 4.
Prof. Luciana R. Cardoso
39
Definições Básicas
 Laço – uma aresta que incide com um único vértice é chamada de laço.
 Orientação – é a direção para a qual uma seta aponta. Se a aresta não
tiver seta, diz-se que ela não tem orientação
 Incidente – Diz-se que uma aresta é incidente com os vértices que ela
liga (não importa a orientação).
 Vértices Adjacentes – dois vértices são adjacentes se estão ligados
por uma aresta.
 Vértice isolado – Um vértice é dito isolado se não existe aresta
incidente sobre ele.
 Arestas paralelas – Duas arestas incidentes nos mesmos vértices
(não importa a orientação). Ou seja, se a1 = (v,w) e a2 = (v,w), então as
arestas a1 e a2 são paralelas.
Prof. Luciana R. Cardoso
40
24/06/2018
21
Definições Básicas
Prof. Luciana R. Cardoso
41
Definições Básicas
Prof. Luciana R. Cardoso
42
24/06/2018
22
Definições Básicas
Prof. Luciana R. Cardoso
43
Definições Básicas
Prof. Luciana R. Cardoso
44
24/06/2018
23
Definições Básicas
Prof. Luciana R. Cardoso
45
Definições Básicas
Prof. Luciana R. Cardoso
46
24/06/2018
24
Definições Básicas
Prof. Luciana R. Cardoso
47
Modelos usando Grafos
Prof. Luciana R. Cardoso
48
24/06/2018
25
Tipos de Grafos
 Grafo Rotulado
 Um grafo é dito rotulado quando seus vértices e/ou arestas são
distinguidos uns dos outros por rótulos (que pode ser um
nome, um número ou conjunto de letras ou números. Caso
contrário o grafo é não rotulado.
 Nos exemplos a seguir, o primeiro grafo não tem nenhum
rótulo. O segundo grafo possui rótulos nos vértices e o terceiro
grafo possui rótulos nas arestas.
Prof. Luciana R. Cardoso
49
Tipos de Grafos
 Grafo Rotulado
Prof. Luciana R. Cardoso
50
24/06/2018
26
Tipos de Grafos
 Exemplo 1 – Represente graficamente um
grafo definido matematicamente como
segue: Grafo G(V,A), onde V = {v1,v2,v3,v4} e
A = {(v1,v2),(v2,v3),(v3,v3),(v3,v1)}.
 Há varias formas gráficas semelhantes de se
representar esse grafo, mantendo as definições, pois
a posição dos vértices no espaço é irrelevante. Vou
fazer de duas formas diferentes.
Prof. Luciana R. Cardoso
51
Tipos de Grafos
Prof. Luciana R. Cardoso
52
Exemplo 1
24/06/2018
27
Tipos de Grafos
 Subgrafos
 Um grafo H = (V 0,E0) é dito ser um subgrafo de um grafo G =
 (V,E) sse:
 cada vértice de H é também um vértice de G, ou seja, V’ V ;
 cada aresta de H é também uma aresta de G, ou seja, E E; e
 cada aresta de H tem os mesmos nós terminais em G, ou seja, se
(u, v) E’ então (u, v) E.
 Exemplo: Todos os subgrafos do grafo G:
Prof. Luciana R. Cardoso
53




Tipos de Grafos
 Ordem
 A ordem de um grafo é definida por |V| = n. Ou seja, a ordem
de um grafo é o número de vértices.
 Grafos simples
 Um grafo simples é um grafo que não possui laços nem
arestas paralelas. Num grafo simples, uma aresta com
vértices (nós terminais) u e v é representada por uv.
Prof. Luciana R.Cardoso
54
24/06/2018
28
Tipos de Grafos
 Grafo completo
 Um grafo completo de n vértices, denominado Kn , é um
grafo simples com n vértices v1, v2, . . . , vn, cujo conjunto de
arestas contém exatamente uma aresta para cada par de
vértices distintos. Exemplo: Grafos completos com 2, 3, 4, e
5 vértices. Um grafo completo de n vértices é denominado
cliques.
Prof. Luciana R. Cardoso
55
Tipos de Grafos
 Multigrafos
 Um multigrafo é um grafo que não possui laços mas pode
ter arestas paralelas. grafo que contém arestas paralelas ou aços
Prof. Luciana R. Cardoso
56
24/06/2018
29
Tipos de Grafos
 Pseudografo
 Um pseudografo é um grafo que pode ter laços e arestas
paralelas. Formalmente, um pseudografo G = (V,E) consiste de
um conjunto V de vértices, um conjunto E de arestas, e uma
função f de E para {{u, v}|u, v V }.
 Pseudografo é mais geral que um multigrafo.
Prof. Luciana R. Cardoso
57

Tipos de Grafos
 Grafo ciclo
 Um grafo ciclo de n vértices, denominado Cn, n ≥ 3, é um
grafo simples com n vértices v1, v2, . . . , vn, e arestas v1v2,
v2v3, . . ., vn−1vn, vnv1.
 Exemplo: Grafos ciclos de 3, 4, e 5 vértices.
Prof. Luciana R. Cardoso
58
24/06/2018
30
Tipos de Grafos
 Grafo roda
 Um grafo roda, denominado Wn, é um grafo simples com n + 1
vértices que é obtido acrescentado um vértice ao grafo ciclo Cn,
n ≥ 3, e conectando este novo vértice a cada um dos n vértices
de Cn. Exemplo: Grafos rodas de 3, 4, e 5 vértices.
Prof. Luciana R. Cardoso
59
Tipos de Grafos
 Grafo Cubo-n
 Um grafo cubo-n de 2n vértices, denominado Qn, é um grafo
simples que representa os 2n strings de n bits. Dois vértices são
adjacentes sse os strings que eles representam diferem em
exatamente uma posição.
 O grafo Qn+1 pode ser obtido a partir do grafo Qn usando o
seguinte algoritmo:
 1. Faça duas cópias de Qn;
 2. Prefixe uma das cópias de Qn com 0 e a outra com 1;
 3. Acrescente uma aresta conectando os vértices que só diferem no
primeiro bit.
Prof. Luciana R. Cardoso
60
24/06/2018
31
Tipos de Grafos
 Grafo Cubo-n
 Exemplo: Grafos Qn, para n = 1, 2, e 3 vértices.
Prof. Luciana R. Cardoso
61
Tipos de Grafos
 Hipergrafo
 Um hipergrafo H(V, F) é definido pelo par de conjuntos V e F,
onde:
 V é um conjunto não vazio de vértices;
 F é um conjunto que representa uma “família” e partes não vazias
de V .
 Um hipergrafo é um grafo não dirigido em que cada aresta
conecta um número arbitrário de vértices.
Prof. Luciana R. Cardoso
62
24/06/2018
32
Terminologia de Grafos
Prof. Luciana R. Cardoso
63
Tipos de Grafos
 Grafo Complementar
 Um grafo é dito complementar de G se possui a mesma
ordem de G e se uma aresta (v,w) G, então (v,w) e vice-
versa. Exemplo:
Prof. Luciana R. Cardoso
64
G
G 
24/06/2018
33
Tipos de Grafos
 Grafo Complementar
 No caso de grafos dirigidos, o grafo complementar será
aquele que possui os mesmos vértices de G, possui todas as
arestas não presentes em G e possui o reverso das arestas de G.
Por exemplo:
Prof. Luciana R. Cardoso
65
G
Tipos de Grafos
 Grafo Bipartido
 Um grafo bipartido de m, n vértices, denominado Km,n, é um
grafo simples com vértices v1, v2, . . . , vm e w1,w2, . . . ,wn, que
satisfaz as seguintes propriedades:
 i, k = 1, 2, . . . ,m ^
 j, l = 1, 2, . . . , n
 1. uma aresta entre cada par de vértices vi e wj;
 2. ~ uma aresta entre cada par de vértices vi e vk;
 3. ~ uma aresta entre cada par de vértices wj e wl;
 Ou seja, o grafo pode ser dividido logicamente em dois
conjuntos de vértices, tal que toda aresta começa no vértice de
um dos conjuntos e termina no vértice do outro conjunto.
Prof. Luciana R. Cardoso
66





24/06/2018
34
Tipos de Grafos
 Grafo Bipartido
 Exemplo: Grafos bipartidos K3,2 e K3,3.
Prof. Luciana R. Cardoso
67
Tipos de Grafos
 Grafo Dirigido
 Um grafo é chamado de dirigido (ou dígrafo) se suas arestas
possuem orientação. Caso contrário o grafo é não dirigido. Em
termos leigos: será dirigido se suas arestas forem “flechas” que
apontam o vértice inicial e final de cada aresta.
Prof. Luciana R. Cardoso
68
24/06/2018
35
Tipos de Grafos
 Grafos Isomorfos
 Dois grafos são isomorfos se coincidirem os vértices de suas
representações gráficas, preservando as adjacências das
arestas. Em outras palavras, são isomorfos se têm a mesma
representação matemática, mas são representados
diferentemente graficamente.
Prof. Luciana R. Cardoso
69
Tipos de Grafos
 Grafos Isomorfos
 Observe os grafos G e H da figura a seguir .
Prof. Luciana R. Cardoso
70
24/06/2018
36
Tipos de Grafos
 Grafos Isomorfos
 A figura apresenta dois grafos diferentes mas que representam
a mesma situação. Os dois grafos apresentam 6 vértices e 10
arestas. Os dois têm as mesmas quantidades de vértices e de
arestas que preservam as correspondências.
 Ao estabelecer uma relação entre os conjuntos dos vértices dos
grafos G e H por uma função, temos uma relação de
correspondência 1 – a - 1. Ou seja, ao tomarmos o vértice 1 do
grafo G, a função fará uma correspondência com o vértice A do
grafo H.
Prof. Luciana R. Cardoso
71
Tipos de Grafos
 Grafos Isomorfos
 Os desenhos abaixo representam o mesmo grafo G:
 Conjuntos de vértices e arestas são idênticos;
 Funções aresta–vértice são as mesmas.
 Grafos isomorfos (do grego, o que significa a mesma forma).
Prof. Luciana R. Cardoso
72
24/06/2018
37
Tipos de Grafos
Prof. Luciana R. Cardoso
73
G
r
a
f
o
s
I
s
o
m
o
r
f
o
s
Tipos de Grafos
Prof. Luciana R. Cardoso
74
24/06/2018
38
Tipos de Grafos
Prof. Luciana R. Cardoso
75
Tipos de Grafos
Prof. Luciana R. Cardoso
76
24/06/2018
39
Tipos de Grafos
Prof. Luciana R. Cardoso
77
 Isomorfismo de grafos é uma relação de equivalência
no conjunto de grafos.
 Informalmente, temos que esta propriedade é:
 Reflexiva: Um grafo é isomorfo a si próprio.
 Simétrica: Se um grafo G é isomorfo a um grafo G’ então G’ é
isomorfo a G.
 Transitiva: Se um grafo G é isomorfo a um grafo G’ e G’ é
isomorfo a G’’ então G é isomorfo a G’.
Prof. Luciana R. Cardoso
78
24/06/2018
40
Tipos de Grafos
 Grafo valorado (ponderado)
 Um grafo valorado é um grafo em que cada aresta tem um
valor associado. Formalmente, um grafo valorado G = (V,E)
consiste de um conjunto V de vértices, um conjunto E de
arestas, e uma função f de E para P, onde P representa o
conjunto de valores (pesos) associados às arestas.
 Grafo valorado é usado para modelar vários problemas
importantes em Ciência da Computação.
Prof. Luciana R. Cardoso
79
Tipos de Grafos
 Grafo regular
 Um grafo é dito ser regular quando todos os seus vértices têm
o mesmo grau.
 Exemplo: Os grafos completos com 2, 3, 4, e 5 vértices são
grafos regulares.
Prof. Luciana R. Cardoso
80
24/06/2018
41
Tipos de Grafos
 Planar: É um grafo onde não há cruzamento de 
arestas.
Prof. Luciana R. Cardoso
81
Representação de um grafo
 Dado um grafo G = (V,E):
 V = conjunto de vértices.
 E = conjunto de arestas, que pode ser representado pelo
subconjunto de V × V .
 O tamanho da entrada de dados é medido em termos
do:
 Número de vértices |V |.
 Número de arestas |E|.
 Se G é conexo então |E| ≥ |V | − 1.
Prof. Luciana R. Cardoso
82
24/06/2018
42
Representação de Grafos em um 
Computador
 Para que um grafo seja armazenado em um
computador, é necessário definir dois aspectos:
 Quais informações devem ser consideradas
 Como armazenar asinformações no computador, ou seja,
definir a estrutura de dados que será utilizada.
 A estrutura de dados é particularmente importante,
pois a eficiência de um algoritmo que irá trabalhar
sobre o grafo vai depender da escolha certa de como
representar o grafo.
 De uma forma geral, pode-se representar um grafo
utilizando matrizes ou listas, como veremos a seguir.
Prof. Luciana R. Cardoso
83
Representação de um grafo
Estruturas de dados
 Matriz de adjacência:
 Forma preferida de representar grafos densos (|E| |V |2).
 Indica rapidamente (O(1)) se existe uma aresta conectando dois
vértices.
 Lista de adjacência:
 Representação normalmente preferida.
 Provê uma forma compacta de representar grafos esparsos (|E| « |V
|2).
 Matriz de incidência:
 Representação que inclui vértice e aresta.
 Dentre outras representações. As duas primeiras formas
acima são as principais formas de representar um grafo.
Prof. Luciana R. Cardoso
84

24/06/2018
43
Representação de um grafo
Estruturas de dados
1. FGVazio(Grafo): Cria um grafo vazio.
2. InsereAresta(V1,V2,Peso, Grafo): Insere uma aresta no
grafo.
3. ExisteAresta(V1,V2,Grafo): Verifica se existe uma
determinada aresta.
4. Obtem a lista de vértices adjacentes a um determinado
vértice (tratada a seguir).
5. RetiraAresta(V1,V2,Peso, Grafo): Retira uma aresta do
grafo.
6. LiberaGrafo(Grafo): Liberar o espaço ocupado por um
grafo.
Prof. Luciana R. Cardoso
85
Representação de um grafo
Estruturas de dados
7. ImprimeGrafo(Grafo): Imprime um grafo.
8. GrafoTransposto(Grafo,GrafoT): Obtém o
transposto de um grafo direcionado.
9. RetiraMin(A): Obtém a aresta de menor peso de
um grafo com peso nas arestas.
Prof. Luciana R. Cardoso
86
24/06/2018
44
Representação de um grafo 
Matriz de adjacência
 A matriz de adjacência de um grafo G = (V;A)
contendo n vértices é uma matriz n x n de bits, onde
A[i; j] é 1 (ou verdadeiro) se e somente se existe uma
conexão do vértice i para o vértice j.
 Para grafos ponderados A[i; j] contém o rótulo ou
peso associado com a aresta e, neste caso, a matriz
não é de bits.
 Se não existir uma aresta de i para j então é
necessário utilizar um valor que não possa ser usado
como rótulo ou peso.
Prof. Luciana R. Cardoso
87
Representação de um grafo não dirigido
Matriz de adjacência
 Exemplos:
Prof. Luciana R. Cardoso
88
24/06/2018
45
Representação de um grafo não dirigido
Matriz de adjacência
 Exemplos:
Prof. Luciana R. Cardoso
89
Representação de um grafo não dirigido
Matriz de adjacência
 Exemplos:
Prof. Luciana R. Cardoso
90
24/06/2018
46
Representação de um grafo dirigido
Matriz de adjacência
 Exemplos:
Prof. Luciana R. Cardoso
91
Representação de um grafo dirigido
Matriz de adjacência
 Exemplos: 
Prof. Luciana R. Cardoso
92
24/06/2018
47
Representação de um grafo dirigido
Matriz de adjacência
 Exemplos:
Prof. Luciana R. Cardoso
93
Representação de um grafo dirigido
Matriz de adjacência
 Exemplos:
Prof. Luciana R. Cardoso
94
24/06/2018
48
Representação de um grafo 
Matriz de adjacência: Análise
 É muito útil para algoritmos em que necessitamos
saber com rapidez se existe uma aresta ligando dois
vértices.
Prof. Luciana R. Cardoso
95
Representação de um grafo 
Lista de adjacência
 Vetor Adj de |V | listas, uma para cada vértice de V .
 Para cada vértice u 2 V , a lista Adj[u] contém
apontadores para todos os vértices v tal que a aresta
(u, v) 2 E (todos os vértices adjacentes a u em G).
 Definição vale para grafos não dirigidos e dirigidos.
 “comprimento da lista de adjacência”, vale:
 Grafo dirigido = |E|, cada aresta aparece uma única vez na
lista.
 Grafo não dirigido = 2|E|, cada aresta aparece duas vezes na
lista (entrada de u e entrada de v).
Prof. Luciana R. Cardoso
96
24/06/2018
49
Representação de um grafo 
Lista de adjacência usando apontadores
 Um arranjo Adj de |V | listas, uma para cada vértice em V .
 Para cada u V , Adj[u] contém todos os vértices adjacentes
a u em G.
Prof. Luciana R. Cardoso
97

Representação de um grafo 
Lista de adjacência usando arranjos
 Cab: endereços do último
item da lista de adjacentes
de cada vértice (nas |V|
primeiras posições) e os
vértices propriamente ditos
(nas |A| últimas posições)
 Prox: endereço do
próximo item da lista de
adjacentes.
 Peso: valor do peso de
cada aresta do grafo (nas
últimas |A| posições).
Prof. Luciana R. Cardoso
98
24/06/2018
50
 Os vértices de uma lista de adjacência são em geral
armazenados em uma ordem arbitrária.
 Possui uma complexidade de espaço O(|V | + |A|)
 É compacta e usualmente utilizada na maioria das
aplicações.
 A principal desvantagem é que ela pode ter tempo
O(|V |) para determinar se existe uma aresta entre o
vértice i e o vértice j, pois podem existir O(|V|)
vértices na lista de adjacentes do vértice i.
Prof. Luciana R. Cardoso
99
Representação de um grafo 
Lista de adjacência: Análise
Representação de um grafo
Lista de adjacência e grafo dirigido
Prof. Luciana R. Cardoso
100
24/06/2018
51
Representação de um grafo
Lista de adjacência e grafo dirigido
Prof. Luciana R. Cardoso
101
Representação de um grafo
Lista de adjacência e grafo dirigido
Prof. Luciana R. Cardoso
102
24/06/2018
52
Representação de um grafo
Lista de adjacência e grafo não dirigido
Prof. Luciana R. Cardoso
103
Representação de um grafo
Lista de adjacência e grafo não dirigido
Prof. Luciana R. Cardoso
104
24/06/2018
53
Representação de um grafo
Matriz de Incidência
 Dado um grafo G(V,A) de n vértices e m arestas a
matriz de incidência de G é denotada por B = [bij] é
uma matriz n x m definida por:
Prof. Luciana R. Cardoso
105



=
contrário caso 0
a de vérticeé vse 1 ji
ijb
Representação de um grafo
Matriz de Incidência
 Se o grafo G for orientado (dígrafo), então poderá ser 
definida como:
Prof. Luciana R. Cardoso
106





=
ji
ji
iji
a aresta à pertence não v vérticeo se 0
a de final efor vértic vse 1-
) v vérticeno laço umexistir se(ou a de inicial efor vértic vse 1
ijb
24/06/2018
54
Representação de um grafo
Matriz de Incidência
Prof. Luciana R. Cardoso
107
Representação de um grafo
Matriz de Custo
 Um grafo valorado pode ser representado por uma
matriz de custo w = {wij}, onde:
Prof. Luciana R. Cardoso
108






=
aresta) exista não caso seja,(ou A ) v,(v caso 
A ) v,(v se aresta, da custo
ji
ji
ijw
24/06/2018
55
Representação de um grafo
Listas de Arestas
 Pode-se representar um grafo em um computador
utilizando-se duas listas de vértices, representando
as arestas do grafo. As listas podem ser vetores
simples.
 A primeira lista contém os vértices de início de cada
aresta.
 A segunda lista contém os vértices onde cada uma
delas termina. Por exemplo:
Prof. Luciana R. Cardoso
109
Representação de um grafo
Listas de Arestas
Prof. Luciana R. Cardoso
110
24/06/2018
56
Representação de um grafo
Estrutura de Adjacência
 Um grafo pode ser representado por uma lista de
vértices e, para cada vértice da lista, é associada uma
lista dos seus respectivos sucessores. Exemplo:
Prof. Luciana R. Cardoso
111
Caminho e Conexidade
 Caminho:
 Formalmente temos o seguinte: Definição: seja G(V,A) um
grafo. Então define-se um caminho de G como sendo uma
sequência de arestas da forma (u,v),(v,w),(w,x),...,(y,z),
onde cada aresta pertence ao grafo G. O caminho denotado
é definido, também, como o caminho entre u e z e podeser
representado por: u v w x ... y z.
 O exemplo abaixo mostra um caminho entre d e c. O
caminho é denotado por d a b c.
Prof. Luciana R. Cardoso
112
24/06/2018
57
Caminho e Conexidade
 Cadeia
 Definição: uma cadeia é uma sequência de arestas de um
grafo G, tal que qualquer par de arestas subsequentes possuem
um vértice de incidência comum. Ao contrário da definição de
caminho, uma cadeia ignora a orientação das arestas.
 Portanto, todo caminho é uma cadeia, porém a recíproca nem
sempre é verdadeira. Veja o seguinte exemplo:
Prof. Luciana R. Cardoso
113
A sequência a b c d é um caminho, também uma
cadeia.
A sequência a b d c é uma cadeia, mas não é um
caminho.
Caminho e Conexidade
 Comprimento
 Definição: o número de arestas k que compõem um caminho
(ou cadeia) é denominado de comprimento do caminho (ou da
cadeia). Exemplo.
 O caminho a b c d é um caminho entre ‘a’ e ‘d’ de comprimento
igual a 3
Prof. Luciana R. Cardoso
114
24/06/2018
58
Caminho e Conexidade
 Caminho Simples x Trajetória
 Definição: se os vértices de um caminho (ou cadeia) forem
distintos (com exceção do vértice inicial e o vértice final), então
a sequência recebe o nome de caminho simples (ou cadeia
simples). Se as arestas da sequência forem distintas, então a
sequência recebe o nome de trajeto ou trajetória. Exemplo:
Prof. Luciana R. Cardoso
115
A sequência 1 2 3 4 5 é um caminho simples.
A sequência 1 2 3 4 2 é uma trajetória.
A sequência 1 2 3 4 2 1 é apenas uma 
sequência.
Caminho e Conexidade
 Grafo Conexo
 Definição: um grafo G é conexo se existe pelo menos um
caminho (ou cadeia) entre qualquer par de vértices de G. Caso
contrário o grafo é desconexo. Exemplo:
 Todo grafo desconexo é composto por subgrafos conexos
chamados de componentes. Por exemplo, o grafo b) é um grafo
desconexo composto por 2 componentes.
Prof. Luciana R. Cardoso
116
24/06/2018
59
Caminho e Conexidade
 Caminhos abertos e fechados
 Um caminho em G é denominado fechado se o vértice final é o
mesmo que o vértice inicial. Caso contrário, o caminho é
denominado aberto. Exemplo:
 De forma semelhante a um caminho fechado, uma cadeia
fechada de um grafo é uma cadeia de G tal que a aresta inicial e
a aresta final possuem um vértice de incidência em comum, ou
em outras palavras, se o vértice inicial e o vértice final se
confundem.
Prof. Luciana R. Cardoso
117
Caminho aberto: b d c e
Caminho fechado: b d c e b
Caminho e Conexidade
 Circuito e Ciclo
 Um circuito é um caminho simples fechado.
 Um ciclo é uma cadeia simples fechada. Exemplo:
 Um grafo que não contém nenhum ciclo é chamado de “grafo 
acíclico”.
Prof. Luciana R. Cardoso
118
Circuito: a b c d a
Ciclo: d c b d
24/06/2018
60
Busca em Grafos
 Um algoritmo de busca (ou varredura) é um
algoritmo que examina, sistematicamente, todos os
vértices e todas as arestas de um grafo.
 Cada aresta é examinado uma só vez. Depois de
visitar a ponta inicial de uma aresta, o algoritmo
percorre aresta e visita sua ponta final.
 Para justificar a palavra "busca", devemos imaginar
que o algoritmo percorre o grafo buscando todos os
vértices que são acessíveis a partir de um
determinado vértice em questão.
Prof. Luciana R. Cardoso
119
Busca em Grafos
 Há muitas maneiras de fazer uma tal busca. Cada
estratégia de busca é caracterizada pela ordem em
que os vértices são visitados.
 Assim, a ordem de visita torna-se essencial se
desejamos determinar outras propriedades além da
mera característica de um determinado vértice ser
alcançado a partir de outro.
 Aplicações:
 Computação gráfica; Técnicas de verificação formal;
Compiladores; Resolução de problemas; ...
Prof. Luciana R. Cardoso
120
24/06/2018
61
Busca em Grafos
 O algoritmo de busca em grafos podem então nos
mostrar outras características de grafos.
 Os algoritmos mais comumente discutidos são os
algoritmos de busca em largura (Breadth-first
search - BFS) e de busca em profundidade (Depth-
first search - DFS), que serão apresentados a seguir
Prof. Luciana R. Cardoso
121
Busca em Largura (BFS)
 A principal característica desse algoritmo é que a
busca encontra primeiro todos os vértices que estão à
distância 1 da origem da busca, em seguida os que
estão à distância 2, e assim por diante.
 No algoritmo de busca em largura, a lista de vértices
obedece a política FIFO (First-In-First-Out): o
vértice que sai da lista é sempre o que está lá há mais
tempo.
 No exemplo a seguir, vamos supor que estejamos
buscando o caminho entre 1 e 5.
Prof. Luciana R. Cardoso
122
24/06/2018
62
Busca em Largura (BFS): Exemplo
 No início todos os vértices são pintados de branco.
 Para o exemplo o vértice de origem é o 1, sendo
marcado com “largura” igual a zero.
 O algoritmo pinta de cinza este vértice e o coloca em
uma fila Q.
Prof. Luciana R. Cardoso
123
Busca em Largura (BFS): Exemplo
 No próximo passo, o algoritmo retira o vértice 1 da
fila Q e pinta-o de preto
 O algoritmo inclui no fim da fila todos os nós
adjacentes ao vértice 1 e mapeando-os com “largura”
igual a 1. No caso, temos apenas o vértice 2. O vértice
2 é então pintado de cinza.
Prof. Luciana R. Cardoso
124
24/06/2018
63
Busca em Largura (BFS): Exemplo
 O vértice 2 é retirado da fila Q e pintado de preto,
enquanto os vértices 3 e 5 são colocados na fila Q e
mapeados com “largura” igual a 2.
 O vértice 1 não é colocado na fila (apesar de haver
uma conexão), pois já está pintado de preto.
Prof. Luciana R. Cardoso
125
Busca em Largura (BFS): Exemplo
 O vértice 3 é retirado da fila Q e pintado de preto,
enquanto o vértice 4 é colocado na fila Q e mapeado
com “largura” igual a 3.
Prof. Luciana R. Cardoso
126
24/06/2018
64
Busca em Largura (BFS): Exemplo
 Em seguida o vértice 5 também é visitado, pintado de
preto e retirado da fila Q. Como sua única conexão é
com o vértice 2 (já pintado de preto), nada é feito.
Prof. Luciana R. Cardoso
127
Busca em Largura (BFS): Exemplo
 No término da execução deste exemplo o vértice 4 é
pintado de preto e retirado da fila Q. Como suas
conexões levam a vértices já pintados de preto (1 e 5),
nada é feito e a fila torna-se vazia (fim do algoritmo).
Prof. Luciana R. Cardoso
128
24/06/2018
65
Busca em Largura (BFS): Exemplo
 Para o caminho entre origem e destino parte-se do
vértice de destino, examinado seus predecessores até
chegar à origem. Depois inverte-se o vetor
conseguido.
 Para este exemplo, o caminho é 1 →2→5. A seguir é
apresentado um pseudocódigo do algoritmo de busca
em largura.
Prof. Luciana R. Cardoso
129
Busca em Largura (BFS): Exemplo
Prof. Luciana R. Cardoso
130
24/06/2018
66
Busca em Largura (BFS): Exemplo
 a) Seleciona-se um vértice para iniciar o
caminhamento.
 b) Visitam-se os vértices adjacentes, marcando-os
como visitados.
 c) Coloca-se cada vértice adjacente numa fila.
 d) Após visitar os vértices adjacentes, o primeiro da
fila torna-se o novo vértice inicial. Reinicia-se o
processo.
 e) O caminhamento termina quanto todos os vértices
tiverem sido visitados ou o vértice procurado for
encontrado.
Prof. Luciana R. Cardoso
131
Busca em Largura (BFS): Exemplo
Prof. Luciana R. Cardoso
132
24/06/2018
67
Busca em Largura (BFS): Exemplo
Prof. Luciana R. Cardoso
133
Exercícios
 Simule o algoritmo de busca em largura no gráfico
abaixo, a partir do vértice 1, e determine:
 Qual a largura de cada vértice do grafo?
 Qual o caminho encontrado entre 1 e 5?
 Suponha que a lista de adjacências mantém os
vértices em ordem numérica, isto é, Adj[3] = {2,4}
Prof. Luciana R. Cardoso
13424/06/2018
68
Busca em Profundidade (DFS)
 A estratégia seguida pela busca em profundidade é, como
seu nome implica, procurar cada vez mais fundo no grafo.
 Nessa busca as arestas são exploradas a partir do vértice v
mais recentemente descoberto que ainda possui arestas
inexploradas saindo dele.
 A estratégia seguida pela busca em profundidade é, como
seu nome implica, procurar cada vez mais fundo no grafo.
 Nessa busca as arestas são exploradas a partir do vértice v
mais recentemente descoberto que ainda possui arestas
inexploradas saindo dele.
Prof. Luciana R. Cardoso
135
Busca em Profundidade (DFS)
 Quando todas as arestas alcançadas a partir do
vértice de origem são visitadas a busca regressa para
explorar as arestas que deixam o vértice do qual v foi
descoberto.
 Para o exemplo a seguir, tentaremos descobrir o
caminho de 1 a 5.
Prof. Luciana R. Cardoso
136
24/06/2018
69
Busca em Profundidade (DFS): Exemplo
 No início todos os vértices são brancos, mas partindo
do vértice 1, este é pintado de cinza e sua aresta é
examinada, levando ao vértice 2. O vértice 1 é
marcado com distância 0.
Prof. Luciana R. Cardoso
137
Busca em Profundidade (DFS): Exemplo
 O vértice 1 é pintado de preto. O vértice 2 é pintado
de cinza, enquanto suas arestas serão examinadas e é
atribuído a ele uma distância 1. A primeira aresta de
2 leva ao vértice 1, já pintado de preto. Partindo para
a segunda aresta, esta leva ao vértice 3.
Prof. Luciana R. Cardoso
138
24/06/2018
70
Busca em Profundidade (DFS): Exemplo
 O vértice 3 é então pintado de cinza e a ele é
atribuído uma distância 2. Sua única aresta é
examinada, levando ao vértice 4.
Prof. Luciana R. Cardoso
139
Busca em Profundidade (DFS): Exemplo
 O vértice 3 é pintado de preto e o vértice 4 é pintado
de cinza, sendo que a ele é atribuído uma distância 3.
Suas arestas serão examinadas. A primeira leva a um
nó já pintado de preto, logo não é analisada. A
segunda, leva ao vértice 5.
Prof. Luciana R. Cardoso
140
24/06/2018
71
Busca em Profundidade (DFS): Exemplo
 O vértice 4 é pintado de preto e o vértice 5 é pintado
de cinza, sendo que a ele é atribuído uma distância 4.
Sua aresta é examinada, constatando-se que leva a
um vértice já pintado de cinza.
Prof. Luciana R. Cardoso
141
Busca em Profundidade (DFS): Exemplo
 O vértice 5 é pintado de preto e parte-se para o
exame da última aresta pertencente ao vértice 2.
Prof. Luciana R. Cardoso
142
24/06/2018
72
Busca em Profundidade (DFS): Exemplo
 Como neste momento esta aresta remete a um
vértice já pintado de preto (vértice 5), o vértice 2
também é pintado de preto e o algoritmo é
terminado. Diferente da busca em largura, este
algoritmo produz um caminho 1 → 2 → 3 → 4 →5
para o caminho de 1 a 5.
Prof. Luciana R. Cardoso
143
Busca em Profundidade (DFS)
 Pesquisa em profundidade:
 Explora os vértices do grafo a partir de arestas não exploradas
ainda, mais fundo no grafo quanto possível.
 Quando todas as arestas de v tiverem sido exploradas, a
pesquisa volta para explorar outras arestas do vértice do qual v
foi descoberto.
 Processo continua até que todos os vértices alcançáveis a partir
de uma origem tenham sido descobertos.
 Se existe vértice não descoberto ainda então um novo vértice é
selecionado e o processo começa todo novamente.
Prof. Luciana R. Cardoso
144
24/06/2018
73
Busca em Profundidade (DFS)
 Para acompanhar o progresso do algoritmo cada vértice é
colorido de branco, cinza ou preto.
 Todos os vértices são inicializados branco.
 Quando um vértice é descoberto pela primeira vez ele
torna-se cinza, e é tornado preto quando sua lista de
adjacentes tenha sido completamente examinada.
 d[v]: tempo de descoberta
 t[v]: tempo de término do exame da lista de adjacentes de
v.
 Estes registros são inteiros entre 1 e 2jV j pois existe um
evento de descoberta e um evento de término para cada um
dos jV j vértices.
Prof. Luciana R. Cardoso
145
Busca em Profundidade (DFS)
 O algoritmo de busca em profundidade na sua forma mais
robusta utiliza um recurso computacional chamado
recursão, em que uma dada função “chama a si mesma”.
 Um pseudocódigo para o algoritmo de busca em
profundidade que encontra o caminho entre dois vértices é
mostrado a seguir.
 Claramente há uma grande diferença no modo de
implementação e nos resultados dos dois algoritmos.
 Desta forma, quando há a necessidade de obtenção do
caminho mínimo entre dois vértices, outros algoritmos
podem ser utilizados.
Prof. Luciana R. Cardoso
146
24/06/2018
74
Busca em Profundidade (DFS)
Prof. Luciana R. Cardoso
147
Busca em Profundidade (DFS)
 a) Seleciona-se um vértice para iniciar o caminhamento.
 b) Visita-se um primeiro vértice adjacente, marcando-o
como visitado.
 c) Coloca-se o vértice adjacente visitado numa pilha.
 d) O vértice visitado torna-se o novo vértice inicial.
 e) Repete-se o processo até que o vértice procurado seja
encontrado ou não haja mais vértices adjacentes. Se
verdadeiro, desempilha-se o topo e procura-se o próximo
adjacente, repetindo o algoritmo.
 f) O processo termina quando o vértice procurado for
encontrado ou quando a pilha estiver vazia e todos os
vértices tiverem sido visitados.
Prof. Luciana R. Cardoso
148
24/06/2018
75
Distância
 Um caminho C num grafo é mínimo se não existe
outro caminho com mesma origem e mesmo término
que C mas comprimento menor que o de C.
 A distância de um vértice s a um vértice t num grafo
é o comprimento de um caminho mínimo de s a t. Se
não existe caminho algum de s a t, a distância de s a t
é infinita.
 Em geral, num grafo direcionado a distância de um
vértice s a um vértice t é diferente da distância de t a
s. Se o grafo é não-orientado, entretanto, as duas
distâncias são iguais.
Prof. Luciana R. Cardoso
149
Algoritmos de Caminhos Mínimos
 O caminho de um vértice a outro vértice é mínimo se
não existe outro caminho entre eles que tenha menos
arcos.
 O problema de encontrar o caminho mais curto entre
dois nós de um grafo ou uma rede é um dos
problemas clássicos da Ciência da Computação. Este
problema consiste, genericamente, em encontrar o
caminho de menor custo entre dois nós da rede,
considerando a soma dos custos associados aos arcos
percorridos.
Prof. Luciana R. Cardoso
150
24/06/2018
76
Algoritmos de Caminhos Mínimos
 Grafos Ponderados: 
 Muitas aplicações associam um número a cada aresta de um
grafo. Diremos que esse número é o custo da aresta, que pode
ser remetido a uma característica física da conexão.
 Por exemplo, se duas arestas de um grafo representam
conexões de cabos óticos entre cidades A, B, e C (vértices do
grafo), sendo que a distância entre A e B é o dobro da distância
de A a C, então pode-se atribuir um custo maior à aresta que
liga os vértices A e B.
 Dependendo da aplicação, pode ser mais apropriado dizer
"peso" ou "comprimento" no lugar de "custo".
Prof. Luciana R. Cardoso
151
Algoritmos de Caminhos Mínimos
 Exemplo: Caminho de Custo Mínimo
 Se o grafo ponderado e direcionado abaixo for tomado como
exemplo, o caminho mínimo C de 1 a 5 tem custo d igual a 2,
levando a um caminho 1 → 2 → 5. Veja que existe um outro
caminho 1 → 2 → 3 → 4 → 5, mas este possui custo d igual
a 5.
Prof. Luciana R. Cardoso
152
24/06/2018
77
Algoritmos de Caminhos Mínimos
 Busca de Caminhos Mínimos
 Para a busca de caminhos mínimos em grafos há algoritmos
específicos que executam a tarefa.
 Entretanto há formas específicas para tratar o problema, sendo
diferentes quando busca-se caminhos mínimos a partir de um
dado vértice ou quando se buscam os caminhos mínimos entre
todos os pares de vértices.Prof. Luciana R. Cardoso
153
Algoritmos de Caminhos Mínimos
 O mais famoso algoritmo para resolver o problema
de caminho mínimo em grafos é o algoritmo de
Dijkstra (1959). Este algoritmo apenas funciona se
os custos associados aos arcos não forem negativos,
mas isso não é muito importante na maioria dos
problemas práticos pois, em geral, os custos
associados aos arcos são em geral grandezas
fisicamente mensuráveis.
Prof. Luciana R. Cardoso
154
24/06/2018
78
Algoritmo de Dijkstra
 Um algoritmo eficiente para o de obtenção do
caminho mínimo em grafos com custos não
negativos é o chamado algoritmo de Dijkstra.
 O algoritmo pode ser usado, em particular, para
encontrar um caminho de custo mínimo de um dado
vértice a outro, ou a todos os outros vértices.
 O algoritmo de Dijkstra funciona de forma iterativa,
passo a passo, como mostrado a seguir. A entrada é a
matriz de adjacências do grafo.
Prof. Luciana R. Cardoso
155
Algoritmo de Dijkstra
1. Como primeiro passo é atribuída uma distância para todos os pares
de vértices. De início é atribuída uma distância infinita para todos,
menos para o vértice de origem.
2. Marque todos os vértices como não visitados e defina o vértice inicial
como vértice corrente.
3. Para este vértice corrente, considere todos os seus vértices vizinhos
não visitados e calcule a distância a partir do vértice. Se a distância
for menor do que a definida anteriormente, substitua a distância.
4. Quando todos os vizinhos do vértice corrente forem visitados,
marque-o como visitado, o que fará com que ele não seja mais
analisado (sua distância é mínima e final).
5. Eleja o vértice não visitado com a menor distância (a partir do vértice
inicial) como o vértice corrente e continue a partir do passo 3.
Prof. Luciana R. Cardoso
156
24/06/2018
79
Algoritmo de Dijkstra
 Mantém um conjunto S de vértices cujos caminhos
mais curtos até um vértice origem já são conhecidos.
 Produz uma árvore de caminhos mais curtos de um
vértice origem s para todos os vértices que são
alcançáveis a partir de s.
 Utiliza a técnica de relaxamento:
 Para cada vértice v 2 V o atributo p[v] é um limite
superior do peso de um caminho mais curto do vértice origem
s até v.
 O vetor p[v] contém uma estimativa de um caminho
mais curto.
Prof. Luciana R. Cardoso
157
Algoritmo de Dijkstra
 O relaxamento de uma aresta (u; v) consiste em
verificar se é possível melhorar o melhor caminho
até v obtido até o momento se passarmos por u.
Prof. Luciana R. Cardoso
158
24/06/2018
80
Algoritmo de Dijkstra: Exemplo
 Para o exemplo a seguir, o vértice 1 é o vértice origem
e o vértice corrente do início do algoritmo. A
distância dele para todos os outros vértices é
mostrada em vermelho. A distância para seu vizinho
(vértice 2) é igual a 1.
Prof. Luciana R. Cardoso
159
Algoritmo de Dijkstra: Exemplo
 O vértice 2 passa a ser o vértice corrente. A partir
dele, atinge-se os vértices 3 e 5, sendo as respectivas
distâncias calculadas para 2 (ao invés de infinito) e 2.
Prof. Luciana R. Cardoso
160
24/06/2018
81
Algoritmo de Dijkstra: Exemplo
 O vértice 3 é o vértice corrente. A partir dele alcança-
se o vértice 4, com distância 4. Neste ponto todos os
vértices foram visitados e o vetor de distâncias
mínimas a partir do vértice 1 é D = [0 1 2 4 2].
Prof. Luciana R. Cardoso
161
Algoritmo de Dijkstra: Exemplo
 Pseudocódigo
Prof. Luciana R. Cardoso
162
24/06/2018
82
Algoritmo de Dijkstra: Exemplo
Prof. Luciana R. Cardoso
163
Algoritmo de Dijkstra: Exemplo
 Porque o Algoritmo de Dijkstra Funciona
 O algoritmo usa uma estratégia gulosa: sempre escolher o
vértice mais leve (ou o mais perto) em V - S para adicionar ao
conjunto solução S, O algoritmo de Dijkstra sempre obtém os
caminhos mais curtos, pois cada vez que um vértice é
adicionado ao conjunto S temos que p[u] = δ(Raiz; u).
Prof. Luciana R. Cardoso
164
24/06/2018
83
Algoritmo de Dijkstra: Exemplo
Prof. Luciana R. Cardoso
165
Mostrar o algoritmo para esse exemplo
Grafos Eulerianos
 É aquele que possui um ciclo que contem todas as
suas arestas. Este ciclo é dito ser um ciclo euleriano.
 O grafo da figura abaixo, é euleriano já que ele
contém o ciclo: (u1, u2, u3, u4, u5, u3, u1, u6, u2, u7, u3,
u6, u7, u1), que é euleriano
Prof. Luciana R. Cardoso
166
24/06/2018
84
Grafos Eulerianos
 Definição: Seja G um grafo. Um circuito
Euleriano é um circuito que contém cada vértice e
cada aresta de G. É uma sequência de vértices e
arestas adjacentes que começa e termina no mesmo
vértice de G, passando pelo menos uma vez por cada
vértice e exatamente uma única vez por cada aresta
de G.
Prof. Luciana R. Cardoso
167
Grafos Eulerianos
 Teorema: Se um grafo possui um circuito Euleriano,
então cada vértice do grafo tem grau par.
 Determine se o grafo abaixo tem um circuito
Euleriano. Em caso positivo ache um circuito
Euleriano para o grafo.
 Os vértices a, b, c, f, g, i, j têm grau 2.
 Os vértices d, e, h têm grau 4.
 Pelo teorema anterior, este grafo possui um circuito Euleriano.
Prof. Luciana R. Cardoso
168
24/06/2018
85
Grafos Eulerianos
 Teorema: Um grafo G tem um circuito Euleriano
sse G é c
 Definição: Seja G um grafo e seja v e w dois vértices
de G. Um Trajeto Euleriano de v para w é uma
sequência de arestas e vértices adjacentes que
começa em v, termina em w e passa por cada vértice
de G pelo menos uma vez e passa por cada aresta de
G exatamente uma única vez.onexo e cada vértice de
G tem grau par.
Prof. Luciana R. Cardoso
169
Grafos Eulerianos
 Exemplo: O grafo da Figura abaixo é euleriano, pois
nele podemos definir o circuito euleriano a, f ,b,c,e,d
,a,b,d,c,a .
Prof. Luciana R. Cardoso
170
24/06/2018
86
Grafos Eulerianos
 Exemplo: O grafo da Figura abaixo é
semi‐euleriano, pois nele podemos definir o trajecto
euleriano a,b,c,e,d,a,c,d,b .
Prof. Luciana R. Cardoso
171
Grafos Eulerianos
 O grafo da Figura abaixo não é euleriano nem
semi‐euleriano, pois não é possível definir, neste
grafo, um circuito ou um trajecto euleriano.
Prof. Luciana R. Cardoso
172
24/06/2018
87
Grafos Eulerianos
 Exemplo: Observe‐se o grafo G da Figura abaixo.
Pelo Teorema, facilmente se conclui que existe um
circuito de Euler.
Prof. Luciana R. Cardoso
173
Grafos Eulerianos
 Conclusão: dizemos que um grafo G com n vértices
e m arestas é Euleriano se ele possui uma trilha
fechada de mesmo comprimento m, começando e
terminado no mesmo vértice. Ou seja, percorrer o
grafo formando um ciclo fechado que utiliza cada
aresta uma única vez.
Prof. Luciana R. Cardoso
174
24/06/2018
88
Grafos Hamiltonianos
 Paralelamente à idéia dos grafos eulerianos, de
passar por cada aresta uma única vez, os grafos
hamiltonianos consistem em passar por cada
vértice uma única vez. Caminho hamiltoniano em
um grafo é o caminho que visita cada vértice
exatamente uma vez.
 Um ciclo hamiltoniano é um ciclo que visita cada
vértice uma só vez (uma trilha fechada que começa e
termina no mesmo vértice).
Prof. Luciana R. Cardoso
175
Grafos Hamiltonianos
 Recursos computacionais são necessários para testar
todas as possíveis soluções. Caso o problema
apresentar 20 vértices, o número de soluções
possíveis é 20!. Caso tenhamos 300 vértices teremos
300! soluções para testar, ou seja, quanto maior o
número de vértices maior será o tempo de verificar
qual das trajetórias hamiltonianas é a melhor. Até
hoje, não existe um algoritmo hamiltoniano capaz de
minimizar a solução. Todos os esforços de estudiosos
comprovam que isto não é possível.
Prof. Luciana R. Cardoso
176
24/06/2018
89
Grafos Hamiltonianos
 O problemado carteiro viajante representa um
problema Hamiltoniano, no qual um carteiro,
viajando por várias cidades uma única vez e
retornando à sua cidade de origem, percorrerá a
menor distância possível.
Prof. Luciana R. Cardoso
177
Grafos Hamiltonianos
 O Problema do Caixeiro Viajante
 Em inglês, Traveling Salesman Problem, ou TSP.
 Suponha o mapa abaixo mostrando quatro cidades (A,B,C,D) e
as distâncias em km entre elas.
 Um caixeiro viajante deve percorrer um circuito
Hamiltoniano, ou seja, visitar cada cidade exatamente uma
única vez e voltar a cidade inicial.
 Que rota deve ser escolhida para minimizar o total da
distância percorrida?
Prof. Luciana R. Cardoso
178
24/06/2018
90
Grafos Hamiltonianos
 O Problema do Caixeiro Viajante
 Possível solução:
 Enumere todos os possíveis circuitos Hamiltonianos começando e
terminando em A;
 Calcule a distância de cada um deles;
 Determine o menor deles.
Prof. Luciana R. Cardoso
179
Assim, tanto a rota ABCDA ou ADCBA tem uma distância total de 125 km.
Grafos Hamiltonianos
 A solução do TSP é um circuito Hamiltoniano que
minimiza a distância total percorrida para um grafo
valorado arbitrário G com n vértices, onde uma
distância é atribuída a cada aresta.
 Algoritmo para resolver o TSP:
 Atualmente, força bruta, como feito no
Prof. Luciana R. Cardoso
180
24/06/2018
91
Árvore
 Definição: Uma árvore (também chamada de
árvore livre) é um grafo não dirigido acíclico e
conexo.
Prof. Luciana R. Cardoso
181
Floresta
 Definição: Uma floresta é um grafo não dirigido
acíclico podendo ou não ser conexo.
Prof. Luciana R. Cardoso
182
24/06/2018
92
Árvore geradora
 Definição: Uma árvore geradora de um grafo G é
um grafo que contém cada vértice de G e é uma
árvore.
 Esta definição pode ser estendida para floresta
geradora.
 Proposição:
 Cada grafo conexo tem uma árvore geradora.
 – Duas árvores geradores quaisquer de um grafo têm a mesma
quantidade de arestas.
Prof. Luciana R. Cardoso
183
Árvore geradora
 Seja o grafo G abaixo
Prof. Luciana R. Cardoso
184
Este grafo possui o circuito v2v1v4v2.
A remoção de qualquer uma das três
arestas do circuito leva a uma árvore.
Assim, todas as três árvores geradoras são:
24/06/2018
93
Árvore geradora mínima ou
Minimal Spanning Tree
 O grafo de rotas da
companhia aérea que
recebeu permissão para
voar pode ser “rotulado”
com as distâncias entre
as cidades:
 Suponha que a
companhia deseja voar
para todas as cidades
mas usando um conjunto
de rotas que minimiza o
total de distâncias
percorridas:
Prof. Luciana R. Cardoso
185
Árvore geradora mínima
 Definição: Um grafo com peso é um grafo onde
cada aresta possui um peso representado por um
número real. A soma de todos os pesos de todas as
arestas é o peso total do grafo. Uma árvore
geradora mínima para um grafo com peso é
uma árvore geradora que tem o menor peso total
possível dentre todas as possíveis árvores geradoras
do grafo.
 Se G é um grafo com peso e e uma aresta de G então:
 w(e) indica o peso da aresta e, e
 w(G) indica o peso total do grafo G.
Prof. Luciana R. Cardoso
186
24/06/2018
94
Algoritmos para obter a árvore geradora 
mínima
 Algoritmo de Kruskal.
 Algoritmo de Prim.
Prof. Luciana R. Cardoso
187
Algoritmo de Kruskal
 Idéia básica:
 Seleciona a aresta de menor peso que conecta duas árvores de
uma floresta.
 Repita o processo até que todos os vértices estejam conectados
sempre
 preservando a invariante de se ter uma árvore.
Prof. Luciana R. Cardoso
188
24/06/2018
95
Algoritmo de Kruskal
Prof. Luciana R. Cardoso
189
Algoritmo de Kruskal
Prof. Luciana R. Cardoso
190
24/06/2018
96
Algoritmo de Prim
 Idéia básica:
 Tomando como vértice inicial A, crie uma fila de prioridades
classificada pelos pesos das arestas conectando A.
 Repita o processo até que todos os vértices tenham sido
visitados.
Prof. Luciana R. Cardoso
191
Algoritmo de Prim
Prof. Luciana R. Cardoso
192
24/06/2018
97
Exercícios
1 - Para o grafo G abaixo, descreva:
a) A matriz de incidencia M(G);
b) A matriz de adjacencia A(G).
Prof. Luciana R. Cardoso
193
Exercícios
2 - Aplique o algoritmo de Dijkstra no grafo
abaixo, considerando o vértice υ5 como raiz.
Mostrar todos os passos do algoritmo e, ao
final, indicar os caminhos de υ5 aos outros
vértices, destacando o custo total para cada
caminho.
Prof. Luciana R. Cardoso
194
24/06/2018
98
Exercícios
3 - Suponha que o grafo a seguir represente
ruas que ligam regiões de uma cidade, onde
os pesos das arestas são as distancias entre
as regiões. Sabe-se que o correio da cidade é
representado pelo vértice v2 e se sabe
também que o carteiro, ao sair da central de
correios, precisa cobrir todas as ruas,
passando por estas pelo menos uma vez e de
modo que seu percurso seja o menor
possível.
Prof. Luciana R. Cardoso
195
Exercícios
a) Mostre que o grafo abaixo e euleriano,
utilizando como base o que diz o teorema
sobre grafos eulerianos dado em sala de
aula.
b) Se o grafo e euleriano, e necessário
considerarmos os pesos para encontrar a
solução para o carteiro? Por que?
c) Se sua resposta acima foi “nao”, quando
então é necessário considerar os pesos?
Prof. Luciana R. Cardoso
196
24/06/2018
99
Exercícios
Prof. Luciana R. Cardoso
197
Exercícios
4 - Grafos hamiltonianos
 a) Mostre que o grafo abaixo e hamiltoniano,
utilizando o segundo teorema dado em sala
de aula sobre grafos hamiltonianos
Prof. Luciana R. Cardoso
198
24/06/2018
100
Exercícios
5 - Observe o grafo com bastante atenção e responda 
as questões abaixo:
Prof. Luciana R. Cardoso
199
Exercícios
 1. Vocês conseguem passar o lápis por toda a figura
sem levantar o lápis do papel e passar uma única vez
por cada aresta?
 2. Vocês começaram por qual vértice?
 3. Agora, determine o grau de cada vértice.
 4. Será que conseguem realizar a mesma atividade
começando por outro vértice?
 5. Podemos fazer a atividade partindo de qualquer
vértice? Por quê?
Prof. Luciana R. Cardoso
200
24/06/2018
101
Exercícios
6 - João é entregador de pizza. Com sua moto ele
calculou o tempo gasto (em minutos) para deslocar
nos pontos principais do bairro, como mostra a
Figura a seguir. Seu ganho é por entrega, ele tem que
entregar uma pizza na Buganville no 32, referência
em frente a Escola Ovidio.
a) Qual o melhor caminho que João terá que tomar? Ou
seja, qual o trajeto que gasta menos tempo?
Prof. Luciana R. Cardoso
201
Prof. Luciana R. Cardoso
202
24/06/2018
102
Exercícios
7 - Esta atividade foi proposta por Hamilton em 1856.
Este jogo tem o nome de "Icosain Game", que
consiste em descobrir uma maneira de sair de
Londres e viajar para as outras cidades do mundo
uma única vez, diferente das atividades Eulerianas,
que consiste em passar por cada aresta uma única
vez, você deverá passar por cada vértice uma única
vez, sempre retornando ao ponto de partida. Os
vértices são representações das cidades e as arestas
são como elas estão conectadas
Prof. Luciana R. Cardoso
203
Exercícios
Prof. Luciana R. Cardoso
204
24/06/2018
103
Exercícios
Prof. Luciana R. Cardoso
205