DCC059-Roteiro_Professor

Prévia do material em texto

DCC059 Teoria dos GrafosDCC059 Teoria dos Grafos
Stênio Sã
Universidade Federal de Juiz de ForaUniversidade Federal de Juiz de Fora
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
2DCC059 - Teoria dos Grafos
Unidade 1: CONCEITOS BÁSICOS
3DCC059 - Teoria dos Grafos
Aula 1: visão geral da 
disciplina
4DCC059 - Teoria dos Grafos
5DCC059 - Teoria dos Grafos
Em 1735, Euler provou que o problema não 
tem solução.
A prova de Euler deu início ao que se conhece 
hoje como Teoria dos Grafos.
6DCC059 - Teoria dos Grafos
Grafos são estruturas bastante utilizadas para representar ou modelar 
soluções/problemas do mundo real;
Em geral, estes modelos se dão através de representação gráfica, onde 
cada elemento do mundo real (no contexto do problema) é representado por 
um ponto, círculo ou outra figura, e as relações entre elementos são 
representados por linhas, que unem elementos da relação.
Exemplo:
G=(V,E)
V={A, B, C, D)
E={a,b,c,d,e,f,g} 
7DCC059 - Teoria dos Grafos
8DCC059 - Teoria dos Grafos
9DCC059 - Teoria dos Grafos
Note que um mesmo grafo pode ser representado graficamente de diferentes 
formas.
10DCC059 - Teoria dos Grafos
Aplicações de Grafos
11DCC059 - Teoria dos Grafos
Aplicações de Grafos
12DCC059 - Teoria dos Grafos
Aplicações de Grafos
13DCC059 - Teoria dos Grafos
Aplicações de Grafos
14DCC059 - Teoria dos Grafos
e3
e2
e4
e5
e9e6
e8
e10
e11
e1 e12e7
v1
v2
v3 v4
v5
v6
v7
v8
v9
V = {v1, v2, v3, v4, v5, v6, v7, v8, v9} n = 9
E = {e1, e2, e3, e4,..., e9, e10, e11, e12} m = 12
Aulas 2, 3 e 4 – Conceitos Aulas 2, 3 e 4 – Conceitos 
BásicosBásicos
• Grafo: Geometricamente, um grafo é um conjunto 
de pontos (vértices ou nós) conectados por linhas 
(arestas).
15DCC059 - Teoria dos Grafos
 V = {v1, v2, ..., vn} |V | = n (ordem de G)
 E = {e1, e2, ..., em} |E | = m
 G = (V, E)
vértices arestas
Conceitos BásicosConceitos Básicos
• Grafo: Geometricamente, um grafo é um conjunto 
de pontos (vértices ou nós) conectados por linhas 
(arestas).
• Um grafo G pode ser definido por um par (V,E), onde 
V é o conjunto de Vértices e E é o conjunto de 
arestas.
16DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Dizemos que: u e v são adjacentes
e é incidente a v
e é incidente a u
• Aresta: é definida por um par não-ordenado de nós, suas 
extremidades:
e = (u , v)
e5
e4
e2 e3
e1
e = (u, v) é um laço se u =v
arestas paralelas possuem 
as mesmas extremidades
17DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
e3
e2
e4
e5
e9e6
e8
e10
e11
e1 e12e7
v1
v2
v3 v4
v5
v6
v7
v8
v9
grau de um nó v d(v) : é o número de arestas incidentes 
a v, ou seja, número de nós adjacentes a v.
d(v1) = d(v2) = d(v8) = d(v9) = 2
d(v3) = d(v4) = d(v5) = d(v6) = 3
d(v7) = 4
Quando d(v) = 0, diz-se que v é um vértice isolado
18DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Teorema: o número de nós de grau ímpar em um grafo 
finito é par.
Demonstre: 
19DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Um grafo G=(V,E) é regular se d(vi) = d(vj) para todo i, 
j tal que vij e vj pertencente a V.
Grafo k-regular: é o grafo em que todos os nós têm grau k.
20DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
e3
e2
e4
e5
e9e6
e8
e10
e11
e1 e12e7
v1
v2
v3 v4
v5
v6
v7
v8
v9
grau de um grafo G=(V,E) d(G): é o valor do maior 
inteiro d(v) para todo v pertencente a V.
d(G) = 4
21DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Classes especiais de grafos
• Quando tanto V quanto E são conjuntos finitos, dizemos 
que G é um grafo finito. 
• G é um grafo vazio se E for vazio.
• G é u grafo trivial se sua ordem for 1.
• G é um multigrafo se não possui laços e apresenta 
arestas paralelas.
• G é um grafo simples se não possui laços nem arestas 
paralelas.
22DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
grafo completo: um grafo G é dito completo se existe uma aresta 
associada a cada par de vértices de G.
Teorema: o número m de arestas em um grafo completo de n nós 
é dado por: m=n*(n-1)/2.
Prove por indução!
23DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Kn: grafo completo com n nós
K3 K4 K5
Kn é (n-1)-regular
24DCC059 - Teoria dos Grafos
????????
????????
Conceitos BásicosConceitos Básicos
Seja G=(V,E): quando o conjunto V pode ser particionado em dois 
subconjuntos disjuntos Vi e Vj tais que Vi ∩ Vj = Φ; Vi Ụ Vj = V; 
 e ∀ (u,v) Є E ⇒ u Є Vi e v Є Vj, dizemos que G é um grafo 
bipartido.
V1 V2
????????
????????
25DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Grafo bipartido completo Kp,q: quando o conjunto de nós pode 
ser particionado em dois subconjuntos V1 e V2 | |V1 |=p, |V2 
|=q, qualquer aresta possui uma extremidade em V1 e a outra 
em V2. e d(v) = q se v є V1 e d(v) = p se v є V2.
e
c
g
a
f
d
b
V1 V2
26DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• é um subgrafo de :
 
• Grafo induzido em por :
onde E(X) é o subconjunto de E formado por todas as 
arestas com as duas extremidades em X.
G(X)
G X = {2, 3, 4, 5}
1 2
3
4
5
6
G=(V,E )
G=(V,E )
V'⊆V,E'⊆E
X⊆V
G'=(V ', E' )
G(X )=( X,E(X ))
27DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Clique: subconjunto de nós que induz um subgrafo 
completo.
1
3
2
4
5
6
28DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Clique: subconjunto de nós que induz um subgrafo 
completo.
C1 = {1, 2, 3}
1
3
2
4
5
6
29DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Clique: subconjunto de nós que induz um subgrafo 
completo.
C1 = {1, 2, 3}5
C2 = {2, 4, 5}1
3
2
4
5
6
30DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Clique: subconjunto de nós que induz um subgrafo 
completo.
C1 = {1, 2, 3}
C2 = {2, 4, 5}
C3 = {4, 6}
1
3
2
4
5
6
31DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Clique: subconjunto de nós que induz um subgrafo 
completo.
C1 = {1, 2, 3}
C2 = {2, 4, 5}
C3 = {4, 6}
C4 = {3} 
1
3
2
4
5
6
32DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Clique: subconjunto de nós que induz um subgrafo 
completo.
C1 = {1, 2, 3}
C2 = {2, 4, 5}
C3 = {4, 6}
C4 = {3} 
1
3
2
4
5
6
33DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Exemplo:
G
1
3
2
4
1
3
2
4G'
• Grafos complementares: dois grafos G=(V,E) e 
G'=(V',E') são complementares se: 
( i,j )∈E⇒( i,j)∉E' ( i,j )∉E⇒( i,j )∈E'e
34DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Caminho de a :
Sequência P de vértices e arestas alternados, tais que cada 
aresta é incidente ao nó anterior e ao nó posterior.
 P é um ciclo ou circuito.
v i v j
v i=v j⇒
– Caminho simples: cada vértice aparece exatamente uma 
vez
– Comprimento de um caminho: número de arestas
– Caminhos disjuntos em vértices/arestas: não têm 
vértices/arestas em comum
35DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Vértices vi e vj são conectados se existe um caminho de vi a 
vj.
• Dois vértices vi e vj estão na mesmacomponente conexa se 
existe um caminho entre eles.
• Um grafo é conexo se possui uma única componente conexa, 
ou seja, se existe um caminho entre qualquer par de nós
É conexo?
Problema importante: determinar se um grafo é conexo 
ou não.
36DCC059 - Teoria dos Grafos
• Um grafo gerador de um grafo conexo G=(V,E) é um subgrafo 
conexo G’ com o mesmo conjunto de nós V.
Conceitos BásicosConceitos Básicos
Grafo G Grafo gerador de G
37DCC059 - Teoria dos Grafos
• Um grafo gerador de um grafo conexo G=(V,E) é um subgrafo 
conexo G’ com o mesmo conjunto de nós V.
Conceitos BásicosConceitos Básicos
Grafo G Grafo gerador de G
38DCC059 - Teoria dos Grafos
• Um grafo gerador de um grafo conexo G=(V,E) é um subgrafo 
conexo G’ com o mesmo conjunto de nós V.
Conceitos BásicosConceitos Básicos
Grafo G Grafo gerador de G
39DCC059 - Teoria dos Grafos
• Um grafo gerador de um grafo conexo G=(V,E) é um subgrafo 
conexo G’ com o mesmo conjunto de nós V.
Conceitos BásicosConceitos Básicos
Grafo G Grafo gerador de G
40DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• v é um ponto de articulação do grafo conexo G se sua 
remoção desconecta G.
41DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• v é um ponto de articulação do grafo conexo G se sua 
remoção desconecta G.
• Se uma componente conexa de um grafo não contém ponto 
de articulação, então ela é uma componente 2-conexa.
Importante:
42DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Uma aresta e, cuja remoção desconecta um grafo conexo é 
chamada de ponte.
43DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Uma aresta e cuja remoção desconecta um grafo conexo é 
chamada de ponte.
44DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Digrafo ou grafo orientado: grafo no qual são 
associadas direções aos seus arcos.
G=(V,A )
V= {v1 , . .. ,vn }
A= {a1 , .. . ,am }
a=( i,j )∈V×V par 
ordenado
Início ou origem Fim ou destino
1
2
3
4
5
6
d−( i)
d+ ( i)
= grau de entrada de i 
= número de predecessores de i
= grau de saída de i 
= número de sucessores de i
d−(1)=
d−( 4 )=
d+ (4 )=
d+ (6 )=
1
3
0
1
j é sucessor de i
i é predecessor de j
i j
45DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Uma cadeia a1, a2, ..., aq de arcos é uma sequência tal que 
cada arco ai tem uma extremidade comum com o arco ai-1 
e outra com o arco ai+1, 2 ≤ i ≤ q-1.
32
41
5
a1 a2
a3
a5
a6
a4
a7
a2, a5, a6, a4 → cadeia entre os nós 2 e 3
• Ciclo: cadeia cujas extremidades coincidem.
• Caminho a1, a2,..., aq: extremidade final do arco ai coincide 
com a extremidade inicial do arco ai+1.
• Circuito: caminho cujas extremidades coincidem.
46DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Dois vértices vi e vj estão na mesma componente fortemente 
conexa de um grafo orientado se existe um caminho de vi a vj 
e um caminho de vj a vi para todo par de vértices vi e vj.
{1, 2, 3, 4, 5, 6, 8, 9, 10}
{7}
{1, 2, 3, 4}
{5, 6, 7}
3
2
4
1
5
6 7
9
10
8
32
41
5
6
7
47DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Grafos planares:
Um grafo é planar se ele pode ser representado no plano de 
modo tal que não haja interseção entre suas arestas.
K3 ?
K5 ?
K4 ?
K3,3 ?
PLANAR
NÃO
PLANAR
NÃO
48DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Árvore: grafo conexo sem circuitos
• Floresta: grafo cujas componentes conexas são 
árvores
Um caminho é uma árvore?
49DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Teorema: Se T é uma árvore com n vértices, então:
• Existe um único caminho entre dois nós quaisquer de T.
• Sejam i, j dois nós de T tais que a aresta (i, j) não existe. 
Então, a inserção da aresta (i, j) em T provoca a formação de 
exatamente um ciclo.
• T possui n-1 arestas.
50DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Matriz de incidência nó-arco:
Uma linha para cada nó
Uma coluna para cada aresta
Formas de representação e matrizes associadas a um grafo
G=(V,A )
∣V ∣=n
∣A∣=m
a=( i,j )∈A
a
i
j
[ 0+10−1
0
]
1 2
34
a1
a2
a3
a4
a5
Am×n=[+1 +1 0 0 0−1 0 +1 +1 00 −1 −1 0 +10 0 0 −1 −1 ]
51DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Matriz de adjacência:
Uma linha para cada nó
Uma coluna para cada nó
a23
1 2
34
a12
a13
a24
a34
An×n=[0 1 1 00 0 1 10 0 0 10 0 0 0 ]
Grafos sem arcos paralelos:
1 2
34
1 2
34
n2 
posições
aij = 1 → (i , j ) ∈ A
aij = 0 → (i , j ) ∉ A
Formas de representação e matrizes associadas a um grafo
52DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
• Lista de nós:
Cada nó aponta para a lista de seus sucessores (ou 
nós adjacentes)
1 2
34
n nós m arestas ⇒ n +m posições
1
2
3
4
2 3
3 4
4
nós sucessores nós predecessores
1
2
3
4
1
1 2
2 3
Formas de representação e matrizes associadas a um grafo
53DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
1 3 5 7
m
n
1 2 3 4
1 3 1 3 2 1
1 2 3 4 5 6 7
Lista de arcos
1 2
34
S(.)
2 3 4 3 2 3
1 1 1 2 4 4
T(.)
É simples passar de uma forma de representação para outra.
Formas de representação e matrizes associadas a um grafo
54DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Desenhar o grafo representado pela matriz de 
adjacência abaixo:
A=[
0 1 0 0 0 1
0 0 1 0 0 1
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 1 0 0
1 0 1 0 1 0
]
Quais são as componentes fortemente conexas deste 
grafo?
Representar sua matriz de incidência.
{1,2,5,6}, {3,4}[
+1 +1 −1 0 0 0 0 0 0 0 0
−1 0 0 0 +1 0 +1 −1 0 0 0
0 0 0 −1 0 0 −1 0 0 +1 −1
0 0 0 0 0 0 0 0 −1 −1 +1
0 0 0 0 0 −1 0 +1 +1 0 0
0 −1 +1 +1 −1 +1 0 0 0 0 0
]
1
2
3
4
5
6
1 2 3 4 5 6 7 8 9 10 11 
55DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Representar o mesmo grafo por sua lista de 
adjacências.
Representar o grafo por sua lista de arcos.
1
2
3
4
5
6
2 6
3 6
4
2 4
1 3
3
5
 1 1 6 6 2 6 2 5 5 3 4
 2 6 1 3 6 5 3 2 4 4 3
 1 2 3 4 5 6 7 8 9 10 11
1 2
3
4
5
6
1
2
3
4
5
6
7
8
9
10
11
56DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Representar o mesmo grafo por sua lista de 
adjacências.
Representar o grafo por sua lista de arcos.
1
2
3
4
5
6
2 6
3 6
4
2 4
1 3
3
5
 1 1 6 6 2 6 2 5 5 3 4
 2 6 1 3 6 5 3 2 4 4 3
 1 2 3 4 5 6 7 8 9 10 11
57DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Algoritmo para converter uma representação de um grafo 
orientado sob forma de matriz de adjacência em matriz de 
incidência.
Ler número de nós n, matriz A
linha ← 1, coluna ← 1, arco ← 0
Enquanto linha ≤ n faça
 Enquanto coluna ≤ n faça
 Se A(linha,coluna)=1 então
 arco ← arco+1, k ← 1
 Enquanto k ≤ n faça
 B(k,arco) ← 0
 k ← k+1
 fim_enquanto
 B(linha,arco) ← +1
 B(coluna,arco) ← -1
 fim_se
 coluna ← coluna +1
 fim_enquanto
 coluna ← 1
 linha ← linha +1
fim_enquanto58DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
ISOMORFISMO
Sejam G1=(V1,E1) e G2=(V2,E2) dois grafos:
G1 é idêntico a G2 sse: V1=V2 e E1=E2.
Note que dois grafos idênticos PODEM ser representados 
graficamente de maneira idêntica (note que G1, G2 e G3 são 
idênticos).
59DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
ISOMORFISMO
Sejam G1=(V1,E1) e G2=(V2,E2) dois grafos:
G1 é idêntico a G2 sse: V1=V2 e E1=E2.
Note que G3 e G4 são representados de forma semelhante 
graficamente. Porém, eles não são grafos idênticos, já que o 
vértice c de G3 possui rótulo diferente em G4 (seu rótulo em 
G4 é z).
60DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
ISOMORFISMO
Sejam G1=(V1,E1) e G2=(V2,E2) dois grafos:
G3 e G4 são chamados grafos isomorfos
61DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
ISOMORFISMO
62DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
ISOMORFISMO
63DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Exercício:
1 - Escrever um algoritmo para converter a representação 
de um grafo orientado sob forma de matriz de 
incidência em uma representação por listas de 
adjacência.
2 – Seja um grafo G=(V,E) tal que |V|=20 e |E|=62 e 
d(vi)=3 ou d(vi)=7 para todo i Є V. O que se pode 
afirmar quanto ao número de vértice de grau 3?
3 – Mostre se existe ou não um grafo 3-regular com 7 
vértices.
4 – Prove que em um grafo, o número de vértices de grau 
ímpar é par. 
64DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Exercício:
5 – Prove que se um grafo G=(V,E) é um grafo k-regular, 
então |E|=(k * |V|)/2.
6 – Dados os grafos abaixo, definir se são ou não 
isomorfos:
a)
65DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Exercício:
6 – Dados os grafos abaixo, definir se são ou não 
isomorfos:
b)
66DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Exercício:
6 – Dados os grafos abaixo, definir se são ou não 
isomorfos:
c)
67DCC059 - Teoria dos Grafos
Conceitos BásicosConceitos Básicos
Exercício:
6 – Dados os grafos abaixo, definir se são ou não 
isomorfos:
d)
68DCC059 - Teoria dos Grafos
CAMINHAMENTOS EM GRAFOS
69DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Dados: 
G = (V,E)
V = {1, 2, ..., n} conjunto de nós
E = { (u1,v1), ..., (um,vm)} conjunto de arestas
Representação por listas de adjacências
5 3
1
2
4
1
2
3
4
5
4 3
3 4
1
3
1 2
5 2
70DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Caminhar/percorrer um grafo: 
visitar todos os nós e arestas
Enquanto for possível, aprofundar-se no grafo. 
Quando não for mais possível, recuar.
BUSCA EM PROFUNDIDADEBUSCA EM PROFUNDIDADE
8
9
1
5
4
2
6
3
7
101
4
6
7
8
3
2
10
5
9
1º1º
2º2º
3º3º
4º4º
5º5º
6º6º7º7º
8º8º
9º9º
10º10º
71DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
8
9
1
5
4
2
6
3
7
101
4
6
7
8
3
2
10
5
9
1º1º
2º2º
3º3º
4º4º
5º5º
6º6º7º7º
8º8º
9º9º
10º10º
1
4
6 5
7
8 3
2 10
9
72DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
A ordem em que os nós e arestas são visitados depende:
do nó inicial
da ordem em que os nós e as arestas aparecem na estrutura 
de dados
73DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Algoritmo recursivo para busca a partir de um nóAlgoritmo recursivo para busca a partir de um nó
Procedimento PROF(nó v)
 visitado(v) ← sim
 Para cada nó w adjacente a v faça
 Se visitado(w) = não então
 PROF(w)
 fim-para
Fim
74DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Exemplo:
D
A
E
B C
F G
H
A
B
C
D
E
F
G
H
B C
A
B H
F G
A D E
B H
C H
C H
D E F G
11
A
D E
B C
F G
H
22
33
44
55 66
77
88 X
X
X
X
X
X
X
X
não visitado
visitado
75DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Exemplo:
D
A
E
B C
F G
H
11
A
D E
B C
F G
H
22
33
44
55 66
77
88
A
B
E F
D
H
C
G
Árvore de busca Árvore de busca 
em profundidadeem profundidade
(pilha)(pilha)
Árvore de busca Árvore de busca 
em profundidadeem profundidade
(pilha)(pilha)
76DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Procedimento BUSCA-PROF
 Para i = 1,...,n faça
 visitado(i) ← não
 fim-para
 Para i = 1,...,n faça
 Se visitado(i) = não então
 PROF(i)
 fim-para
Fim
Algoritmo de busca em profundidadeAlgoritmo de busca em profundidade
77DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Exemplo:
11
8
2
3
1
7
5
6
4
11
9
14
12
10
13
8
1
322
4
33
5
44
6
55
7
66
2
77
9
88
99
14
1010
11
1111
10
1212
13
1313
12
1414
78DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Exemplo:
11
8
2
3
1
7
5
6
4
11
9
14
12
10
13
8
1
322
4
33
5
44
6
55
7
66
2
77
9
88
99
14
1010
11
1111
10
1212
13
1313
12
1414
79DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Aplicações de busca em profundidade, grafo 
G=(V,E):
G é acíclico?
G é conexo?
G é bipartido?
Quais são as componentes conexas de G?
Quais são as componentes biconexas de G?
Quais são os pontos de articulação de G?
80DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Procedimento COMPONENTES-CONEXAS
 Para i = 1,...,n faça
 visitado(i) ← 0
 fim-para
 componente ← 0
 Para i = 1,...,n faça
 Se visitado(i) = 0 então
 componente ← componente + 1
 PROF(i, componente)
 fim-se
 fim-para
Fim
Algoritmo para encontrar as componentes conexasAlgoritmo para encontrar as componentes conexas
81DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Procedimento PROF(v, marca)
 visitado(v) ← marca
 Para cada nó w adjacente a v faça
 Se visitado(w) = 0 então
 PROF(w, marca)
 fim-se
 fim-para
Fim
Algoritmo para encontrar as componentes conexasAlgoritmo para encontrar as componentes conexas
82DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
Exemplo: Problema do mosaicoProblema do mosaico
Quantos e quais mosaicos intermediários 
existem entre dois mosaicos específicos?
Novas configurações 
(mosaicos) são obtidas através 
do movimento de um elemento 
para a posição vazia.
4 5 3
8
2
7
1
6
■
1 2 3
4
57 6
8 ■
4 5 3
8
2
7
1
6
■
83DCC059 - Teoria dos Grafos
Caminhamento em GrafosCaminhamento em Grafos
4 ■ 6
2
7
5
1
3
8
4 5 6
2
7
■
1
3
8
4 5 6
■
7
2
1
3
8
1 2 3
4
5
■
6
8
7
4 5 6
2
7
3
1
■
8
4 5 6
2
7
1
■
3
8
4 5 6
2
7
1
8
3
■
4 5 6
2
■
1
7
3
8
?
84DCC059 - Teoria dos Grafos
2 8 3
6 ■ 4
1 7 5
Caminhamento em GrafosCaminhamento em Grafos
■ 8 3
2 6 4
1 7 5
2 8 3
■ 6 4
1 7 5
2 8 3
1 6 4
■ 7 5
2 8 3
1 ■ 4
7 6 5
2 8 3
1 6 4
7 ■ 5
2 8 3
■ 1 4
7 6 5
2 ■ 3
1 8 4
7 6 5
2 8 3
1 4 ■
7 6 5
2 8 3
1 6 4
7 5 ■
■ 8 3
21 4
7 6 5
2 8 3
7 1 4
■ 6 5
■ 2 3
1 8 4
7 6 5
2 3 ■
1 8 4
7 6 5
8 ■ 3
2 6 4
1 7 5
2 ■ 3
6 8 4
1 7 5
2 8 3
6 4 ■
1 7 5
2 8 3
6 7 4
1 ■ 5
8 ■ 3
2 1 4
7 6 5
2 8 3
7 1 4
6 ■ 5
1 2 3
■ 8 4
7 6 5
8 3 ■
2 6 4
1 7 5
8 6 3
2 ■ 4
1 7 5
■ 2 3
6 8 4
1 7 5
2 3 ■
6 8 4
1 7 5
2 8 ■ 
6 4 3
1 7 5
2 8 3
6 4 5
1 7 ■ 
2 8 3
6 7 4
■ 1 5
2 8 3
6 7 4
1 5 ■ 
8 3 ■
2 1 4
7 6 5
8 1 3
2 ■ 4
7 6 5
2 8 3
7 ■ 4
6 1 5
2 8 3
7 1 4
6 5 ■ 
1 2 3
8 ■ 4
7 6 5
1 2 3
7 8 4
■ 6 5
NÓ INICIALNÓ INICIALNÓ INICIALNÓ INICIAL
NÓ ALVONÓ ALVONÓ ALVONÓ ALVO
Busca em Busca em 
profundidadeprofundidade
1
2
3
4
5
6 7 10 11 13 14 16 17
8
9 12 15
18
19
20
21
22 23
24
25
26 27
28
29
30
31
85DCC059 - Teoria dos Grafos
CAMINHOS MAIS CURTOS
86DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Dados: grafo G=(V,A) orientado e distância cij associada 
ao arco (i,j) ∈ A.
Problema: Obter o caminho mais curto entre dois nós s e t.
O comprimento de um caminho é igual à soma dos 
comprimentos (distâncias) dos arcos que formam o 
caminho.
A “distância” ou “comprimento” de um arco pode ter diversas 
interpretações dependendo da aplicação: custos, distâncias, 
consumo de combustível, etc.
Exemplo 1: Dado um mapa rodoviário, determinar a rota mais curta 
de uma cidade a outra.
(rota mais rápida, rota com menor consumo de combustível, ...)
87DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Exemplo 2: Construção de uma estrada entre duas cidades 
A e K. O grafo abaixo representa os diversos trechos 
possíveis e o custo de construção de cada um. Determinar 
o trajeto ótimo cujo custo de construção seja mínimo 
(corresponde a achar o caminho mais curto de A a K em 
relação a estes custos).
A
B
C
D
F
E
G J
I
H
K
8
7
5
6 4
2 4
5
4
4
2
244
5
2 4 4
88DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Exemplo 2: Construção de uma estrada entre duas cidades 
A e K. O grafo abaixo representa os diversos trechos 
possíveis e o custo de construção de cada um. Determinar 
o trajeto ótimo cujo custo de construção seja mínimo 
(corresponde a achar o caminho mais curto de A a K em 
relação a estes custos).
A
B
C
D
F
E
G J
I
H
K
8
7
5
6 4
2 4
5
4
4
2
244
5
2 4 4
Solução: A – D – G – I – K
custo = 7 + 2 + 2 + 5 = 16
89DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Condição de existência: 
Caminho de i a j contendo um circuito w:
k
j
i
w
Compr.(i → j) = compr.(i → k) +compr.(w) +compr.(k → j)
Qual é o comprimento do caminho mais curto de i a j se 
o comprimento do circuito w é negativo?
90DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Condição de existência: não há circuitos de compr. negativo.
A solução ótima (caminho mais curto) sempre será um 
caminho elementar (sem circuito).
91DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Problemas de Caminho mais curto:
- De um nó a outro
- De um nó a todos os demais
- Entre todos os pares de nós de um grafo
92DCC059 - Teoria dos Grafos
Caminho mais curto do nó 1 a cada nó do grafo 
G=(V,A)
Hipótese: todas as distâncias cij são positivas:
 cij ≥ 0, ∀(i,j) ∈ A
Algoritmo de Moore-Dijkstra (1957-1959)
pi*(i) = comprimento do caminho mais curto do nó 1 ao nó i
Em especial, pi*(1)=0 (distâncias positivas).
Algoritmo com n-1 iterações
No início de cada iteração, o conjunto V de nós está particionado 
em dois subconjuntos S e S, com o nó 1 em S.
Caminhos mais CurtosCaminhos mais Curtos
93DCC059 - Teoria dos Grafos
Cada nó i ∈ V possui um rótulo pi(i ), que verifica a 
seguinte propriedade:
Caminhos mais CurtosCaminhos mais Curtos
Se i∈S⇒π ( i)=π∗( i)
Se i∈ S̄⇒π ( i)≥π∗( i)
 dá o valor do caminho mais curto de 1 a i sob 
a restrição de que todos os nós utilizados (exceto o 
próprio i ) pertençam a S.
π ( i) , i∈S̄ ,
a
1 b
c
i
π (a )
π (b )
π (c )
π ( i)cai
cbi
cci
S̄S
94DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Teorema: Seja o nó tal que .
Então , isto é, o comprimento do 
caminho mais curto do nó 1 ao nó j é igual a .
j∈ S̄ π ( i)
π∗( j )=π ( j)
Demonstração:
Por construção, certamente existe um caminho de 1 até j 
com comprimento pi(j).
Suponhamos que exista outro caminho de 1 a j de 
comprimento menor do que pi(j).
Dividamos este caminho em duas partes:
- P1 é a parte inicial, do nó 1 ao nó L, onde L é o primeiro nó 
de encontrado
- P2 é a parte final, do nó L ao nó j
π ( j )
S̄
95DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
comprimento de P1 ≥ pi(L) ≥ pi(j)
comprimento de P2 ≥ 0
 Logo, o comprimento de P1 + P2 ≥ pi(j).
96DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Algoritmo de Moore-Dijkstra
O algoritmo constrói progressivamente o conjunto dos nós mais 
próximos de 1.
→ Construção de uma arborescência com raiz em 1 que define os
 caminhos mais curtos do nó 1 a cada nó do grafo.
Inicializar S ← {2,3,...,n}, 
 S ← {1},
 pi(1)← 0,
 pi(j)← c1j se j∈Γ1+
 +∞ caso contrário
Enquanto S ≠ ∅ faça
 Selecionar j∈S tal que pi(j)= mini∈S{pi(i)}
 S ← S – {j}
 Para ∀i∈S e i∈Γj+ faça 
 pi(i) ← min{pi(i), pi(j)+cji}
fim_enquanto
97DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Exemplo
:
1
2
3
4
5
6
1
2
35
7
7
5
1 2
4
ITERAÇÃO 
1
pi*(1) = 0
pi*(3) = 1
1
2
3
4
5
6
1
2
35
7
7
5
1 2
4
S = {1}
S = {2,3,4,5,6}
pi(1) = 0
pi(2) = 7
pi(3) = 1
pi(4) = pi(5) = pi(6) = +∞
pi(2) = min{7, 
pi(5) = min{∞, 
pi(6) = min{∞, 
j = 3
S = {2,4,5,6}
1+5} = 6
1+2} = 3
1+7} = 8
98DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
ITERAÇÃO 
2
pi(2) = min{6, 
pi(4) = min{∞, 
j = 5
S = {2,4,6}
3+2} = 5
3+5} = 8
pi*(1) = 0
pi*(3) = 1
1
2
3
4
5
6
1
2
35
7
7
5
1 2
4
pi*(5) = 3
ITERAÇÃO 
3
pi(4) = min{8, 
pi(6) = min{∞, 
j = 2
S = {4,6}
5+4} = 8
5+1} = 6
pi*(1) = 0
pi*(3) = 1
1
2
3
4
5
6
1
2
35
7
7
5
1 2
4
pi*(5) = 3pi*(2) = 5
99DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
ITERAÇÃO 
4
pi(4) = 8 
j = 6
S = {4}
ITERAÇÃO 
5
j = 4
S = { }
pi*(1) = 0
pi*(3) = 1
1
2
3
4
5
6
1
2
35
7
7
5
1 2
4
pi*(5) = 3pi*(2) = 5
pi*(6) = 6
pi*(1) = 0
pi*(3) = 1
1
2
3
4
5
6
1
2
35
7
7
5
1 2
4
pi*(5) = 3pi*(2) = 5
pi*(6) = 6
pi*(4) = 8
100DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
1
2
3
5
4
2
3
25
4
3
1 2
6
7
3
1
4
3
1 2 3 4 5 6
1
2
3
4
5
6
7
nó
Iteração
Início 0
4
2
∞
∞
∞
∞
pi
0
4
2
5
4
7
7
0
4
2
5
4
∞
∞
0
4
2
5
4
7
7
0
4
2
5
4
7
7
0
4
2
5
4
7
7
0
4
2
5
4
7
7
101DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Número de operações (tempo): ~ n2 
n-1 iterações, cadaiteração busca o mínimo em uma 
lista com até n-1 elementos (vetor pi)
Caminho mais curto do nó 1:
→ ao nó j
→ a todos os nós
Mesma complexidade, mas critérios de parada 
diferentes.
Distâncias negativas:
1
3
2
10
- 8
3
Caminho mais curto de 1 a 3?
Resultado do algoritmo?
2
3
Por 
que?
102DCC059 - Teoria dos Grafos
Inicializar S ← {2,3,...,n}, 
 S ← {1},
 pi(1)← 0,
 pi(j)← c1j se j∈Γ1+
 +∞ caso contrário
Enquanto S ≠ ∅ faça
 Selecionar j∈S tal que pi(j)= mini∈S{pi(i)}
 S ← S – {j}
 Para ∀i∈Γj+ faça 
 Calcular pi* ← pi(j)+ cji
 Se pi* < pi(i) então
 S ← S ∪ {i}
 pi(i) ← pi*
 fim-se
 fim-para
fim-enquanto
Caminhos mais CurtosCaminhos mais Curtos
Extensão do algoritmo de Moore-Dijkstra para o caso 
com distâncias negativas (mas sem ciclos negativos)
103DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
1
2
3
5
4
2
3
-2-3
4
3
1 2
6
7
3
1
4
3
1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
nó
Iteração
Início
0
4
2
∞
∞
∞
∞
pi
S = 2 3 4 5 6 7
0
4
2
5
4
∞
∞
0
4
1
5
4
7
7
0
4
2
5
4
7
7
0
4
1
4
2
6
6
0
4
1
4
2
5
5
0
4
1
4
2
5
5
0
4
1
4
3
7
7
0
4
1
4
3
6
6
XX 3X
3
X
5
X 5X
5
X X
7
104DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Caminho mais curto:
- De um nó a outro
- De um nó a todos os demais
- Entre todos os pares de nós de um grafo
105DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Dados: 
Grafo G=(V, A) orientado, |V | = n.
Não há circuitos negativos.
c = {cij}, j = 1,...,n, i = 1,...,n
 cij ≥ 0
 cii = 0
 cij = +∞, (i, j ) ∉ A
Ak(i, j ) = valor do caminho mais curto de i a j podendo 
usar apenas nós numerados de 1 a k como nós 
intermediários.
Caminho mais curto entre todos os pares de nós de um grafo
106DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Se Ak+1(i, j ) não usa o nó k+1 como intermediário, 
então: Ak+1(i, j ) = Ak(i, j ) 
Ak+1(i, j ) = min { Ak(i, j ), Ak(i, k+1) + Ak(k+1, j ) }Ak+1(i, j ) = min { Ak(i, j ), Ak(i, k+1) + Ak(k+1, j ) }
Se Ak+1(i, j ) usa o nó k+1 como intermediário, então: 
Ak+1(i, j ) = Ak(i, k+1) + Ak(k+1, j )
107DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
A0(i, j ) = cij : caminho mais curto de i a j usando no 
máximo o nó “0” (que não existe) como nó 
intermediário (caminho mais curto de i a j 
sem nós intermediários)
Ak(i, j ) : pode usar o nó k ou não.
Ak+1(i, j ) : pode usar o nó k+1 ou não.
A0 → A1
A1 → A2
 ...
An-1 → An
An(i, j ) = valor do caminho mais curto de 
i a j podendo usar qualquer nó 
de 1 a n como nó intermediário.
108DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Algoritmo de Floyd:
Para i = 1,...,n faça
 Para j = 1,...,n faça
A0(i,j) ← cij
 fim-para
fim-para
Para k = 1,...,n faça
 Para i = 1,...,n faça
 Para j = 1,...,n faça
 Ak(i,j) ← min{Ak-1(i,j),
 Ak-1(i,k) + Ak-1(k,j)}
 fim-para
 fim-para
fim-para
109DCC059 - Teoria dos Grafos
073
206
1140
A1 = 
Caminhos mais CurtosCaminhos mais Curtos
Exemplo
:
1 2
3
3
6
4
1
1
2 0+∞3
206
1140
C = 
0+∞3
206
1140
A0 = 
073
206
640
A2 = 
073
205
640
A3 = 
110DCC059 - Teoria dos Grafos
Caminhos mais CurtosCaminhos mais Curtos
Algoritmo de Dijkstra: número de operações (tempo) ~ n2 
n-1 iterações, cada iteração busca o mínimo em uma lista 
com até n-1 elementos (vetor pi)
Algoritmo de Floyd: número de operações (tempo) ~ n3 
Três comandos for de 1 até n um dentro do outro
Ou seja, o problema de calcular os caminhos mais curtos 
entre todos os pares de nós pode ser resolvido com a 
mesma eficiência aplicando-se n vezes o algoritmo de 
Dijkstra, uma vez a partir de cada nó inicial.
111Teoria de Grafos
CAMINHOS MAIS LONGOS E 
SEQUENCIAMENTO DE 
TAREFAS 
112Teoria de 
Grafos
Caminhos mais Longos
Adaptação dos algoritmos para o problema de 
caminho mais curto
f* = mínimo f(x) = - máximo {- 
f(x)} 
• Condição: o grafo não pode ter circuitos de 
comprimento positivo.
f*
x*
f
- f*
- f
Multiplicar as distâncias por (-1) e 
aplicar
o algoritmo para caminhos mais 
curtos
Multiplicar as distâncias por (-1) e 
aplicar
o algoritmo para caminhos mais 
curtos
113Teoria de 
Grafos
Caminhos mais Longos
• Alternativa: adaptar os algoritmos de caminhos mais 
curtos para que calculem caminhos mais longos.
Inicializar S ← {2,3,...,n}, 
 S ← {1},
 pi(1)← 0,
 pi(j)← c1j se j∈Γ1+
 -∞ caso contrário
Enquanto S ≠ ∅ faça
 Selecionar j∈S tal que pi(j)= maxi∈S{pi(i)}
 e todos os predecessores de j já pertençam a S
 S ← S – {j}
 S ← S ∪ {j}
 Para ∀i∈S e i∈Γj+ faça 
 pi(i) ← max{pi(i,pi(j)+cji}
fim-enquanto
114Teoria de 
Grafos
Caminhos mais Longos
Problema central de seqüenciamento de tarefas
Os grandes projetos exigem acompanhamento 
constante e perfeita coordenação das tarefas, de modo 
a:
evitar atrasos
evitar custos adicionais
Problema de seqüenciamento:
– Objetivo: determinar a ordem e o calendário de execução 
das tarefas.
– Tarefa 
– Representação por um grafo
duração
restrições 
(precedências)
115Teoria de 
Grafos
Caminhos mais Longos
Exemplo: 
Preparação da construção de um prédio:
1. Executar o aterro (10 dias)
2. Instalar um guindaste (2 dias)
3. Fazer as fundações (6 dias)
4. Ligações elétricas (3 dias)
5. Instalação de esgotos (5 dias)
Restrições:
• O guindaste só pode funcionar após as ligações 
elétricas estarem prontas.
• O guindaste é necessário para fazer as fundações.
• A instalação dos esgotos e as fundações só podem ser 
executadas após o final do trabalho de aterro.
116Teoria de 
Grafos
Caminhos mais Longos
• PERT (Program Evaluation and Review Technique)
Rede PERT:
– nós: representam etapas (instantes privilegiados do 
projeto)
- etapa INÍCIO
 - etapa FIM
– arcos: representam tarefas 
- tarefas reais de duração positiva
- tarefas virtuais (ou fictícias) de duração nula para 
exprimir as restrições de precedência.
– Grafo potenciais-etapas (nós são etapas)
117Teoria de 
Grafos
Caminhos mais Longos
• Uma etapa x é atingida quando todas as tarefas (reais 
e fictícias) correspondendo a arcos dos quais x é 
extremidade final foram concluídas.
• Só é possível iniciar a execução da tarefa 
correspondente ao arco (x, y) depois que a etapa x 
tiver sido atingida.
x
t1
t2 t3
y
118Teoria de 
Grafos
Caminhos mais Longos
Exemplo: A tarefa 1 deve estar terminada para que a 
tarefa 5 possa ser iniciada.
Supressão de arcos inúteis:
3
5
2
1
4
I F
3
2
10
6
5
2
1
4
3
5
I F
3
2
10
6
5
a
b
I
b
a
F
119Teoria de 
Grafos
Caminhos mais Longos
Resolver um problema de seqüenciamento de 
tarefas corresponde a:
determinar um calendário de execução
determinar as tarefas críticas (aquelas cujo atraso 
provoca um atraso na execução do projeto como um 
todo)
controlar o desenvolvimento do projeto e saber, a 
cada instante, atualizar as previsões iniciais
120Teoria de 
Grafos
Caminhos mais Longos
Etapa x:
α(x): data mais cedo (data mínima em que a etapa x 
pode ser atingida)
β(x): data mais tarde (data máxima em que a etapa x 
pode ser atingidasem que resulte em atraso na 
execução do projeto como um todo)
• Uma tarefa é dita crítica se qualquer atraso em sua 
execução se repercute automaticamente na 
duração do projeto.
Caminho crítico: 
formado por 
tarefas 
críticas
121Teoria de 
Grafos
Caminhos mais Longos
• Para que a etapa x possa ser atingida, é necessário 
que todos os caminhos de I a x tenham sido 
percorridos.
α(x) = comprimento do caminho mais 
longo de I a x considerando-se α(I) 
= 0.
Tarefa u = (x,y):
δ(u) = β(y) - α(x) - d(u) é a folga da tarefa u.
• u ∈ caminho crítico δ(u) 
= 0 I(u)
x
T(u)
y
u
O grafo PERT não tem 
circuitos.
122Teoria de 
Grafos
Caminhos mais Longos
Algoritmo 
PERT
S ← {I}, α(I) ← 0
Enquanto ∃ x ∉ S tal que todos seus 
predecessores estão em S faça
 α(x) ← max{u: T(u)= x}{α(I(u))+d(u)}
 S ← S ∪ {x}
fim-enquanto
S ← {F}, β(F) ← α(F)
Enquanto ∃ x ∉ S tal que todos seus 
sucessores estão em S faça
 β(x) ← min{u: I(u)= x}{β(T(u))-d(u)}
 S ← S ∪ {x}
fim-enquanto
Calcular δ(u) ← β(T(u))-α(I(u))–d(u), ∀u ∈ U
123Teoria de 
Grafos
Caminhos mais Longos
Exemplo:
α(I) = 0 S={I}
α(b) = 10 S={I, b}
α(a) = 10 S={I, a, b}
α(F) = 16 S={I, a, b, 
F}
I F
3
2
10
6
5
0
a
b
β(F) = 16 S={F}
β(a) = 10 S={F, a}
β(b) = 10 S={F, b, a}
β(I) = 0 S={F, b, a, I}
ITERAÇÃO 1:
ITERAÇÃO 2:
ITERAÇÃO 3:
ITERAÇÃO 1:
ITERAÇÃO 2:
ITERAÇÃO 3:
124Teoria de 
Grafos
Caminhos mais Longos
Grafo potenciais-tarefas:
nó → tarefa
arco(i,j) → se a tarefa i deve preceder a tarefa j
3
5
2
1
4
I F
3
2
10
6
5
I
3
2
10
6
5100
0
0
4
2
1
3
5
F
125Teoria de 
Grafos
Caminhos mais Longos
A tarefa j só pode começar 
após a 
metade da execução da tarefa 
i:
A tarefa j só pode começar 
um 
tempo t após o fim de i:
A tarefa j só pode começar 
após 
a data bj:
i j
di/2
i j
di + t
I j
bj
126Teoria de 
Grafos
Caminhos mais Longos
B1C
D, C2E
A8D
D, C1F
D, C1G
F3H
H2J
E, G ,J1K
A3B
-7A
ANTERIORE
SDURAÇÃOTAREFAS
GRAFO POTENCIAIS-ETAPAS:
I 1
2
3
5 6
4 FA
B C
D E
F
H
J
K
G
7
3 1
8
1
3
2
2
1
1
α(I)=0
β(I)=0
α(1)=
7
α(3)=15
α(2)=10
α(4)=21
α(F)=22
α(6)=19α(5)=16
β(F)=22
β(4)=21
β(6)=19β(5)=16
β(3)=15β(1)=7
β(2)=14
127Teoria de 
Grafos
Caminhos mais Longos
Cálculo das folgas: 
 δ(u) = β(T(u)) – α(I(u)) – d(u)
δ(A) = 7 – 0 – 7 = 0
δ(B) = 14 – 7 – 3 = 4
δ(C) = 15 – 10 – 1 = 4
δ(D) = 15 – 7 – 8 = 0
δ(E) = 21 – 15 – 2 = 4
δ(F) = 16 – 15 – 1 = 0
δ(G) = 21 – 15 – 1 = 5
δ(H) = 19 – 16 – 3 = 0
δ(J) = 21 – 19 – 2 = 0
δ(K) = 22 – 21 – 1 = 0
Caminho crítico: 
A → D → F → H → J → K
128DCC059 - Teoria dos Grafos
 Árvore Geradora de Peso Mínimo
129DCC059 - Teoria dos Grafos
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
Dados: G = (V,E) grafo não-orientado, com |V|=n e |E|=m
peso c(e), ∀e ∈ E
Problema 
Obter F ⊆ E tal que:
o grafo G’=(V,F) é acíclico e conexo (G’ é gerador de G) 
c(F) = Σe∈E c(e) é mínimo
130DCC059 - Teoria dos Grafos
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
Exemplo:
9D
A
E
B
C
F3
4
8
4
7
2
2
5
9
árvore geradoraárvore geradora
peso = 15peso = 15
D
A B
C
E F
árvore geradoraárvore geradora
peso = 24peso = 24
D
A
E
B
C
F
3
4
8
4 5
D
A B
C
E F
D
A
E
B
C
F
4
3
4
2
2
D
A
E
B
C
F
131DCC059 - Teoria dos Grafos
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
Princípio: a aresta de menor peso sempre pertence à 
árvore geradora de peso mínimo.
Algoritmo de KruskalAlgoritmo de Kruskal
Prova: 
Suponha que a aresta de peso mínimo não pertença à 
solução ótima.
Inserindo-se a aresta de peso mínimo nesta solução 
ótima, obtém-se um ciclo.
Pode-se obter uma nova árvore geradora 
removendo-se a aresta de maior peso.
Esta nova árvore geradora teria peso menor do que a 
anterior, portanto aquela solução não poderia ser 
ótima.
132DCC059 - Teoria dos Grafos
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
Criar uma lista L com as arestas ordenadas em 
ordem crescente de pesos.
Criar |V| subárvores contendo cada uma um nó 
isolado.
F ← ∅
contador ← 0
Enquanto contador < |V|-1 e L ≠ ∅ faça
 Seja (u,v) o próximo arco de L.
 L ← L – {(u,v)}
 Se u e v não estão na mesma subárvore então
 F ← F ∪ {(u,v)}
 Unir as subárvores que contêm u e v.
 contador ← contador + 1
 fim-se
fim-enquanto
Algoritmo de KruskalAlgoritmo de Kruskal
133DCC059 - Teoria dos Grafos
Exemplo:
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
83
9D
A
E
B
C
F
4
4
7
2
2
5
9
3
134DCC059 - Teoria dos Grafos
Exemplo:
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
H
A
B
J
C
E
M L
G
D
I
F
4
7
4
3
7
5
6
2
2
3
1
4
2
3
8
6
4
135DCC059 - Teoria dos Grafos
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
Começar com uma árvore formada apenas por um nó 
qualquer do grafo, ou pela aresta de peso mínimo.
Algoritmo de PrimAlgoritmo de Prim
A cada iteração, adicionar a aresta de menor peso 
que conecta um nó já conectado a um nó 
não-conectado.
136DCC059 - Teoria dos Grafos
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
Seja (u,v) a aresta de menor peso.
F ← {(u,v)}
Para i = 1,...,n faça
 Se c(i,u) < c(i,v) então prox(i) ← u
 Senão prox(i) ← v
fim-para
prox(u), prox(v) ← 0, contador ← 0
Enquanto contador < n-2 faça
 Seja j tal que prox(j)≠0 e c(j,prox(j)) é mínimo.
 F ← F ∪ {(j,prox(j))}
 prox(j) ← 0
 Para i = 1,...,n faça
 Se prox(i) ≠ 0 e c(i,prox(i)) > c(i,j) então
 prox(i) ← j
 fim-para
 contador ← contador + 1
fim-enquanto
Algoritmo de PrimAlgoritmo de Prim
137DCC059 - Teoria dos Grafos
Árvore Geradora de Peso Árvore Geradora de Peso 
MínimoMínimo
Exemplo:
9D
A
E
B
C
F3
4
8
4
7
2
2
5
9
3
138DCC059 - Teoria dos Grafos
ÁrvoresÁrvores
Distancia ( denotado por distancia(u,v) ) entre dois vértices: 
número de arestas no menor caminho entre os vértices u e v.
Excentricidade (denotado por excentricidade(v))de um vértice v:
max( distancia(v,u) ) ∀ u ∈ V(G).
Raio (denotado por raio(G) ) de um grafo é a excentricidade 
mínima de um vértice do grafo.
Diâmetro (denotado por diametro(G)) de um grafo é a 
excentricidade máxima de um vértice do grafo.
139DCC059 - Teoria dos Grafos
ÁrvoresÁrvores
Vértice central: v é vértice central ↔ excentricidade(v) =raio(G)
ou seja, se v é um vértice com excentricidade mínima no grafo
Centro de um grafo G: é o conjunto de todos pontos centrais de G.
140DCC059 - Teoria dos Grafos
Árvores com RaizÁrvores com Raiz
Uma árvore com raiz é uma árvore que contém um vértice 
especial marcado como raiz.
Exemplo:
Aplicações:
141DCC059 - Teoria dos Grafos
Árvores com RaizÁrvores com Raiz
Para todo vértice v, de uma árvore com raiz r, existe um único 
caminho Pv de r a v.
Exemplo:
• Se w é um vértice em Pv, w é um ancestral ou predecessor de v e 
v é um descendente de w (imagine uma árvore genealógica).
• Se w é um vértice em Pv adjacente a v, w é um ancestral 
imediato, predecessor imediato ou pai de v e v é um decendente 
imediato ou filho de w.
142DCC059 - Teoria dos Grafos
Árvores com RaizÁrvores com Raiz
 Um vértice sem filho é dito folha da árvore;
 Todo vértice de uma árvore, comexceção da raiz, possui 
exatamente um pai.
 Um vértice que não é uma folha é dito um vértice interno da 
árvore.
143DCC059 - Teoria dos Grafos
Árvores com RaizÁrvores com Raiz
Para todo vértice v, de uma árvore com raiz r, existe um único 
caminho Pv de r a v.
• Se Pv possui k arestas, então v está no nível k da árvore.
• O maior nível de uma árvore é denominado altura da árvore.
• Uma subárvore T' de uma árvore T é formada por um vértice 
(que será a raiz de T') e todos os seus descendentes.
144DCC059 - Teoria dos Grafos
Árvores com RaizÁrvores com Raiz
 Uma árvore m-ária é uma árvore cujos vértices possuem, no 
máximo, m filhos.
 Cada vértice de uma árvore possui exatamente um pai (exceto a 
raiz, que não possui pai).
 Árvores 2-árias, em particular, são chamadas de árvores binárias.
145DCC059 - Teoria dos Grafos
Árvores com RaizÁrvores com Raiz
 Uma árvore m-ária cheia é uma árvore cujos vértices internos 
possuem exatamente m filhos.
Exemplo:
 Uma árvore m-ária completa é uma árvore m-ária cheia onde 
todas as folhas estão no mesmo nível.
Exemplo
146DCC059 - Teoria dos Grafos
Árvores com RaizÁrvores com Raiz
 Se G é uma árvore de altura h, todas as subárvores formadas 
pelos filhos da raiz possuem altura no máximo h-1 e pelo menos 
uma destas subárvores possui altura h-1.
Prove (dica: por contradição)
147DCC059 - Teoria dos Grafos
Árvores com RaizÁrvores com Raiz
 Uma árvore m-ária cheia com k vértices internos possui mk+1 
vértices.
Prova: cada um dos k vértices internos possui m filhos, totalizando 
mk vértices com pai. Como a raiz é o único vértice da árvore sem 
pai, o total de vértices é: mk+1.
148DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Aplicações:
Projeto de circuitos eletrônicos e VLSI.
Redes de comunicação.
Redes de tráfego.
Tubulações de gás e óleo.
Distribuição de água para irrigação e redes de drenagem.
Projetos de instalações elétricas e mecânicas.
Projetos de edificações
...
1 - Problema da Árvore de Steiner
149DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Definição:
Seja o grafo G = (V,A), e ∆ e Χ conjuntos resultantes de uma 
partição do conjunto V, ou seja, ∆ ⊆ V e Χ ⊆ V, sendo que ∆ ∪ Χ= V 
e ∆ ∩ Χ = ∅, |Χ| = r e |∆| = s. Determinar um subconjunto de 
arestas B ⊆ A que ligue todos os vértices xi ∈ Χ em um grafo 
conexo, onde i = 1, 2, ...,r, de modo a minimizar ∑cj | j ∈ B, onde
cj é o custo ou o comprimento das arestas de B.
1 - Problema da Árvore de Steiner
150DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Definição:
Seja o grafo G = (V,A), e ∆ e Χ conjuntos resultantes de uma 
partição do conjunto V, ou seja, ∆ ⊆ V e Χ ⊆ V, sendo que ∆ ∪ Χ= V 
e ∆ ∩ Χ = ∅, |Χ| = r e |∆| = s. Determinar um subconjunto de 
arestas B ⊆ A que ligue todos os vértices xi ∈ Χ em um grafo 
conexo, onde i = 1, 2, ...,r, de modo a minimizar ∑cj | j ∈ B, onde
cj é o custo ou o comprimento das arestas de B.
Os vértices pertencentes ao conjunto ∆ (pontos de Steiner) podem 
ser usados ou não pela estrutura de ligação.
1 - Problema da Árvore de Steiner
151DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Exemplo:
1 - Problema da Árvore de Steiner
1
2
8
7
3
5
3
10
9
1
1
2
8
3
5
3
10
9
1
7
1
152DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Exemplo:
1 - Problema da Árvore de Steiner
Vértices Terminais
1
2
8
7
3
5
3
10
9
1
1
2
8
3
5
3
10
9
1
7
1
153DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Exemplo:
1 - Problema da Árvore de Steiner
Vértices Terminais
1
2
8
7
3
5
3
10
9
1
7
1
154DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Exemplo:
1 - Problema da Árvore de Steiner
1
2
8
7
3
5
3
10
9
1
Vértices Terminais
155DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Exemplo:
1 - Problema da Árvore de Steiner
1
23
1
156DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Casos:
1- |Χ| = 2 
O problema torna-se um PCMC e pode ser facilmente resolvido (e.g. 
usando o algorit-mo de Dijkstra visto anteriormente).
2- Χ = N ou ∆ =∅:
Resume-se em achar uma AGM do grafo, que também pode ser 
facilmente resolvido (e.g. usando os algoritmos de Kruskal ou Prim 
vistos anteriormente)
3- |Χ| > 2 e ∆ ≠∅.
1 - Problema da Árvore de Steiner
157DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Exercício em sala (mesmo grupo dos trabalhos)
Apresente um algoritmo em pseudocódigo (detalhado) para o PAS.
1 - Problema da Árvore de Steiner
158DCC059 - Teoria dos Grafos
Problemas em grafosProblemas em grafos
Considera-se o grafo direcionado e assume-se a formulação do 
Problema de Steiner.
Exercício:
Apresente um algoritmo em pseudocódigo (detalhado) para o PAS.
2 - Problema da Arborescência de Steiner
159Teoria de Grafos
PROBLEMAS EM GRAFOS
3 – Problemas de Emparelhamento em Grafos
160Teoria de Grafos
Emparelhamento em Grafos
• Problema: Formar duplas de pessoas que 
se conhecem.
• Pessoas -> nós.
• Se conhecer -> arestas.
• Problema: Encontrar um emparelhamento 
dos nós do grafo.
3 – Problemas de Emparelhamento em Grafos
161Teoria de Grafos
Emparelhamento em Grafos
H
A
B
J
C
E
M L
G
D
I
F
162Teoria de Grafos
Emparelhamento em Grafos
• Um emparelhamento (matching) de um 
grafo G=(V, E) é um subconjunto M ⊆ E tal 
que nenhum par de arestas de M incidem 
no mesmo nó.
• Os dois extremos de uma aresta em M são 
emparelhados pelo eparelhamento M. 
3 – Problemas de Emparelhamento em Grafos
163Teoria de Grafos
Emparelhamento em Grafos
• Os nós de G incidentes a alguma aresta de 
M estão cobertos por M.
• Se todo nó de G está coberto por M, 
disse-se que M é perfeito.
• Problema: Emparelhamento máximo.
• Todo emparelhamento perfeito é máximo.
3 – Problemas de Emparelhamento em Grafos
164Teoria de Grafos
Emparelhamento em Grafos
1
2
5
3
6
4 8
7
1
2
5
3
6
4
7
EmparelhamenEmparelhamen
to máximoto máximo
EmparelhamenEmparelhamen
to perfeitoto perfeito
3 – Problemas de Emparelhamento em Grafos
165Teoria de Grafos
Emparelhamento em Grafos
• Se M é um emparelhamento, um caminho 
simples (não repete nó) alternado em M é 
um caminho cujas arestas pertencem e 
não pertencem alternadamente a M.
3 – Problemas de Emparelhamento em Grafos
166Teoria de Grafos
Emparelhamento em Grafos
1
2
5
3
6
4 8
7
1
2
5
3
6
4
7
Caminho Caminho 
alternado: (1, 2, 5, alternado: (1, 2, 5, 
3, 4)3, 4)
Caminho Caminho 
alternado: (8, 4, 7, alternado: (8, 4, 7, 
3, 5)3, 5)
3 – Problemas de Emparelhamento em Grafos
167Teoria de Grafos
Emparelhamento em Grafos
• Caminho de aumento em M: Caminho 
alternado em M tal que o nó inicial e o no 
final não estão cobertos por M.
3 – Problemas de Emparelhamento em Grafos
168Teoria de Grafos
Emparelhamento em Grafos
1
2
5
3
6
4 8
7
1
2
5
3
6
4
7
Caminhos de Caminhos de 
aumento: (7, 3, 5, aumento: (7, 3, 5, 
4)4)
(4, 7)(4, 7)
(6, 2, 1, 5, 3, 7)(6, 2, 1, 5, 3, 7)
Caminho de Caminho de 
aumento: (5, 4, 3, 7)aumento: (5, 4, 3, 7)
3 – Problemas de Emparelhamento em Grafos
169Teoria de Grafos
Emparelhamento em Grafos
• Teorema: Um emparelhamento M é 
máximo em G se e somente se G não 
contém nenhum caminho de aumento em 
M.
3 – Problemas de Emparelhamentoem Grafos
170Teoria de Grafos
Emparelhamento em Grafos
• Teorema: Uma árvore tem no máximo um 
emparelhamento perfeito.
Prova: Sejam M e M' dois emparelhamentos 
perfeitos diferentes de uma árvore. Consideremos o 
grafo induzido por M ∇ M'. Todo nó desse grafo tem 
grau 2, uma aresta incidente por M e outra por M' 
(tanto M como M' são perfeitos) e portanto tem um 
cíclo.
Como as arestas deste grafo pertencem à árvore, a 
árvore também tem um ciclo, o que é absurdo.
3 – Problemas de Emparelhamento em Grafos
171Teoria de Grafos
Emparelhamento em Grafos
• Problema de atribuição (assignment) : Em 
uma empresa n trabalhadores estão 
disponíveis para fazer n tarefas, cada 
trabalhador sabe fazer um subconjunto 
dessas tarefas.
• Existe uma maneira de atribuir a cada um 
dos trabalhadores exatamente uma tarefa 
que ele saiba fazer? 
3 – Problemas de Emparelhamento em Grafos
172Teoria de Grafos
Emparelhamento em Grafos
• Trabalhadores -> nós.
• Tarefas -> nós.
• Sabe fazer -> aresta.
• Grafo bipartido.
3 – Problemas de Emparelhamento em Grafos
173Teoria de Grafos
Emparelhamento em Grafos
• Seja S um conjunto de nós de um grafo.
• Define-se a vizinhança de S (N(S)) em G 
ao subconjunto de nós adjacente a algum 
nó de S. 
3 – Problemas de Emparelhamento em Grafos
174Teoria de Grafos
Emparelhamento em Grafos
• Seja G um grafo bipartido com bipartição 
(X, Y). G contém um emparelhamento no 
qual todo vértice de X está coberto se e 
somente se |N(S)| ≥ |S| para todo S ⊆ X.
• Prova:
• => Contém matching então |N(S)|≥|S|
– Fácil
• <= |N(S)|≥|S| então contém matching.
– + difícil 
3 – Problemas de Emparelhamento em Grafos
175Teoria de Grafos
Emparelhamento em Grafos
• Corolário: Todo grafo bipartido k-regular 
com k > 0 tem um emparelhamento 
perfeito.
3 – Problemas de Emparelhamento em Grafos
176Teoria de Grafos
Emparelhamento em Grafos
• Se K é uma cobertura por nós e M um 
emparelhamento do grafo G, então |M| ≤ 
|K|.
– Por cada aresta de M preciso um nó de 
K.
• Em particular, o tamanho da cobertura 
mínima é maior ou igual que o tamanho 
do emparelhamento máximo.
3 – Problemas de Emparelhamento em Grafos
177Teoria de Grafos
Emparelhamento em Grafos
• Teorema: Se |M| = |K| então M é 
emparelhamento máximo e K é cobertura 
mínima.
• Em geral, a igualdade não se verifica.
• Teorema: Em grafos bipartidos, |M*| = 
|K*|
3 – Problemas de Emparelhamento em Grafos
178Teoria de Grafos
Emparelhamento em Grafos
• Problema de atribuição (assignment) : Em uma 
empresa n trabalhadores estão disponíveis para 
fazer n tarefas, cada trabalhador sabe fazer um 
subconjunto dessas tarefas.
• Existe uma maneira de atribuir a cada um dos 
trabalhadores exatamente uma tarefa que ele 
saiba fazer? 
3 – Problemas de Emparelhamento em Grafos
179Teoria de Grafos
Emparelhamento em Grafos
• Trabalhadores -> nós.
• Tarefas > nós.
• Sabe fazer -> aresta.
• Grafo bipartido.
• Existe um emparelhamento perfeito em 
G?
3 – Problemas de Emparelhamento em Grafos
180Teoria de Grafos
Emparelhamento em Grafos
• Método Húngaro:
– Encontra um emparelhamento em um 
grafo bipartito com bipartição (X, Y) tal 
que X está coberto pelo 
emparelhamento ou encontra um 
subconjunto S ⊆ X tal que |N(S)| < |S|. 
3 – Problemas de Emparelhamento em Grafos
181Teoria de Grafos
Método Húngaro
• Seja M um emparelhamento qualquer. (por exemplo M = ∅).
• Se M cobre X então parar. Senão seja u um nó de X não 
coberto por M.
• Fazer S={u}, T={∅}.
• Se N(S) = T então parar pois |N(S)|<|S|. Em caso contrário, 
seja y um nó de N(S)\T.
• Se y está coberto por M seja (y, z) a aresta de M que cobre y. 
Fazer S = S ∪ {z} e T = T ∪ {y} e volte ao passo 4.
• Se y não está coberto por M determinamos um caminiho de 
aumento de u a y. Aumentar M e voltar ao passo 2. 
3 – Problemas de Emparelhamento em Grafos
182Teoria de Grafos
Problemas em Grafos
Subonjunto de nós K ⊆ V tal que toda aresta de E 
tem um extremo em um nó de K.
O problema de cobertura de vértices é minimal.
Uma variação do problema é quando tem-se um 
grafo com pesos nos nós. O problema então 
consiste em encontrar uma cobertura K em que o 
somatório dos pesos dos vértices de K seja 
mínimo.
4 – Problemas de Cobertura de Vértices
183Teoria de Grafos
1
Emparelhamento em Grafos
1
2
5
3
6
4 8
7
2
5
3
6
4
73
2
41
3
2
41 8
4 – Problemas de Cobertura de Vértices
184Teoria de Grafos
PROBLEMAS EM GRAFOS
5 – Circuito Euleriano
185Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
186Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
187Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
188Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
189Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
190Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
191Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
192Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
193Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
194Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
195Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
196Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
197Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
198Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
199Teoria de Grafos
Circuito euleriano
• É possível atravesar todas as pontes 
de uma cidade composta por ilhas 
sem repetir nenhuma ponte? 
5 – Circuito Euleriano
200Teoria de Grafos
Circuito euleriano
• Pode-se desenhar os seguintes 
grafos sem levantar o lapiz do papel?
Sim Não
5 – Circuito Euleriano
201Teoria de Grafos
Circuito euleriano
• Caminho euleriano: Caminho que passa 
por todas as arestas de um grafo 
exatamente uma vez.
• Circuito euleriano: Circuito que passa por 
todas as arestas de um grafo exatamente 
uma vez.
• Um grafo é euleriano se contém um 
circuito euleriano.
5 – Circuito Euleriano
202Teoria de Grafos
Circuitoeuleriano
• Teorema: Um grafo conexo é euleriano se 
e somente se não tem nós de grau ímpar.
• Prova:
• =>) Seja C o ciclo euleriano com inicio e 
fim no nó u.
• Por cada vez que um nó v diferente de u 
aparece no ciclo duas arestas incidentes a 
v são usadas.
5 – Circuito Euleriano
203Teoria de Grafos
Circuito euleriano
• Como todas as arestas do grafo são 
percorridas por C o grau de todo nó 
diferente de u é par.
• Considerando que o ciclo inícia e acaba 
em outro nó mostra-se que u também tem 
grau impar.
5 – Circuito Euleriano
204Teoria de Grafos
Circuito euleriano
• <=) Suponhamos que G é o grafo conexo 
não euleriano com graus sempre pares com 
o menor número de arestas possível.
• Dado que o grau de cada nó é maior ou 
igual a 2, G tem um ciclo.
• Seja C o ciclo de G com maior número de 
arestas.
• Com C não é euleriano, G-E(C) tem alguma 
componente conexa G' com mais do que 1 
aresta.
5 – Circuito Euleriano
205Teoria de Grafos
Circuito euleriano
• Como C é euleriano, todos os nós de C tem grau 
par em C.
• Então todos os nós de G' são pares.
• Então G' é euleriano por ter menos arestas que 
G. Seja C' um ciclo euleriano de G'.
• Como o grafo é conexo, existe um no v que 
pertence à interseção de C com C'.
• Escolhendo v como início e fim de ambos ciclos 
temos que CC' é um ciclo de G com mais arestas 
que C.
• Absurdo porque C era máximo em número de 
arestas.
5 – Circuito Euleriano
206Teoria de Grafos
Circuito euleriano
• Corolário: Um grafo tem um caminho 
euleriano se e somente se tem no 
máximo dois nós de grau impar.
5 – Circuito Euleriano
207Teoria de Grafos
Circuito euleriano
• Ideia para determinar que um grafo não é 
hamiltoniano: tirar conjuntos de nós com 
grau alto e contar as componentes 
conexas.
• Condição necessária mas não suficiente.
5 – Circuito Euleriano
208Teoria de Grafos
Circuito euleriano
5 – Circuito Euleriano
209
Circuito Euleriano
Algoritmo de Fleury
Encontra um ciclo euleriano em grafo 
euleriano.
• Escolher um nó v0 qualquer. Fazer vc = v0. 
• Escolher uma aresta (vc, vp) que não seja 
ponte de G a menos que seja a única 
alternativa.
• Apagar (vc, vp) e fazer vc=vp.
• Se o grafo ainda tem arestas voltar ao 
passo 2. 
5 – Circuito Euleriano
210Teoria de Grafos
Carteiro Chines
• Problema do carteiro chines: Percorrer 
todas as arestas do grafo e voltar para o 
nó de início a custo mínimo.
– Caminhão coletor de lixo.
5 – Circuito Euleriano
211Teoria de Grafos
Carteiro Chines
• Se o grafo é euleriano, o circuito euleriano 
é a solução ótima pois o carteiro percorre 
cada aresta do grafo apenas uma vez.
5 – Circuito Euleriano
212Teoria de Grafos
Carteiro Chines
• Se o grafo tem nós de grau impar, algumas 
arestas deverão ser percorridas duas vezes.
• Algumas arestas devem ser duplicadas para 
transformar o grafo em um grafo euleriano.
• As arestas a serem duplicadas devem ser 
tais que:
– Todo nó fica com grau par.
– A soma dos pesos das arestas duplicadas 
deve ser mínima.
5 – Circuito Euleriano
213Teoria de Grafos
Carteiro Chines
• Quando o grafo tem apenas dois nós com 
grau impar as arestas que são parte do 
caminho mínimo entre esses dois nós 
devem ser duplicadas.
Depois usar o algoritmo de Fleury para 
determinar um circuito euleriano.
5 – Circuito Euleriano
214Teoria de Grafos
Carteiro Chines
• Se o grafo tem mais de dois nós de grau 
impar?
– Determinar o caminho mínimo entre todo par de 
nós de grau impar.
– Criar o grafo completo dos nós de grau impar 
com peso das arestas igual ao comprimento do 
caminho mínimo.
– Resolver emparelhamento a custo mínimo nesse 
grafo.
– Duplicar as arestas dos caminhos mínimos entre 
os nós emparelhados.
– Usar o algoritmo de Fleury para determinar um 
circuito euleriano.
5 – Circuito Euleriano
215Teoria de Grafos
Caminho e Ciclo Hamiltoniano
PROBLEMAS EM GRAFOS
6 – Ciclo e caminho Hamiltoniano
216Teoria de Grafos
Caminho Hamiltoniano
• Caminho hamiltoniano: Caminho 
simples que contém todo nó de G.
• Ciclo hamiltoniano: Ciclo simples que 
contém todo nó de G.
• Grafo hamiltoniano: grafo que tem um 
ciclo hamiltoniano.
• Determinar se um grafo é hamiltoniano 
é NP-Completo.
6 – Ciclo e caminho Hamiltoniano
217Teoria de Grafos
Caminho Hamiltoniano
• Teorema: Se G é hamiltoniano, para todo 
S ⊂ V tal que |S|>0, o número de 
componentes conexas de G-S é menor 
igual a |S|.
– Tirando um nó não podem ficar mais que 1 
componente conexa. (sem ponto de 
articulação)
– Tirando dois nó não podem ficar mais que 2 
componentes conexas.
– etc.
6 – Ciclo e caminho Hamiltoniano
218Teoria de Grafos
Caminho Hamiltoniano
Problema do Caixeiro Viajante: apresentado 
em sala.
Dado um grafo ponderado G=(V,E), apresente 
um ciclo hamiltoniano de custo mínimo.
6 – Ciclo e caminho Hamiltoniano
219Teoria de Grafos
Caminho Hamiltoniano
6 – Ciclo e caminho Hamiltoniano
Outros variantes do problema de roteamento:
• PRV Capacitado
• PRV Assimétrico
• PRV Aberto
• PRV e PCV com Coleta e Entrega Simultânea
• PRV com Múltiplos Depósitos
• PRV com Frota Heterogênea
220Teoria de Grafos
PROBLEMAS EM GRAFOS
7 – Coloração de Vértices
221Teoria de Grafos
PROBLEMAS EM GRAFOS
7 – Coloração de Vértices
Aplicação
222Teoria de Grafos
PROBLEMAS EM GRAFOS
7 – Coloração de Vértices
O problema consiste em atribuir cores aos 
nós de um grafo de forma que nenhum par 
de vértices adjacentes tenha a mesma cor e 
o total de cores usadas na atribuição seja 
mínimo.
Coloração de Vértices
• Problema:
– Alunos cursam disciplinas.
– Cada disciplina tem uma prova.
– Há um único horário em que são marcadas provas em 
cada dia.
– Provas de duas disciplinas diferentes não podem ser 
marcadas para o mesmo dia se há alunos que cursam 
as duas disciplinas.
• Montar um calendário de provas:
– satisfazendo as restrições de conflito e …
– … minimizando o número de dias necessários para 
realizar todas as provas.
• Modelagem por conjuntos:
   





 






 












A
B
C
D
E
F
Coloração de Vértices
• Os alunos que fazem apenas uma disciplina influem 
na modelagem? 
– Não!
• O número de alunos que cursam simultaneamente um 
par de disciplinas influi na modelagem? 
– Não!
– E se o objetivo fosse minimizar o número de alunos 
“sacrificados”?
– Neste caso, sim!
• Este modelo pode ser simplificado?
Coloração de Vértices
• Simplificação tratando-se apenas as 
interseções:
 







 




















A
B
C
D
E
F 






A
B
C
D
E
F
Considerar apenas as 
interseções não-vazias.
Coloração de Vértices
• Simplificação com a utilização de um grafo de conflitos:







E
 





















A
B
C
D
F
disciplinas → nós 
conflitos → arestas






A
B
C
D
E
F
A
B C F
E
D
Coloração de Vértices
• Simplificação com a utilização de um grafo de 
conflitos:
 








 





















A
B
C
D
E
F A
B C F
E
D
disciplinas → nós 
conflitos → arestas
Coloração de Vértices
• As provas de um par dedisciplinas não 
podem ser marcadas simultaneamente 
se existe uma aresta entre os nós que 
representam estas duas disciplinas. 
• Outros modelos de dados: listas, 
árvores, conjuntos, circuitos
• Como representar em computador o 
modelo de dados chamado grafo?
– Matriz de incidência (nó-aresta)
– Matriz de adjacência (nó-nó)
Grafo = [ nós, arestas ]
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer combinação 
de disciplinas sem conflitos: A, B, C, D, E, F, AE, 
AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer 
combinação de disciplinas sem conflitos: A, B, 
C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
• Escolher por exemplo o par de disciplinas B e E para o primeiro 
dia e retirá-las do grafo.
Coloração de Vértices
• Como montar um calendário satisfazendo as 
restrições de conflito?
• Marcar para o primeiro dia qualquer combinação 
de disciplinas sem conflitos: A, B, C, D, E, F, AE, 
AF, BD, BE, BF, CD, CE, DF, BDF
C
D
F
A
• Escolher por exemplo o par de disciplinas B e E para o primeiro 
dia e retirá-las do grafo.
Coloração de Vértices
• Marcar para o segundo dia qualquer 
combinação de disciplinas sem conflitos: A, C, 
D, F, AF, CD, DF
C
D
F
A
• Marcar para o segundo dia qualquer 
combinação de disciplinas sem conflitos: A, C, 
D, F, AF, CD, DF
C
D
F
A
Coloração de Vértices
• Marcar para o segundo dia qualquer 
combinação de disciplinas sem conflitos: A, C, 
D, F, AF, CD, DF
C
D
F
A
Coloração de Vértices
• Marcar para o segundo dia qualquer combinação 
de disciplinas sem conflitos: A, C, D, F, AF, CD, 
DF
C
D
F
A
Coloração de Vértices
• Marcar para o segundo dia qualquer 
combinação de disciplinas sem conflitos: A, C, 
D, F, AF, CD, DF
C
D
F
A
• Escolher por exemplo o par de disciplinas D e F para o segundo 
dia e retirá-las do grafo.
Coloração de Vértices
• Marcar para o segundo dia qualquer 
combinação de disciplinas sem conflitos: A, C, 
D, F, AF, CD, DF
C
A
• Escolher por exemplo o par de disciplinas D e F para o segundo 
dia e retirá-las do grafo.
Coloração de Vértices
• Marcar A ou C para o terceiro dia e a que 
sobrar para o quarto dia:
C
A
Coloração de Vértices
• A solução assim construída utiliza quatro dias: 
B-E no primeiro dia, D-F no segundo dia, A no 
terceiro e C no quarto:
B C
E
D
F
A
• Uma solução com quatro dias corresponde a colorir os nós do 
grafo de conflitos com quatro cores!
• Esta solução utiliza o menor número possível de 
dias? ou ...
• É possível montar uma solução com menos dias? 
ou ...
• É possível colorir o grafo de conflitos com três cores?
B C
E
D
F
A
• É impossível colorir o grafo de conflitos com menos de três 
cores! (por que?)
Sim!
Coloração de Vértices
251Teoria de Grafos
Subconjunto Independente 
Máximo
PROBLEMAS EM GRAFOS
Um subconjunto independente de um grafo é um 
subconjunto de nós sem que no grafo não exista 
nenhuma aresta entre seus elementos.
8 – Subconjunto independente máximo
• Na aplicação do problema anterior, como 
montar um escalonamento com o menor 
número possível de dias?
• Recordando: um subconjunto independente de 
um grafo é um subconjunto de nós sem 
nenhuma aresta entre eles.
• Logo, um conjunto de disciplinas que forma um 
subconjunto independente dos nós do grafo de 
conflitos pode ter suas provas marcadas para o 
mesmo dia.
• Os nós deste subconjunto independente podem 
receber a mesma cor.
Subconjunto independente máximo
• Quanto mais disciplinas forem marcadas para o 
primeiro dia, menos disciplinas sobram para os 
dias seguintes e, portanto, serão necessários 
menos dias para realizar as provas das 
disciplinas restantes.
• Então, marcar para o primeiro dia as provas das 
disciplinas correspondentes a um subconjunto 
independente máximo.
• Retirar os nós correspondentes a estas 
disciplinas do grafo de conflitos.
• Continuar procedendo da mesma maneira, até 
as provas de todas as disciplinas terem sido 
marcadas. 
Subconjunto independente máximo
• Subconjunto independente máximo no grafo 
de conflito?
BDF
B C
E
D
F
A
Subconjunto independente máximo
• Subconjunto independente máximo no grafo 
de conflito?
BDF
B C
E
D
F
A
• Eliminar os nós B, D e F do grafo de conflitos.
Subconjunto independente máximo
• Subconjunto independente máximo no grafo 
de conflito?
BDF
C
E
A
• Eliminar os nós B, D e F do grafo de conflitos.
Subconjunto independente máximo
• Subconjunto independente máximo no grafo 
de conflito?
CE
C
E
A
Subconjunto independente máximo
• Subconjunto independente máximo no grafo 
de conflito?
CE
C
E
A
• Eliminar os nós C e E do grafo de conflitos.
Subconjunto independente máximo
• Subconjunto independente máximo no grafo 
de conflito?
CE
A
• Eliminar os nós C e E do grafo de conflitos.
Subconjunto independente máximo
• Subconjunto independente máximo no grafo 
de conflito?
A
A
Subconjunto independente máximo
• Subconjunto independente máximo no grafo