Rafael de Santiago

Anotações para a Disciplina de Grafos

Versão de 27 de março de 2023

6
2

5 3
4

Universidade Federal de Santa Catarina

 Sumário

List of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1 Definições Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Grafos Valorados ou Ponderados . . . . . . . . . . . . . . . . . . . 8
1.1.2 Grafos Orientados . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.3 Hipergrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.4 Multigrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.5 Grau de um Vértice . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1.6 Igualdade e Isomorfismo . . . . . . . . . . . . . . . . . . . . . . . 12
1.1.7 Partição de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1.8 Matriz de Incidência . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.9 Operações com Grafos . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.10 Vizinhança . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.11 Grafo Regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.12 Grafo Simétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.13 Grafo Anti-simétrico . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.14 Grafo Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.15 Grafo Complementar . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.16 Percursos em Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.17 Cintura e Circunferência . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.18 Planaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.19 Vértice de Corte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.20 Ponte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.21 Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.22 Anti-Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.23 SCIE (Subconjunto Internamente Estável ou conjunto indepen-
dente) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.1.24 SCEE (Subconjunto Externamente Estável ou conjunto dominante) 18
2 Representações Computacionais . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Lista de Adjacências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Matriz de Adjacências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Buscas em Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1 Busca em Largura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Complexidade da Busca em Largura . . . . . . . . . . . . . . . . . 24
3.1.2 Propriedades e Provas . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.2.1 Caminhos Mínimos . . . . . . . . . . . . . . . . . . . . . 24
3.1.2.2 Árvores em Largura . . . . . . . . . . . . . . . . . . . . . 27
3.2 Busca em Profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 Complexidade da Busca em Profundidade . . . . . . . . . . . . . 28
4 Caminhos e Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1 Caminhos e Ciclos Eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.0.1 Curiosidade . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.1.1 Algoritmo de Hierholzer . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Caminhos e Ciclos Hamiltonianos . . . . . . . . . . . . . . . . . . . . . . 38
4.2.1 Caixeiro Viajante . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5 Caminhos Mínimos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
 5.1 Propriedades de Caminhos Mínimos . . . . . . . . . . . . . . . . . . . . . 43
5.1.1 Propriedade de subcaminhos de caminhos mínimos o são . . . 43
5.1.2 Propriedade de desigualdade triangular . . . . . . . . . . . . . . 44
5.1.3 Propriedade de limite superior . . . . . . . . . . . . . . . . . . . . 44
5.1.4 Propriedade de inexistência de caminho . . . . . . . . . . . . . . 45
5.1.5 Propriedade de convergência . . . . . . . . . . . . . . . . . . . . . 45
5.1.6 Propriedade de relaxamento de caminho . . . . . . . . . . . . . . 46
5.1.7 Propriedade de relaxamento e árvores de caminho mínimo . . . 47
5.1.8 Propriedade de subgrafo dos predecessores . . . . . . . . . . . . 48
5.2 Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2.1 Complexidade de Bellman-Ford . . . . . . . . . . . . . . . . . . . 51
5.2.2 Corretude de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . 51
5.3 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.3.1 Complexidade de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.2 Corretude do Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . 55
5.4 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.4.1 Complexidade de Floyd-Warshall . . . . . . . . . . . . . . . . . . 57
5.4.2 Corretude de Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . 58
5.4.3 Construção de Caminhos Mínimos para Floyd-Warshall . . . . . 58
6 Problemas de Travessia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1 Problema dos Canibais e Missionários . . . . . . . . . . . . . . . . . . . . 62
6.1.1 Construção e Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2 Problemas dos Potes de Vinho . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.3 Problema da Fuga dos Ladrões . . . . . . . . . . . . . . . . . . . . . . . . 65
6.4 Problema dos três maridos ciumentos . . . . . . . . . . . . . . . . . . . . 65
6.5 Problema de Agrupamento de Indivíduos . . . . . . . . . . . . . . . . . . 65
7 Conectividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.1 Componentes Fortemente Conexas . . . . . . . . . . . . . . . . . . . . . . 67
7.1.1 Complexidade do Algoritmo de Componentes Fortemente Conexas 69
7.1.2 Corretude do Algoritmo de Componentes Fortemente Conexas 69
7.1.2.1 Propriedades de Buscas em Profundidade . . . . . . . 69
7.1.2.2 Propriedades de Componentes Fortemente Conexas . 71
7.2 Ordenação Topológica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.2.1 Complexidade da Ordenação Topológica . . . . . . . . . . . . . . 75
7.2.2 Corretude da Ordenação Topológica . . . . . . . . . . . . . . . . . 75
8 Árvores Geradoras Mínimas . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.1 Propriedades do Método Genérico . . . . . . . . . . . . . . . . . . . . . . 78
8.2 Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.2.1 Complexidade do Algoritmo de Kruskal . . . . . . . . . . . . . . . 80
8.3 Algoritmo de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.3.1 Complexidade do Algoritmo de Prim . . . . . . . . . . . . . . . . 82
9 Fluxo Máximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
9.1 Redes de Fluxo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
9.2 Rede Residual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
9.3 Caminhos Aumentantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
9.4 Cortes de Redes de Fluxo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
9.5 Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
9.5.1 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
9.6 Edmonds-Karp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.6.1 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
10 Emparelhamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
 10.1 Emparelhamento Máximo em Grafos Bipartidos . . . . . . . . . . . . . . 91
10.1.1 Resolução por Fluxo Máximo . . . . . . . . . . . . . . . . . . . . . 91
10.1.1.1 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . 93
10.1.2 Algoritmo de Hopcroft-Karp . . . . . . . . . . . . . . . . . . . . . 93
10.1.2.1 Algoritmo detalhado . . . . . . . . . . . . . . . . . . . . 94
10.1.2.2 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . 96
10.2 Emparelhamento Máximo em Grafos . . . . . . . . . . . . . . . . . . . . . 96
11 Coloração de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
11.1 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
11.2 Algoritmo de Lawler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
11.2.1 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
11.3 Listar Conjuntos Independentes Maximais . . . . . . . . . . . . . . . . . 102
12 Caminho Crítico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
12.1 Listar Conjuntos Independentes Maximais . . . . . . . . . . . . . . . . . 105
12.2 Cálculo do caminho crítico . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
A Revisão de Matemática Discreta . . . . . . . . . . . . . . . . . . . . . . 111
B Estruturas de Dados Auxiliares . . . . . . . . . . . . . . . . . . . . . . . 113
B.1 Conjuntos Disjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
 Índice de algoritmos

1 Criação de uma lista de adjacências para um grafo dirigido e ponderado. 20

2 Criação de uma matriz de adjacências para um grafo dirigido e ponderado. 21

3 Busca em largura. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Busca em profundidade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 Algoritmo de Hierholzer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6 Algoritmo de Auxiliar “busc ar Subci cl oEul er i ano”. . . . . . . . . . . . . 35
7 Algoritmo de Bellman-Held-Karp. . . . . . . . . . . . . . . . . . . . . . . . . 39

8 Inicialização de G. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
9 Relaxamento de v. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
10 Algoritmo de Bellman-Ford. . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
11 Algoritmo de Dijkstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
12 Algoritmo de Floyd-Warshall. . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
13 Algoritmo de Floyd-Warshall com Matriz dos Predecessores. . . . . . . . . 59
14 Print-Shortest-Path. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

15 Algoritmo de Componentes-Fortemente-Conexas . . . . . . . . . . . . . . 68
16 DFS de Cormen et al. (2012). . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
17 DFS-Visit de Cormen et al. (2012). . . . . . . . . . . . . . . . . . . . . . . . . 69
18 DFS para Ordenação Topológica . . . . . . . . . . . . . . . . . . . . . . . . . 74
19 DFS-Visit-OT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

20 Método Genérico de Cormen et al. (2012). . . . . . . . . . . . . . . . . . . . 78

21 Algoritmo de Kruskal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
22 Algoritmo de Prim. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

23 Algoritmo de Ford-Fulkerson. . . . . . . . . . . . . . . . . . . . . . . . . . . 87
24 Busca em Largura para Edmonds-Karp. . . . . . . . . . . . . . . . . . . . . 88

25 Adaptação de entrada de Emparelhamento Máximo para um algoritmo de

Fluxo Máximo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
26 Resolução de Emparelhamento Máximo através um algoritmo de Fluxo
Máximo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
27 Algoritmo de Hopcroft-Karp. . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
28 Algoritmo de Hopcroft-Karp detalhado. . . . . . . . . . . . . . . . . . . . . 94
29 BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
30 DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
31 Emparelhamento máximo para grafos não-dirigidos e não-ponderados. . 97
32 AumentanteAlternante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
33 Blossom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6 SUMÁRIO

34 Algoritmo de Lawler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

35 Listar Conjuntos Independentes Maximais . . . . . . . . . . . . . . . . . . 102

36 Listar Conjuntos Independentes Maximais . . . . . . . . . . . . . . . . . . 105

 CAPÍTULO 1
Introdução

1.1 Definições Iniciais

Antes de visitar a representação de grafos, é importante que saibamos o que são vér-

tices e arestas. Vértices geralmente são representados como unidades, elementos ou

entidades, enquanto as arestas representam as ligações/conexões entre pares de vér-

tices. Geralmente, chamaremos o conjunto de vértices de V e o conjunto de arestas

de E . Define-se que E ⊆ V × V . Também usaremos n e m para denotarem o número

de vértices e arestas respectivamente, então n = |V | e m = |E |. O número de arestas

n 2 −n
possível em um grafo é 2 .

Um grafo pode ser representado de duas formas (CORMEN et al., 2012). A primeira

forma é chamada de lista de adjacências e tem mais popularidade em artigos científicos.

Nela, o grafo é representado como uma dupla para especificar vértices e arestas. Por

exemplo, para um grafo G, pode-se dizer que o mesmo é uma dupla G = (V, E ), especifi-

cando assim que o grafo G possui um conjunto V de vértices e E de arestas. A segunda

forma seria uma através de uma matriz binária, chamada de matriz de adjacência.

Normalmente representada pela letra A(G), a matriz é definida por A(G) = {0, 1}|V |×|V | ,

a qual seus elementos a u,v = 1 se existir uma aresta entre os vértices u e v. Um exemplo

das das formas para um mesmo grafo pode ser visualizado no Exemplo 1.1.1.
8 Capítulo 1. Introdução

Example 1.1.1. A Figura 1 exibe um grafo de 4 vértices e 4 arestas. Na representação

por listas de adjacências, o grafo pode ser representado da seguinte forma

G = ({1, 2, 3, 4}, {{1, 2}, {1, 4}, {2, 4}, {3, 4}}). (1.1)

A representação por uma matriz de adjacência ficaria assim

1 2 3 4

1 0 1 0 1

A(G) = 2 1 0 0 1 .

3 0 0 0 1

4 1 1 1 0

1 3

2 4
Figura 1 – Exemplo de grafo com 4 vértices e 4 arestas.

1.1.1 Grafos Valorados ou Ponderados

Um grafo é valorado quando um peso ou valor é associado a suas arestas. Na literatura,

a definição do grafo passa a ser uma tripla G = (V, E , w), na qual V é o conjunto de

vértices, E é o conjunto de arestas e w : e ∈ E → R é a função que especifica o valor.

Quando não se possui valornas arestas, parte-se de uma relação binária entre existir

ou não uma aresta entre dois vértices. Neste caso, se u e v possui uma aresta, geralmente

se simboliza essa ligação com o valor 1, e se não existir 0.

1.1. Definições Iniciais 9

Em uma matriz de adjacências para grafos valorados, o valor das arestas aparecem

nas células da matriz. Em um par de vértices que não possui valor estabelecido (não há

aresta), representa-se com uma lacuna ou com um valor simbólico para o problema que

o grafo representa. Por exemplo, se os valores representam as distâncias, geralmente se

associa o valor infinito aos pares de vértices que não possuem arestas.

Um exemplo de grafo valorado e suas representações pode ser visualizado no Exem-

plo 1.1.2.

Example 1.1.2. A Figura 2 exibe um grafo valorado de 4 vértices e 4 arestas. Na repre-

sentação por listas de adjacências, o grafo pode ser representado da seguinte forma

G = ({1, 2, 3, 4}, {{1, 2}, {1, 4}, {2, 4}, {3, 4}}, w). (1.2)

A função w teria os seguintes valores: w({1, 2}) = 8, w({1, 4}) = 9, w({2, 4}) = 5 e w({3, 4}) =

7.

A representação por uma matriz de adjacência ficaria assim

1 2 3 4

1 0 8 0 9

A(G) = 2 8 0 0 5

3 0 0 0 7

4 9 5 7 0
ou desta outra forma para o caso de uma aplicação a problemas que envolvam

distâncias
1 2 3 4

1 ∞ 8 ∞ 9

A(G) = 2 8 ∞ ∞ 5 .

3 ∞ ∞ ∞ 7

4 9 5 7 ∞
10 Capítulo 1. Introdução

1 3
9
8 7
2 5
4
Figura 2 – Exemplo de grafo valorado com 4 vértices e 4 arestas.

Grafos com Sinais

Para representar alguns problemas, utiliza-se valores negativos associados às arestas.

Um exemplo disso, seriam grafos que representem relações de amizade e de inimizade.

Para amizade, utiliza-se o valor 1 e para inimizade o valor −1. Nesse caso, não dizemos

que o grafo é valorado ou ponderado, mas sim um grafo com sinais. Quando os valores

negativos e positivos podem ser diferentes de 1 e −1, diz-se que os grafos são valorados

e com sinais.

1.1.2 Grafos Orientados

Um grafo orientado é aquele no qual suas arestas possuem direção. Nesse caso, não

chamamos mais de arestas e sim de arcos. Um grafo orientado é definido como uma

dupla G = (V, A), a qual V é o conjunto de vértices e A é o conjunto de arcos. O conjunto

de arcos é composto por pares ordenados (u, v), os quais u, v ∈ V e representam um

arco saindo de u e incidindo em v. Duas funções importantes devem ser consideradas

nesse contexto: a função de arcos saintes δ+ (v) = {(v, u) : (v, u) ∈ A} e arcos entrantes

δ− (v) = {(u, v) : (u, v) ∈ A}.

O Exemplo 1.1.3 exibe a representação de um grafo orientado.

1.1. Definições Iniciais 11

Example 1.1.3. A Figura 3 exibe um grafo orientado de 4 vértices e 4 arestas. Na repre-

sentação por listas de adjacências, o grafo pode ser representado da seguinte forma

G = ({1, 2, 3, 4}, {(1, 4), (2, 1), (4, 2), (4, 3)}). (1.3)

A representação por uma matriz de adjacência ficaria assim

1 2 3 4

1 0 0 0 1

A(G) = 2 1 0 0 0 .

3 0 0 0 0

4 0 1 1 0

1 3

2 4
Figura 3 – Exemplo de grafo orientado com 4 vértices e 4 arcos.

1.1.3 Hipergrafo

Um hipergrafo H = (V, E ) é um grafo no qual as arestas podem conectar qualquer

número de vértices. Cada aresta é chamada de hiperaresta E ⊆ 2V \{}.

1.1.4 Multigrafo

Um multigrafo G = (V, E ) é um grafo que permite múltiplas arestas para o mesmo par de

vértices. Logo, não se tem mais um conjunto de arestas, mas sim uma tupla de arestas.
12 Capítulo 1. Introdução

Para o exemplo da Figura 4, têm-se E = ({1, 2}, {1, 2}, {1, 4}, {2, 4}, {3, 4}, {3, 4}).

1 3

2 4
Figura 4 – Exemplo de um multigrafo com 4 vértices e 6 arestas.

1.1.5 Grau de um Vértice

O grau de um vértice é a quantidade de arestas que se conectam a determinado vértice.

É denotada por uma função d v , onde v ∈ V . Em um grafo orientado, o número de arcos

saintes para um vértice v é denotado por d v+ , e o número de arcos entrantes é denotado

por d v− .

1.1.6 Igualdade e Isomorfismo

Diz-se que dois grafos G 1 = (V1 , E 1 ) e G 2 = (V2 , E 2 ) são iguais se V1 = V2 e E 1 = E 2 . Os

dois grafos são considerados isomorfos se existir uma função bijetora (uma-por-uma)

para todo v ∈ V1 e para todo u ∈ V2 preserve as relações de adjacência (NETTO, 2006).

1.1.7 Partição de Grafos

Uma partição de um grafo é uma divisão disjunta de seu conjunto de vértices. Um grafo

G = (V, E ) é dito k-partido se existir uma partição P = {p i |i = 1, . . . , k ∧ ∀ j ∈ {1, . . . , k}, j 6=

i (p i ∩ p j 6= {})}. Quando k = 2, dize que o grafo é bipartido (NETTO, 2006).

1.1. Definições Iniciais 13

1.1.8 Matriz de Incidência

Sobre um grafo orientado G = (V, E ), uma matriz de incidência B (G) = {+1, −1, }|V |×|A|

mapeia a origem e o destino de cada arco no grafo G. Dado um arco (u, v), b u,(u,v) = +1

e b v,(u,v) = −1 (NETTO, 2006).

1.1.9 Operações com Grafos

As seguintes operações binárias são descritas em Netto (2006):

• União: Dados os grafos G 1 = (V1 , E 1 ) e G 2 = (V2 , E 2 ), G 1 ∪G 2 = (V1 ∪ V2 , E 1 ∪ E 2 );

• Soma (ou join): Dados os grafos G 1 = (V1 , E 1 ) e G 2 = (V2 , E 2 ), G 1 +G 2 = (V1 ∪V2 , E 1 ∪

E 2 ∪ {{u, v} : u ∈ V1 ∧ v ∈ V2 });

• Produto cartesiano: Dados os grafos G 1 = (V1 , E 1 ) e G 2 = (V2 , E 2 ), G 1 ×G 2 = (V1 ×

V2 , E ), onde E = {{(v, w), (x, y)} : (v = x ∧{w, y} ∈ E 2 )∨(w = y ∧{x, y} ∈ E 1 )}. G 1 ×G 2

e G 2 ×G 1 são isomorfos;

• Composição ou produto lexicográfico: Dados os grafos G 1 = (V1 , E 1 ) e G 2 = (V2 , E 2 ),

G 1 ◦ G 2 = (V1 × V2 , E ), onde E = {{(v, w), (x, y)} : ({v, x} ∈ E 1 ∨ v = x) ∧ {w, y} ∈ E 2 };

• Soma de arestas: Dados os grafos G 1 = (V1 , E 1 ) e G 2 = (V2 , E 2 ), os quais V1 = V2 ,

G 1 ⊕G 2 = (V1 , E 1 ∪ E 2 ).

A seguinte operação unária é descrita em Netto (2006):

• Contração de dois vértices: Dado um grafo G = (V, E ) e dois vértices u, v ∈ V , a

operação de contração desses dois vértices em G, gera um grafo G 0 = (V 0 , E 0 ) o qual

V 0 = V \{u, v} ∪ {uv} e E 0 = {{x, y} ∈ E : x 6= u ∧ x 6= v} ∪ {{x, uv} : {x, u}, {x, v} ∈ E }.

Outras operações sobre grafos são descritas na literatura. Esse texto irá omití-las

por enquanto para que sejam utilizados no momento mais oportuno. Sõ elas: inserção

e remoção de vértices e arestas, desdobramento de um vértice. Essa última depende do

contexto de aplicação.
14 Capítulo 1. Introdução

1.1.10 Vizinhança

A vizinhança de vértices é diferente para grafos não-orientados e orientados. Para

um grafo grafo não-orientado G = (V, E ), uma função de vizinhança é definida por

N : v ∈ V → {u ∈ V : {v, u} ∈ E } e indica o conjunto de todos os vizinhos de um vértice

específico. Para o grafo do Exemplo 1.1.1, N (1) = {2, 4}.

Para um grafo orientado G = (V, A), diz-se que um vértice u ∈ V é sucessor de v ∈ V

quando (v, u) ∈ A; e u ∈ V é antecessor de v ∈ V quando (u, v) ∈ A. As funções de

vizinhança para um grafo orientado G são N + : v ∈ V → {u ∈ V : (v, u) ∈ A}, N − : v ∈ V →

{u ∈ V : (u, v) ∈ A}, e N (v) = N + (v) ∪ N − (v).

Diz-se que a vizinhança de v é fechada quando esse mesmo vértice se inclui no

conjunto de vizinhos. A função que representa vizinhança fechada v é simbolizada

neste texto como N∗ (v) = N (v) ∪ {v}.

As funções de vizinhança também podem ser utilizadas para identificar um conjunto

de vértices vizinhos de um grupo de vértices em um grafo G = (V, E ) (orientado ou não).

Nesse contexto, N (S) = v∈S N (v), N + (S) = v∈S N + (v), e N − (S) = v∈S N − (v).
S S S

As noções de sucessor e antecessor podem ser aplicadas iterativamente. As Equações

(1.4), (1.5), (1.6) e (1.7) exibem exemplos de fechos transitivos diretos.

N 0 (v) = {v} (1.4)

N +1 (v) = N + (v) (1.5)

N +2 (v) = N + N +1 (v)
¡ ¢
(1.6)

N +n (v) = N + N +(n−1) (v)

¡ ¢
(1.7)

Chama-se de fecho transitivo direto aqueles que correspondem aos vizinhos suces-

sivos e os inversos os que correspondem aos vizinhos antecessores. Um fecho transitivo

1.1. Definições Iniciais 15

direto de um vértice v de um grafo G = (V, E ) são todos os vértices atingíveis a partir v

no grafo G; ele é representado pela função R + (v) = |V

S | +k
k=0
N (v). Um fecho transitivo

inverso de v é o conjunto de vértices que atingem v; ele é representado pela função

R − (v) = |V
S | −k
k=0
N (v). Diz-se que w é descendente de v se w ∈ R + (v). Diz-se que w é

ascendente de v se w ∈ R − (v).

1.1.11 Grafo Regular

Um grafo não-orientado G = (V, E ) que tenha d (v) = k∀v ∈ V é chamado de grafo

k-regular ou de grau k. Um grafo orientado G o = (V, A) que possui a propriedade

d + (v) = k∀v ∈ V é chamado de grafo exteriormente regular de semigrau k. Se G o tiver

d − (v) = k∀v ∈ V é chamado de grafo interiormente regular de semigrau k.

1.1.12 Grafo Simétrico

Um grafo orientado G = (V, A) é simétrico se (u, v) ∈ A ⇐⇒ (v, u) ∈ A∀u, v ∈ V .

1.1.13 Grafo Anti-simétrico

Um grafo orientado G = (V, A) é anti-simétrico se (u, v) ∈ A ⇐⇒ (v, u) ∉ A∀u, v ∈ V .

1.1.14 Grafo Completo

Um grafo completo G = (V, E ) é completo se E = V × V .

Grafos bipartidos completos G B = ((X , Y ), E ) possuem E = X × Y .

1.1.15 Grafo Complementar

Para um grafo G = (V, E ), um grafo complementar é definido por G c = G = (V, (V ×V )\E ).

16 Capítulo 1. Introdução

1.1.16 Percursos em Grafos

“Um percurso, itinerário ou cadeia é uma família de ligações sucessivamente adjacentes,

cada uma tendo uma extremidade adjacente a anterior e a outra à subsequente (à

execeção da primeira e da última)” (NETTO, 2006). Diz-se que um percurso é aberto

quando a última ligação é adjacente a primeira. Têm-se desse modo um ciclo.

Um percurso é considerado simples se não repetir ligações (NETTO, 2006).

Caminhos são cadeias em grafos orientados.

Circuitos são ciclos em grafos orientados.

1.1.17 Cintura e Circunferência

Cintura de um grafo G é comprimendo do menor ciclo existente no grafo. É representada

pela função g (G). A circunferência é comprimento do maior ciclo. A circunferência do

grafo G é representada pela função c(G).

1.1.18 Planaridade

Netto (2006) comenta que a noção de planaridade se baseia na ideia da representação

de um conjunto de elementos em um plano, como em um mapa. Nesse contexto, um

grafo planar pode ser representado em um plano sem que suas arestas se cruzem. Um

grafo plano é um grafo planar que foi desenhado numa superfície plana.

Netto (2006) cita três resultados mais conhecidos para considerar que um grafo é

planar:

• (Harary) Um grafo é planar sse não tiver, como subgrafo, um grafo homeomorfo1

a K 5 2 ou a K 3,3 3 .
1
Um grafo H é homeomorfo a um grafo G, se H pode ser obtido de G pela inserção de vértices de grau
2 em pontos intermediários de suas arestas (substitui uma aresta {u, v}, adicionando um vértice w e
duas arestas {u, w} e {v, w}) (NETTO, 2006).
2
Grafo K 5 : grafo completo com cinco vértices.
3
Grafo K 3,3 : grafo bipartido com 3 vértices para cada parte e cada parte se conecta a outra completa-
mente (9 arestas).
1.1. Definições Iniciais 17

• (Wagner) Um grafo G é planar sse ele não contiver um subgrafo contratível a K 5

ou a K 3,3 .

• (Whitney) Um grafo G 2-conexo4 é planar sse possui um dual5 .

1.1.19 Vértice de Corte

Um vértice é dito ser um vértice de corte se sua remoção (juntamente com as ares-

tas a ele conectadas) provoca um redução na conexidade do grafo (passa a ter mais

componentes desconexas).

1.1.20 Ponte

Uma aresta é dita ser um a ponte se sua remoção provoca um redução na conexidade

do grafo (passa a ter mais componentes desconexas).

1.1.21 Base

Uma base de um grafo G(V, E ) é um subconjunto B ⊆ V , tal que:

• dois vértices quaisquer de B não são ligados por nenhum caminho;

• todo vértice não pertencente a B pode ser atingido por um caminho partindo de

B.

1.1.22 Anti-Base

Uma anti-base de um grafo G(V, E ) é um subconjunto A ⊆ V , tal que:

• dois vértices quaisquer de A não são ligados por nenhum caminho;

• de todo vértice não pertencente a A pode se atingir A por um caminho.

4
Grafo k-conexo: são necessários desconectar no mínimo k vértices para desconectar o grafo conexo.
5
Um grafo dual D é obtido a partir de um grafo G tal que cada vértice de D corresponde a uma face em
G e cada aresta em D conecta duas faces adjacentes em G.
18 Capítulo 1. Introdução

1.1.23 SCIE (Subconjunto Internamente Estável ou conjunto inde-

pendente)

Seja G(V, A) um grafo não orientado. Diz-se que S ⊂ V é um subconjunto internamente

estável se dois vértices quaisquer de S nunca são adjacentes entre si.

Agora, se dado um SCIE S não existe um outro SCIE S 0 tal que S ⊂ S 0 , então S é dito

ser um SCIE maximal.

1.1.24 SCEE (Subconjunto Externamente Estável ou conjunto do-

minante)

Seja G(V, A) um grafo orientado. Diz-se que T ⊂ V é um subconjunto externamente

estável se todo vértice não pertencente a T tiver pelo menos um vértice de T como

sucessor. A Figura 5 traz um grafo dirigido com o conjunto dominante {A, B,C }.

A B C

D E F

Figura 5 – Exemplo de conjunto SCEE.

Se dado um SCEE T não existe um outro SCEE T 0 tal que T 0 ⊂ T , então T é dito

ser um SCEE minimal. Este conceito também pode ser aplicado a grafos não-dirigidos,

bastando que considere-se que todo vértice exterior a T deva ter como adjacente pelo

menos um vértice de T .
 CAPÍTULO 2
Representações Computacionais

Duas formas de representação computacional de grafos são amplamente utilizadas.

São elas “listas de adjacências” e “por matriz de adjacências” (CORMEN et al., 2012).

Elas possuem vantagens e desvantagens principamente relacionadas à complexidade

computacional (consumo de recursos em tempo e espaço). Detalhes sobre vantagens e

desvantagens não aparecerão nesse documento. Um de nossos objetivos do momento

será implementar e avaliar as duas formas de representação.

2.1 Lista de Adjacências

A representação de um grafo G = (V, E ) por listas de adjacências consiste em um arranjo,

chamado aqui de Adj. Esse arranjo é composto por |V | listas, e cada posição do arranjo

representa as adjacências de um vértice específico (CORMEN et al., 2012). Para cada

{u, v} ∈ E , têm-se Adj[u] = (. . . , v, . . .) e Adj[v] = (. . . , u, . . .) quando G for não-dirigido.

Quando G for dirigido, para cada (u, v) ∈ E , têm-se Adj[u] = (. . . , v, . . .).

Para grafos ponderados, Cormen et al. (2012) sugere o uso da própria estrutura de ad-

jacências para armazenar o peso. Dado um grafo ponderado não-dirigido G = (V, E , w),
¡ ¡ ¢ ¢ ¡ ¡ ¢ ¢
para cada {u, v} ∈ E , têm-se Adj[u] = . . . , v, w({u, v}) , . . . e Adj[v] = . . . , u, w({u, v}) , . . . .
¡ ¡ ¢ ¢
Quando o grafo for dirigido, para cada (u, v) ∈ E , têm-se Adj[u] = . . . , v, w((u, v)) , . . . .
20 Capítulo 2. Representações Computacionais

O Algoritmo 1 representa a carga de um grafo dirigido e ponderado G = (V, A, w) em

uma lista de adjacências Adj.

Algoritmo 1: Criação de uma lista de adjacências para um grafo dirigido e

ponderado.
Input :um grafo dirigido e ponderado G = (V, A, w)
1 criar arranjo Adj[|V |]
2 foreach v ∈ V do
3 Adj[v] ← listaVazia()
4 foreach (u, v) ∈ A do
¡ ¢
5 Adj[u] ← Adj[u] ∪ v, w((u, v))
6 return Adj

2.2 Matriz de Adjacências

Uma matriz de adjacência é uma representação de um grafo através de uma matriz A.

Para um grafo não-dirigido G = (V, E ), A = B|V |×|V | , na qual cada elemento a u,v = 1 e

a v,u = 1 se {u, v} ∈ E ; a u,v = 0 e a v,u = 0 caso {u, v} ∉ E . Para todo grafo não-dirigido G,

a u,v = a v,u .

Para um grafo dirigido G = (V, X ), A = B|V |×|V | , na qual cada elemento a u,v = 1 se

(u, v) ∈ A; a u,v = 0 e a u,v = 0 caso (u, v) ∉ X .

Para um grafo não-dirigido e ponderado G = (V, E , w), a matriz será formada por

células que comportem o tipo de dado representado pelos pesos. Assumindo que

os pesos serão números reais, então a matriz de adjacências será A = R|V |×|V | . Cada

elemento a u,v = w({u, v}) e a v,u = w({u, v}) se {u, v} ∈ E ; a u,v = ² e a v,u = ² caso {u, v} ∉

E . ² é um valor que representa a não conexão, geralmente 0, +∞ ou −∞ dependendo

do contexto de aplicação.

O Algoritmo 2 representa a carga de um grafo dirigido e ponderado G = (V, A, w) em

uma matriz de adjacências Adj.

2.3. Exercícios 21

Algoritmo 2: Criação de uma matriz de adjacências para um grafo dirigido e

ponderado.
Input :um grafo dirigido e ponderado G = (V, A, w : A → R), um símbolo ² que
representa a não adjacência
1 Ad j ← R|V |×|V |
2 foreach v ∈ V do
3 foreach u ∈ V do
4 Adju,v ← ²

5 foreach (u, v) ∈ A do
6 Adju,v ← w((u, v))
7 return Adj

2.3 Exercícios

Implemente as duas bibliotecas para grafos. Preencha a seguinte tabela a partir da

análise computacional, de acordo com as operações abaixo determinadas.

Lista de Adjacências Matriz de Adjacências

Inserção de vértice

inserção de arestas

Remoção de vértice

Remoção de arestas

Teste se {u, v} ∈ E

Percorrer vizinhos

Grau de um vértice
 CAPÍTULO 3
Buscas em Grafos

3.1 Busca em Largura

Dado um grafo G = (V, E ) e uma origem s, a busca em largura (Breadth-First Search -

BFS) explora as arestas/arcos de G a partir de s para cada vértice que pode ser atingido a

partir de s. É uma exploração por nível. O procedimento descobre as distâncias (número

de arestas/arcos) entre s e os demais vértices atingíveis de G. Pode ser aplicado para

grafos orientados e não-orientados (CORMEN et al., 2012).

O algoritmo pode produzir uma árvore de busca em largura com raiz s. Nessa árvore,

o caminho de s até qualquer outro vértice é um caminho mínimo em número de

arestas/arcos (CORMEN et al., 2012).

O Algoritmo 3 descreve as operações realizadas em uma busca em largura. Nele,

criam-se três estruturas de dados que serão utilizadas para armazenar os resultados

da busca. O arranjo C v é utilizado para determinar se um vértice v ∈ V foi visitado ou

não; D v determina a distância percorrida até encontrar o vértice v ∈ V ; e A v determina

o vértice antecessor ao v ∈ V em uma busca em largura a partir de s (CORMEN et al.,

2012).
24 Capítulo 3. Buscas em Grafos

Algoritmo 3: Busca em largura.

Input :um grafo G = (V, E ), vértice de origem s ∈ V
// configurando todos os vértices
1 C v ← false ∀v ∈ V
2 D v ← ∞ ∀v ∈ V
3 A v ← null ∀v ∈ V
// configurando o vértice de origem
4 C s ← true
5 Ds ← 0
// preparando fila de visitas
6 Q ← Fila()
7 Q.enqueue(s)
// propagação das visitas
8 while Q.empty() = false do
9 u ← Q.dequeue()
10 foreach v ∈ N (u) do
11 if C v = false then
12 C v ← true
13 Dv ← Du + 1
14 Av ← u
15 Q.enqueue(v)

16 return (D, A)

3.1.1 Complexidade da Busca em Largura

O número de operações de enfileiramento e desenfileiramento é limitado a |V | vezes,

pois visita-se no máximo |V | vértices. Como as operações de enfileirar e desenfileirar

podem ser realizadas em tempo Θ(1), então para realizar estas operações demanda-se

tempo de O(|V |). Deve-se considerar ainda, que muitas arestas/arcos incidem em vérti-

ces já visitados, então inclui-se na complexidade de uma BFS a varredura de todas as

adjacências, que demandaria Θ(|E |). Diz-se então, que a complexidade computacional

da BFS é O(|V | + |E |) .

3.1.2 Propriedades e Provas

3.1.2.1 Caminhos Mínimos

A busca em largura garante a descoberta dos caminhos mínimos em um grafo não-

ponderados G = (V, E ) de um vértice de origem s ∈ V para todos os demais atingíveis.

3.1. Busca em Largura 25

Para demonstrar isso, Cormen et al. (2012) examina algumas propriedades importantes

a seguir. Considere a distância de um caminho mínimo δ(s, v) de s a v como o número

mínimo de arestas/arcos necessários para percorrer esse caminho.

Lema 3.1.1. Seja G = (V, E ) um grafo orientado ou não-orientado e seja s ∈ V um vértice

arbitrário, então δ(s, v) ≤ δ(s, u) + 1 para qualquer aresta/arco (u, v) ∈ E .

Prova: Se u pode ser atingido a partir de s, então o mesmo ocorre com v. Desse modo,

o caminho mínimo de s para v não pode ser mais longo do que o caminho de s para u

seguido pela aresta/arco (u, v) e a desigualdade vale. Se u não pode ser alcançado por s,

então δ(s, u) = ∞, e a desigualdade é válida. 

Lema 3.1.2. Seja G = (V, E ) um grafo orientado ou não-orientado e suponha que G tenha

sido submetido ao algoritmo BFS (Algoritmo 3) partindo de um dado vértice de origem

s ∈ V . Ao parar, o algoritmo BFS satisfará D v ≥ δ(s, v)∀v ∈ V .

Prova: Utiliza-se a indução em relação ao número de operações de enfileiramento

(enqueue). A hipótese indutiva é D v ≥ δ(s, v)∀v ∈ V .

A base da indução é a situação imediatamente após s ser enfileirado na linha 7 do

Algoritmo 3. A hipótese indutiva se mantém válida nesse momento porque D s = 0 =

δ(s, s) e D v = ∞ ≥ δ(s, v)∀v ∈ V \{s}.

Para o passo da indução, considere um vértice v não-visitado (C v =false) que é

descoberto depois do último desenfileirar. Consideramos que o vértice desenfileirado

é u ∈ V . A hipótese da indução implica que D u ≥ δ(s, u). Pela atribuição da linha 13 e

pelo Lema 3.1.1, obtem-se

D v = D u + 1 ≥ δ(s, u) + 1 ≥ δ(s, v). (3.1)

Então, o vértice v é enfileirado e nunca será enfileirado novamente porque ele também

é marcado como visitado e as operações entre as linhas 12 e 15 são apenas executadas

para vértices não-visitados. Desse modo, o valor de D v nunca muda novamente e a

hipótese de indução é mantida. 

26 Capítulo 3. Buscas em Grafos

Lema 3.1.3. Suponha que durante a execução do algoritmo de busca em largura (Al-

goritmo 3) em um grafo G = (V, E ), a fila Q contenha os vértices (v 1 , v 2 , . . . , v r ), onde

v 1 é o início da fila e v r é o final da fila. Então, D v r ≤ D v 1 + 1 e D v i ≤ D v i +1 para todo

i ∈ {1, 2, . . . , r − 1}.

Prova: A prova é realizada por indução relacionada ao número de operações de fila.

Para a base da indução, imediatamente antes do laço de repetição (antes da linha 8),

têm-se apenas o vértice s na fila. O lema se mantém nessa condição.

Para o passo da indução, deve-se provar que o lema se mantém para depois do de-

senfileiramento quanto do enfileiramento de um vértice. Se o início v 1 é desenfileirado,

v 2 torna-se o início. Pela hipótese de indução, D v 1 ≤ D v 2 . Então D v r ≤ D v 1 + 1 ≤ D v 2 + 1.

Assim, o lema prossegue com v 2 no início.

Quando enfileira-se um vértice v (linha 15), ele se torna v r +1 . Nesse momento, já se

removeu da fila o vértice u cujo as adjacências estão sendo analisadas, e pela hipótese

de indução, o novo início v 1 deve ter D v 1 ≥ D u . Assim, D v r +1 = D v = D u + 1 ≤ D v 1 + 1.

Pela hipótese indutiva, têm-se D v r ≤ D u + 1, portanto D v r ≤ D u + 1 = D v = D v r +1 e o

lema se mantém quando um vértice é enfileirado. 

Corolário 3.1.4. Suponha que os vértices v i e v j sejam enfileirados durante a execução

do algoritmo de busca em largura (Algoritmo 3) e que v i seja enfileirado antes de v j .

Então, D v i ≤ D v j no momento que v j é enfileirado.

Prova: Imediata pelo Lema 3.1.3 e pela propriedade de que cada vértice recebe um

valor D finito no máximo uma vez durante a execução do algoritmo. 

Teorema 3.1.5. Seja G = (V, E ) um grafo orientado ou não-orientado, e suponha que o

algoritmo de busca em largura (Algoritmo 3) seja executado em G partindo de um dado

vértice s ∈ V . Então, durante sua execução, o algoritmo descobre todo o vértice v ∈ V

atingível por s. Ao findar sua execução, o algoritmo retornará a distância mínima entre s

e v ∈ V , então D v = δ(s, v)∀v ∈ V .

3.1. Busca em Largura 27

Prova: Por contradição, suponha que algum vértice receba um valor de distância não

igual à distância de seu caminho mínimo. Seja v um vértice (com δ(s, v)) que recebe tal

valor de distância D v incorreto. O vértice v não poderia ser s, pois o algoritmo define

D s = 0, o que estaria correto. Então deve-se encontrar um outro v 6= s. Pelo Lema 3.1.2,

D v ≥ δ(s, v) e portanto, temos D v > δ(s, v). O vértice v deve poder ser visitado a partir

de s, se não puder, δ(s, v) = ∞ ≥ D v . Seja u o vértice imediatamente anterior a v em um

caminho mínimo de s a v, de modo que δ(s, v) = δ(s, u) + 1. Como δ(s, u) < δ(s, v), e em

razão de selecionar-se v, têm-se D u = δ(s, u). Reunindo essas propriedades, obtém-se a

seguinte hipótese de contradição

D v > δ(s, v) = δ(s, u) + 1 = D u + 1. (3.2)

Considere o momento que o algoritmo opta por desenfileirar o vértice u de Q. Nesse

momento, o vértice v pode ter sido não-visitado, visitado e já foi removido da fila, ou

visitado e está na fila. O restante da prova analisa cada um desses casos:

• Se v é não-visitado (C v =false e lembrando que v é vizinho de u), então a operação

na linha 13 define D v = D u + 1, contradizendo o que é dito na Equação 3.2.

• Se v já foi visitado (C v =true) e foi removido da fila, pelo Corolário 3.1.4, têm-se

D v ≤ D u que também contradiz o que é dito na Equação 3.2.

• Se v já foi visitado e permanece na fila, quando v fora enfileirado w era o vértice

antecessor imediato no caminho até v, logo D v = D w + 1. Considere também

que w já foi desenfileirado. Porém, pelo Corolário 3.1.4, D w ≤ D u , então, temos

D v = D w + 1 ≤ D u + 1, contradizendo a Equação 3.2.

3.1.2.2 Árvores em Largura

O algoritmo de busca em largura (Algoritmo 3) criar uma árvore de busca em largura

à medida que efetua busca no grafo G = (V, E ). Também chamada de “subgrafo dos
28 Capítulo 3. Buscas em Grafos

predecessores”, uma árvore de busca em lagura pode ser definida como G π = (Vπ , E π ),

na qual Vπ = {v ∈ V : A v 6=null} ∪ {s} e E π = {(A v , π, v) : v ∈ Vπ \{s}}.

3.2 Busca em Profundidade

A busca em profundidade (Depth-First Search - DFS) realiza a visita a vértices cada vez

mais profundos/distantes de um vértice de origem s até que todos os vértices sejam

visitados. Parte-se a busca do vértice mais recentemente descoberto do qual ainda saem

arestas inexploradas. Depois que todas as arestas foram visitadas no mesmo caminho,

a busca retorna pelo mesmo caminho para passar por arestas inexploradas. Quando

não houver mais arestas inexploradas a busca em profundidade pára (CORMEN et al.,

2012).

O Algoritmo 4 apresenta um pseudo-código para a busca em profundidade. Note

que no lugar de usar uma fila, como na busca em largura (vide Algoritmo 3, utiliza-se

uma pilha. Os arranjos C v , T v , e A v ∀v ∈ V são respectivamente o arranjo de marcação

de visitados, do tempo de visita e do vértice antecessor à visita.

Cormen et al. (2012) afirma que é mais comum realizar a busca em profundidade de

várias fontes. Desse modo, seu livro reporta um algoritmo que sempre que um subgrafo

conexo é completamente buscado, parte-se de um outro vértice de origem não-visitado

ainda (um vértice não atingível por s).

3.2.1 Complexidade da Busca em Profundidade

Da mesma maneira que a complexidade da busca em largura, a busca em profundidade

possui complexidade O(|V | + |E |). As operações da pilha resultariam tempo O(|V |).

Muitos arestas/arcos incidem em vértices já visitados, então inclui-se na complexidade

de uma DFS a varredura de todas as adjacências, que demandaria Θ(|E |).

3.2. Busca em Profundidade 29

Algoritmo 4: Busca em profundidade.

Input :um grafo G = (V, E ), vértice de origem s ∈ V
// configurando todos os vértices
1 C v ← false ∀v ∈ V
2 T v ← ∞ ∀v ∈ V
3 A v ← null ∀v ∈ V
// configurando o vértice de origem
4 C s ← true
5 tempo ← 0
// preparando fila de visitas
6 S ← Pilha()
7 S.push(s)
// propagação das visitas
8 while S.empty() = false do
9 tempo ← tempo +1
10 u ← S.pop()
11 Tu ← tempo
12 foreach v ∈ N (u) do
13 if C v = false then
14 C v ← true
15 Av ← u
16 S.push(v)

17 return (C , T, A)
 CAPÍTULO 4
Caminhos e Ciclos

Este capítulo tem o objetivo de introduzir o conceito de caminhos e ciclos e apresen-

tar problemas importantes envolvendo-os. Dois problemas clássicos são definidos e

algoritmos são apresentados.

Antes de iniciar a abordagem de problemas e algoritmos, é importante entender o

que é um caminho e um ciclo, para estabelecer suas diferenças no contexto de grafos.

Um caminho1 é uma sequência de vértices 〈v 1 , v2, . . . v n 〉 conectados por uma aresta

ou arco. Gross e Yellen (2006) definem um caminho como um grafo com dois vértices

com grau 1 e os demais vértices com grau 2, formando uma estrutura linear. Um

ciclo (ou circuito)2 é uma cadeia fechada de vértices 〈v 1 , v 2 , . . . , v n , v 1 〉 onde cada par

consecutivo é conectado por uma aresta ou arco. É como um caminho com o fim e o

início conectados.

4.1 Caminhos e Ciclos Eulerianos

Dois problemas são apresentados a seguir. Eles estão relacionados a encontrar percursos

que passem por todas as arestas em grafos não-dirigidos. Há versões de problemas

envolvendo percursos Eulerianos para grafos dirigidos, mas não será o foco deste curso.
1
Em inglês, chamado de path.
2
Em inglês, chamado de cycle ou circuit.
32 Capítulo 4. Caminhos e Ciclos

O problema do Caminho (ou Trilha) Euleriano pode ser definido como: encontrar

um caminho p = 〈v 1 , v 2 , . . . , v k 〉 em um grafo não-orientado G = (V, E ), que passe por

todas as arestas de G, no qual nenhuma aresta é repetida e v 1 6= v k ou v 1 = v k .

O problema do Ciclo Euleriano pode ser definido como: encontrar um ciclo p =

〈v 1 , v 2 , . . . , v k , v 1 〉 em um grafo não-orientado G = (V, E ), que passe por todas as arestas

de G, no qual nenhuma aresta é repetida.

Em um problema de decisão relacionado a caminhos ou ciclos eulerianos, deseja-se

saber se há um caminho ou um ciclo euleriano no grafo de entrada. Um grafo é dito

Euleriano se possui um ciclo Euleriano. Se houver um caminho Euleriano, mas não um

ciclo Euleriano, diz-se que o grafo é semi-Euleriano.

4.1.0.1 Curiosidade

Os problemas de caminho e ciclo Euleriano surgiram com o conhecido problema das

Sete Pontes de Königsberg por Euler em 1736. O problema consistia em atravessar as

todas as sete pontes da cidade de Königsberg da Prussia (hoje Kaliningrado na Rússia)

sem repetí-las.

Observando um mapa antigo das sete pontes, você consegue determinar o caminho

Euleriano?

Figura 6 – Mapa das sete pontes de Königsberg na época de in Euler (GIUSCA, 2005).
4.1. Caminhos e Ciclos Eulerianos 33

4.1.1 Algoritmo de Hierholzer

O algoritmo de Hierholzer (Algoritmo 5) foi publicado em artigo datado de 1873, como

publicação póstuma a seu criador, Carl Hierholzer (falecido em 1871). Através desse

trabalho, Carl Hierholzer provou que o que Leonhard Euler tinha razão ao conjecturar

que

“Todo grafo conectado possui um Ciclo Euleriano se e somente se todos os seus

vértices possuem grau par.”3

. A partir dessa definição, uma dúvida pode permanecer: e sobre um grafo com vértice(s)

de grau zero, não teriam Ciclo Euleriano? A resposta mais adequada é teriam. Aceita-

mos que essa definição de conectado, no contexto de Ciclo Euleriano, desconsidera

os vértices de grau zero fora da única componente conectada do grafo. O algoritmo

3
Será que podemos estender uma propriedade semelhante para Caminhos Eulerianos?
34 Capítulo 4. Caminhos e Ciclos

proposto identifica o ciclo Euleriano em tempo O(|E |).

Algoritmo 5: Algoritmo de Hierholzer.
Input :um grafo não-orientado G = (V, E )

1 foreach e ∈ E do

2 C e ← false

3 v ← selecionar um v ∈ V arbitrariamente, que esteja conectado a uma aresta.

// “buscar Subci cl oEul er i ano ” invoca o Algoritmo 6

4 (r,C i cl o) ← buscar Subci cl oEul er i ano(G, v,C )

5 if r =false then

6 return (false,null)

7 else

8 if ∃e ∈ E : C e =false then

9 return (false,null)

10 else

11 return (true,C i cl o)
4.1. Caminhos e Ciclos Eulerianos 35

Algoritmo 6: Algoritmo de Auxiliar “busc ar Subci cl oEul er i ano”.

Input :um grafo não-orientado G = (V, E ),um vértice v ∈ V , o vetor de arestas visitadas

1 C i cl o ← (v)

2 t ←v

3 repeat

// Só prossegue se existir uma aresta não-visitada conectada a C i cl o .

4 if @u ∈ N (v) : C {u,v} =false then

5 return (false,null)

6 else

7 {v, u} ← selecionar uma aresta e ∈ E tal que C e =false

8 C {v,u} ← true

9 v ←u

// Adiciona o vértice v ao final do ciclo.

10 C i cl o ← C i cl o · (v)

11 until v = t

/* Para todo vértice x no C i cl o que tenha uma aresta adjacente não

visitada. */
© ª
12 foreach x ∈ u ∈ C i cl o : ∃{u, w} ∈ {e ∈ E : C e =false} do

13 (r,C i cl o 0 ) ← buscar Subci cl oEul er i ano(G, x,C )

14 if r =false then

15 return (false,null)

16 Assumindo que C i cl o = 〈v 1 , v 2 , . . . , x, . . . , v 1 〉 e C i cl o 0 = 〈x, u 1 , u 2 , . . . , u k , x〉, alterar

C i cl o para C i cl o = 〈v 1 , v 2 , . . . , x, u 1 , u 2 , . . . , u k , x, . . . , v 1 〉, ou seja, inserir o C i cl o 0 no

lugar da posição de x em C i cl o.

17 return (true,C i cl o)

Explique porque a complexidade de Algoritmo de Hierholzer é de O(|E |).

Lema 4.1.1. Seja G = (V, E ) um grafo não-dirigido no qual todas as arestas pertençam

à única componente conectada e todos os vértices possuem grau par, é sempre possível
36 Capítulo 4. Caminhos e Ciclos

encontrar obter um ciclo em G que não repita arestas.

Prova: A prova é realizada por contradição. Imagine que comecemos a criar um ciclo p

por um vértice arbitrário v 1 ∈ V , conectado a uma aresta em G. Chamaremos de aresta

marcada a que já foi colocada no ciclo e d v0 a quantidade de arestas conectadas a v que

ainda não estão marcadas.

Por contradição, tentamos demonstrar que não é possível obter um ciclo em G,

iremos tentar criar um caminho que nunca encontrará novamente v 1 . Ao iniciar por v 1 ,

selecionamos arbitrariamente um vértice adjacente, chamado aqui de u, e o adiciona-

mos a p. Desse modo, a aresta {v 1 , u} é considerada como marcada. Nesse momento,

d v0 1 e d u0 se tornam números ímpares. Como o grau de u é par e maior que 0, ele terá

alguma aresta não marcada que permitirá que o caminho continue a ser construído.

Repete-se o processo até que não seja mais possível encontrar arestas não marcadas,

adicionando um novo vértice ao caminho que esteja conectado ao último vértice adicio-

nado em p utilizando uma aresta não marcadas. Note que é impossível não retornar a v 1

e estabelecer um ciclo, pois todo vértice recém adicionado terá uma aresta não marcada

para adicionar alguém ao caminho, a não se que se tenha retornado a v 1 , portanto

formando um ciclo, o que é uma contradição. Dessa forma, a prova por contradição

está completa. 

Lema 4.1.2. Seja G = (V, E ) um grafo não-dirigido com dois ciclos p 1 e p 2 que não com-

partilham arestas, eles podem ser unidos para formar um único ciclo, caso compartilhem

um vértice.

Prova: A prova é dada por construção. Considere p 1 = 〈u 1 , u 2 , . . . , u 1 〉 e p 2 = 〈v 1 , v 2 , . . . , v 1 〉.

Para construir um único ciclo:

1. considere que o vértice x que seja comum aos dois ciclos;

2. conside p 1 = 〈u 1 , u 2 , . . . , x, . . . , u 1 〉 e p 2 = 〈v 1 , v 2 , . . . , x, . . . , v 1 〉;
4.1. Caminhos e Ciclos Eulerianos 37

3. formatar o ciclo p 2 para iniciar e começar em x, tornando-se desse modo p 2 =

〈x, . . . , v 1 , v 2 , . . . , x〉;

4. copiar p 1 para r , o ciclo resultante, desse modo r = 〈u 1 , u 2 , . . . , x, . . . , u 1 〉;

5. substituir o vértice x em r pelo ciclo na ordem em p 2 , obtendo p 1 = 〈u 1 , u 2 , . . . , x, . . . , v 1 , v 2 , . . . , x, . . . , u 1 〉.

Lema 4.1.3. Seja G = (V, E ) um grafo não-dirigido no qual todos os vértices possuem grau

par, remover as arestas que compõem qualquer ciclo em G, todos os vértices continuarão

com grau par.

Prova: A prova é dada por contradição. Considere o ciclo p = 〈v 1 , v 2 , . . . , v k , v 1 〉. Os

vértices que sofrerão redução de grau serão aqueles que pertencem ao ciclo, portanto,

por contradição, devemos supor que ao menos um vértice do ciclo terá grau ímpar. Isso

é impossível, pois ao remover as arestas que pertença ao ciclo, os vértices pertencentes

ao ciclo sofrerão sempre o decréscimo de dois em seus graus (um para aresta que entra

e outro para a que sai). 

Teorema 4.1.4. Um grafo não-orientado G = (V, E ) é (ou possui um ciclo) Euleriano se e

somente se G cada vértice tem um grau par e todas as arestas pertençam a uma única

componente conectada no grafo.

Prova: A prova será realizada por contradição. Considerando o Lema 4.1.1 há ao menos

um ciclo. Se houver mais de um ciclo, e se eles se conectam em vértices, é possível

converter esses ciclos em um apenas pelo Lema 4.1.2.

Então devemos imaginar arestas que não pertençam a um ciclo presente no grafo.

Ao remover os ciclos formados, ainda assim, teremos vértices com grau par pelo Lema

4.1.3. Essas arestas podem estar em uma única ou em várias componentes conectadas.

Sabe-se que essa ou essas componentes terão vértices de grau par e cada componente

poderá ter um ciclo (Lema 4.1.1). No caso de mais de uma componente conectada ter

sido gerada, significa que o ciclo removido conectava as componentes. Se cada uma
38 Capítulo 4. Caminhos e Ciclos

delas tiver um ciclo, então é possível obter um ciclo de cada uma (pelo Lema 4.1.2), logo

não sobrando arestas sem ciclo.

Analisando cada componente (ou a única que tenha sobra pela remoção), há de se

encontrar a aresta que não está no ciclo. No entanto, cada componente conectada pos-

sui um ciclo (Lema 4.1.1) e a remoção desse ciclo gerará componente ou componentes

com vértices de grau par (Lema 4.1.3) até que o grau seja igual a zero ou não haja mais

componentes. Desse modo, é impossível encontrar tal aresta e completa-se a prova. 

4.2 Caminhos e Ciclos Hamiltonianos

Ciclos ou caminhos Hamiltonianos são aqueles que percorrem todos os vértices de um

grafo apenas uma vez. Mais especificamente para um ciclo Hamiltoniano, o início e o

fim terminam no mesmo vértice. O nome Hamiltoniano vem de William Rowan Hamil-

ton, o inventor de um jogo que desafia a buscar um ciclo pelas arestas de dodecaedro

(figura tridimensional de 12 faces).

Um grafo é dito Hamiltoniano se possui um ciclo Hamiltoniano.

Há |V |! diferentes sequências de vértices que podem ser caminhos Hamiltonianos,

então, um algoritmo de força-bruta demanda muito tempo computacional. O problema

de decisão para encontrar um caminho ou ciclo Hamiltoniano é considerado N P -

Completo.

4.2.1 Caixeiro Viajante

Dado um grafo completo4 G = (V, E , w) no qual V é o conjunto de vértices, E é o

conjunto de arestas e w : E → R+ é a função dos pesos (ou custo ou distâncias), busca-se

pelo ciclo Hamiltoniano de menor soma total de peso (menor custo ou distância).

Um dos algoritmos mais eficientes para resolvê-lo é o de programação dinâmica

Held-Karp (ou Bellman–Held–Karp, no Algoritmo 7). No entanto, o mesmo demanda

4
Em um grafo completo, o conjunto de arestas é definido por E = V × V .
4.2. Caminhos e Ciclos Hamiltonianos 39

tempo computacional de O(2|V | |V |2 ).

O algoritmo de Bellman-Held-Karp é de programação dinâmica e considera que

“cada subcaminho de um caminho de distância mínima é mínimo”. Segue abaixo a

recorrência utilizada para a programação dinâmica do algoritmo. Ela tem o objetivo de

descobrir o valor do menor caminho que começa em 1 e temina em v passando por

todos os vértices que estão em S. Para isso, assumimos que 1, v ∉ S



w({1, v})
 para |S| = 0,
OP T (S, v) =

minu∈S,u6=1 {OP T (S − {u}, u) + w({u, v})} para n > 0.


Algoritmo 7: Algoritmo de Bellman-Held-Karp.

Input :um grafo G = (V, E = V × V, w)
1 for k ← 2 to |V | do
¡ ¢
2 C ({k}, k) ← w {1, k}
3 for s ← 2 to |V | − 1 do
© ª
4 foreach S ∈ x ⊆ {2, 3, . . . , |V |} : |x| = s do
5 foreach v ∈ S do
© ¡ ¢ª
6 C (S, v) ← minu6=v,u∈S C (S\{v}, u) + w {u, v}
© ¡ ¢ª
7 return minv∈V \{1} C ({2, 3, . . . , |V |}, v) + w {v, 1}

Execute o Algoritmo 7 sobre o grafo G = (V = {1, 2, 3, 4}, E = V × V, w), no qual

¡ ¢ ¡ ¢ ¡ ¢ ¡ ¢ ¡ ¢
w {1, 2} → 10, w {1, 3} → 15, w {1, 4} → 20, w {2, 3} → 35, w {2, 4} → 25 e
¡ ¢
w {3, 4} → 30.

A resposta deve ser 80.

 CAPÍTULO 5
Caminhos Mínimos

Em um problema de Caminho Mínimo, há um grafo ponderado orientado ou não G =

(V, E , w), onde V é o conjunto de vértices, E é o conjunto de arcos ou arestas, e w : E → R

é a função que representa o peso entre dois vértices (distância ou custo das arestas).

Para um caminho p = 〈v 1 , v 2 , . . . , v k 〉 seu peso é dado por w(p) = ki=2 w (v i −1 , v i )

P ¡ ¢

(CORMEN et al., 2012).

O peso de um caminho mínimo de u a v é dado por


 p
min{w(p) : u
 v}, se há um caminho de u para v ,
δ(u, v) = (5.1)

∞, caso contrário.


Há algumas variantes para os problemas de caminho mínimo (CORMEN et al.,

2012):

• Problema de caminhos mínimos de fonte única: dado um grafo ponderado G =

(V, E , w) e um vértice de origem s ∈ V , encontrar o caminho de custo δ(s, v) para

todo o v ∈ V ;

• Problema de caminhos mínimos para um destino:dado um grafo ponderado

G = (V, E , w), um vértice de destino t ∈ V , determinar o caminho de custo δ(v, t )

para todo o v ∈ V ;
42 Capítulo 5. Caminhos Mínimos

• Problema de caminhos mínimos para um par: dado um grafo ponderado G =

(V, E , w), um vértice de origem s ∈ V e um vértice de destino t , determinar o

caminho de custo δ(s, t );

• Problema de caminhos mínimos para todos os pares: dado um grafo ponderado

G = (V, E , w), encontrar o caminho de curso δ(u, v) para todo o par u, v ∈ V .

Pesos Negativos

Os problemas de caminho mínimo geralmente operam sem erros em grafos com pe-

sos negativos. Uma exceção a isso é quando há um ciclo com peso negativo. Nesse

caso, nunca haverá um peso definido, pois é sempre possível diminuir o peso total do

caminho percorrendo o ciclo mais uma vez.

Inicialização e Relaxamento

Os Algoritmos 8 e 9 são utilizados em diversos algoritmos de resolução de caminhos

mínimos. A estrutura de dados D é referente a estimativa de caminho que será obtida

ao longo da execução de um caminho mínimo para cada vértice v ∈ V . A estrutura de

dados A é utilizada para identificar o vértice anterior em cada caminho mínimo para
5.1. Propriedades de Caminhos Mínimos 43

um vértice v ∈ V .
Algoritmo 8: Inicialização de G.
Input :um grafo G = (V, E , w), um vértice de origem s ∈ V

// inicialização

1 D v ← ∞ ∀v ∈ V

2 A v ← null ∀v ∈ V

3 Ds ← 0

4 return (D, A)

Algoritmo 9: Relaxamento de v.
Input :um grafo G = (V, E , w)a , (u, v) ∈ E , A, D
¡ ¢
1 if D v > D u + w (u, v) then
¡ ¢
2 D v ← D u + w (u, v)

3 Av ← u

a
Para o caso de G ser não-dirigido, deve-se realizar o relaxamento em (u, v) e (v, u) para uma aresta
{u, v} ∈ E , ou seja, deve-se realizar o relaxamento nos dois sentidos.

5.1 Propriedades de Caminhos Mínimos

5.1.1 Propriedade de subcaminhos de caminhos mínimos o são

Lema 5.1.1. Dado um grafo ponderado G = (V, E , w), um caminho mínimo entre v 1 e v k

p = 〈v 1 , v 2 , . . . , v k 〉, suponha que, para quaisquer i e j , 1 ≤ i ≤ j ≤ k, todo o subcaminho

de p chamado de p i j = 〈v i , v i +1 , . . . , v j 〉 é um caminho mínimo de v i a v j .

p 1i pi j p jk
Prova: Se o caminho p for decomposto em v 1 vi vj v k , têm-se w(p) = w(p 0 j )+

w(p i j ) + w(p j k ). Suponha que exista um caminho p i0 j de v i a v j com peso w(p i0 j ) <
p 1i p i0 j p jk
w(p i j ). Então, v 1 vi vj v k é um caminho de v 1 a v k cujo o peso w(p) = w(p 0 j )+

w(p i0 j ) + w(p j k ) é menor do que w(p), o que contradiz a hipótese de que p seja um

caminho mínimo de v 1 a v k . 
44 Capítulo 5. Caminhos Mínimos

5.1.2 Propriedade de desigualdade triangular

Lema 5.1.2. Seja G = (V, E , w) um grafo ponderado e s ∈ V um vértice de origem, então

para todas as arcos/arestas (u, v) ∈ E têm-se

δ(s, v) ≤ δ(s, u) + w (u, v) .

¡ ¢
(5.2)

Prova: Suponha que p seja um caminho entre s e v. Então, p não tem peso maior do

que qualquer outro caminho de s a v. Especificamente, p não possui peso maior que o

caminho de s até o vértice u que utiliza a aresta/arco (u, v) para atingir o destino v. 

5.1.3 Propriedade de limite superior

Lema 5.1.3. Seja G = (V, E , w) um grafo ponderado dirigido ou não com a função de peso

w : E → R. Seja s ∈ V o vértice de origem, considera-se também o grafo G inicializado

(Algoritmo 8). Então, D v ≥ δ(s, v) para todo v ∈ V , e esse invariante é mantido para

qualquer sequência de etapas de relaxamentos em G (Algoritmo 9). Além disso, tão logo

D v alcance seu limite inferior δ(s, v), nunca mais se altera.

Prova: Prova-se que o invariante D v ≥ δ(s, v) para todo o vértice v ∈ V por indução em

relação ao número de etapas de relaxamento.

Para a base da indução, D v ≥ δ(s, v) é verdadeiro após a inicialização (Algoritmo 8),

pois esse procedimento define que D v = ∞ para todo v ∈ V \{s}, ou seja, D v ≥ δ(s, v)

mesmo que v seja inatingível em um caminho mínimo a partir de s. Nesse momento

D s = 0 ≥ δ(s, s), observando que δ(s, s) = ∞ caso s participa de um ciclo negativo.

Para o passo da indução, considere o relaxamento de uma aresta/arco (u, v). Pela

hipótese de indução, D x ≥ δ(s, x) para todo o x ∈ V antes do relaxamento. O único valor

5.1. Propriedades de Caminhos Mínimos 45

de D que pode mudar é D v . Se ele mudar, têm-se

¡ ¢
D v = D u + w (u, v)

≥ δ(s, u) + w (u, v) (pela hipótese da indução)

¡ ¢
(5.3)
≥ δ(s, v) (pela desigualdade triangular,

Lema 5.1.2)

e, portanto o invariante é mantido.

Para demonstrar que D v não se altera depois que D v = δ(s, v), por ter alcaçado seu

limite inferior, D v não pode diminuir porque D v ≥ δ(s, v) e não pode aumentar porque

o relaxamento não aumenta valores de D. 

5.1.4 Propriedade de inexistência de caminho

Corolário 5.1.4. Supõe-se que, em um grafo G = (V, E , w) ponderado dirigido ou não,

nenhum caminho conecte o vértice de origem s ∈ V a um vértice v ∈ V . Então, depois

que o grafo G é inicializado (Algoritmo 8), temos D v = δ(s, v) = ∞ e essa desigualdade

é mantida como um invariante para qualquer sequência de etapas de relaxamento

(Algoritmo 9) nas arestas de G;

Prova: Pela propriedade de limite superior (Lema 5.1.3), têm-se sempre ∞ = δ(s, v) ≤

D v , portanto D v = ∞ = δ(s, v). 

5.1.5 Propriedade de convergência

Lema 5.1.5. Seja G = (V, E , w) um grafo ponderado dirigido ou não, s ∈ V um vértice de

origem e s u → v um caminho mínimo de s a v em G. Suponha que G seja inicializado

(Algoritmo 8) e depois uma sequência de etapas de relaxamento (Algoritmo 9) é executado

para todas as arestas/arcos de G. Se D u = δ(s, u) em qualquer tempo anterior da chamada,

então D u = δ(s, u) igual em toda a chamada.

46 Capítulo 5. Caminhos Mínimos

Prova: Pela propriedade do limite superior (Lema 5.1.3), se D u = δ(s, u) em algum

momento antes do relaxamento da aresta/arco (u, v), então essa igualdade se mantém

válida a partir de sua definição. Em particular, após o relaxamento (Algoritmo 9) da

aresta/arco (u, v), têm-se:

¡ ¢
D v ≤ D u + w (u, v) pelo Corolário 5.1.4)

= δ(s, u) + w (u, v) (5.4)

¡ ¢

= δ(s, v) pelo Lema 5.1.1.)

Pela propriedade do limite superior (Lema 5.1.3) D v ≥ δ(s, v), da qual concluímos

que D v = δ(s, v), e essa igualdade é mantida daí em diante. 

5.1.6 Propriedade de relaxamento de caminho

Lema 5.1.6. Seja G = (V, E , w) um grafo ponderado dirigido ou não e s ∈ V um vértice

de origem. Considere qualquer caminho mínimo p = 〈v 1 , v 2 , . . . v k 〉 de s = v 1 a v k . Se G

é inicializado (Algoritmo 8) e depois ocorre uma sequência de etapas de relaxamento

(Algoritmo 9) que inclui, pela ordem, relaxar as arestas/arcos (v 1 , v 2 ), (v 2 , v 3 ), . . . (v k−1 , v k ),

então D k = δ(s, v k ) depois desses relaxamentos e todas as vezes daí em diante. Essa

propriedade se mantém válida, não importa quais outros relaxamentos forem realizados.

Prova: Esta prova é realizada por indução, na qual têm-se D v i = δ(s, v i ) depois que o

i -ésimo aresta/arco do caminho p é relaxado.

Para a base, i = 1 antes que quaisquer arestas/arcos em p sejam relaxados. Têm-se

D v 1 = D s = 0 = δ(s, s) pela inicialização. Pela propriedade do limite superior (Lema

5.1.3) o valor D s nunca se altera depois da inicialização.

Pelo passo da indução, supõe-se que v i −1 = δ(s, v i −1 ) e examina-se o que acontece

quando se relaxa a aresta (v i −1 , v i ). Pela propriedade de convergência (Lema 5.1.5),

após o relaxamento dessa aresta, têm-se D v = δ(s, v i ) e essa igualdade é mantida todas

as vezes depois disso. 

5.1. Propriedades de Caminhos Mínimos 47

5.1.7 Propriedade de relaxamento e árvores de caminho mínimo

Lema 5.1.7. Seja G = (V, E , w) um grafo ponderado dirigido ou não e si nV um vértice de

origem, suponha que G não possua um ciclo de peso negativo que possa ser atingido por

s. Então, depois que o grafo G é inicializado (Algoritmo 8), o subgrafo dos predecessores

G π = (Vπ , E π ) forma uma árvore enraizada em s, e qualquer sequência de etapas de

relaxamento em arestas em G (Algoritmo 9) mantém essa propriedade invariante.

Prova: Inicialmentem o único vértice em G π é o vértice s, e o lema é trivialmente ver-

dade. Considere um subgrafo dos predecessores G π que surja depois de uma sequência

de etapas de relavamento.

Primeiro, prova-se que o subgrafo é acíclico. Suponha por contradição que alguma

etapa de relaxamento cria um ciclo no grafo G π . Seja c = 〈v 1 , v 2 , . . . , v k 〉 o ciclo onde

v 1 = v k . Então, A v i = v i −1 para i = 1, 2, . . . , k e, sem prejuízo de generalidade, pode-se

supor que o relaxamento de arestas (v k−1 , v k ) criou o ciclo em G π . Afirma-se que todos

os vértices do ciclo c podem ser atingidos por s, pois cada um tem um predecessor não

nulo (null). Portanto, uma estimativa de caminho mínimo fora atribuída a cada vértice

em c quando um valor atribuídoo à A v não foi igual a null. Pela propriedade do limite

superior (Lema 5.1.3), cada vértice no ciclo c tem um peso de caminho mínimo infinito,

o que implica que ele pode ser atingido por s.

Examina-se as estimativas de caminhos mínimos em c imediatamente antes de cha-

mar o procedimento de relaxamento (Algoritmo 9) passando os parâmetros G, (v k−1 , v k ), A, D

e mostra-se que c é um ciclo de peso negativo, contradizendo a hipótese que G não

possui um ciclo negativo que possa ser atingido por s. Imediatamente antes da cha-

mada, têm0se A v i = v i −1 para i = 2, 3, . . . , k − 1. Assim, para i = 2, 3, . . . , k − 1, a última

¡ ¢
atualização para D v i foi realizada pela atribuição D v i ← D v i −1 + w (v i −1 , v i ) . Se D v i −1

mudou desde então, ela diminuiu. Por essa razão, imediatamente antes da chamada de

relaxamento, têm-se

¡ ¢
D v i ≥ D v i −1 + w (v i −1 , v i ) ∀i ∈ {2, 3, . . . , k − 1} (5.5)
48 Capítulo 5. Caminhos Mínimos

Como A k é alterado pela chamada, imediatamente antes têm-se também a desi-

gualdade estrita
¡ ¢
D v k > D v k−1 + w (v k−1 , v k ) . (5.6)

Somando essa desigualdade estrita com as k − 1 desigualdades (Equação (5.5)),

obtêm-se a soma das estimativas dos caminhos mínimos em torno do ciclo c:

k
X k ³
X ¡ k
¢´ X k
X ¡ ¢
D vi > D v i −1 + w (v i −1 , v i ) = D v i −1 + w (v i −1 , v i ) . (5.7)
i =2 i =2 i =2 i =2

Mas,
k
X k
X
D vi = D v i −1 , (5.8)
i =2 i =2

já que cada vértice no ciclo c aparece exatamente uma vez em cada somatório. Esa

desigualdade implica
k
X ¡ ¢
0> w (v i −1 , v i ) . (5.9)
i =2

Assim a soma dos pesos no ciclo c é negativa, o que dá acontradição desejada.

Agora, provamos que G π é acíclico. Para mostrar que ele forma uma árvore enraizada

em s, basta provar que há um único caminho simples de s a v em G π para cada v ∈ Vπ .

Primeiro, deve-se mostrar que existe um caminho de s a cada vértice em v ∈ Vπ . Os

vértices em Vπ são os que têm os valores A não null, e o vértice s. Aqui a ideia é provar a

indução que existe em um caminho de s para todos os vértices em Vπ .

Para concluir a prova do lema, deve-se mostrar agora que, para qualquer vértice v ∈

Vπ , o grafo G π contém no máximo um caminho simples de s a v. Suponha o contrário:

que existam dois caminhos simples de s a algum outro vértice p 1 〈s u x→z v,

e p 2 〈s u y→z v onde x 6= y. Mas então A z = x e A z = y o que implica uma

contradição, pois x = y. Conclui-se que G π contém um caminho simples único de s a v

e G π forma uma árvore enraizada em s. 

5.1.8 Propriedade de subgrafo dos predecessores

Lema 5.1.8. Seja G = (V, E , w) um grafo ponderado orientado ou não e um vértice de

origem s ∈ V . Suponha que G não possua um ciclo de peso negativo que possa ser atingido
5.1. Propriedades de Caminhos Mínimos 49

por s. Chama-se de inicialização o procedimento do inicializado Algoritmo 8 e depois

executar qualquer sequência de etapas de relaxamento de arestas de G (Algoritmo 9) que

produza D v = δ(s, v) para todo v ∈ V . Então, o subgrafo predecessor G π (Vπ , E π ) é uma

árvore de caminhos mínimos com uma raiz em s.

Prova: Para ilustrar a primeira propriedade, deve-se mostrar Vπ é o conjunto de vértices

atingidos por s. Por definição, um peso de caminho mínimo δ(s, v) é finito sse v pode ser

alcançado por s. Isso implica que os vértices atingidos por s possuem peso de caminho

finito. Porém, um vértice v ∈ V \{s} recebeu um valor finito para D v sse A v 6=null. Assim,

os vértices em Vπ são exatamente aqueles que podem ser alcançados por s.

O Lema 5.1.7 define que após a inicialização, G π possui raiz em s e assim permanece

mesmo depois de sucessivas etapas de relaxamento.

Agora, prova-se que para todo vértice em v ∈ Vπ , o único caminho simples em

G π de s a v é o caminho mínimo de s a v em G. Seja p = 〈v 1 , v 2 , . . . v k 〉, onde v 1 = s

e v k = v. Para i = 2, 3, . . . , k, temos D v = δ(s, v i ) e também D v ≥ D v i −1 + w (v i −1 , v i ) ,

¡ ¢

do que concluímos w (v i −1 , v i ) ≤ δ(s, v i ) − δ(s, v i −1 ). A soma dos pesos ao longo de p

¡ ¢

produz

k
X ¡ ¢
w(p) = w (v i −1 , v i )
i =2
k
δ(s, v i ) − δ(s, v i −1 )
X
≤
i =2 (5.10)

= δ(s, v k ) − δ(s, v 0 )

= δ(s, v k )

Assim w(p) ≤ δ(s, v k ). Visto que δ(s, v k ) é um limite inferior para o peso de qualquer

caminho de s a v k , conclui-se que w(p) = δ(s, v k ). Deste modo, p é um caminho mínimo

de s a v = v k .


50 Capítulo 5. Caminhos Mínimos

5.2 Bellman-Ford

O algoritmo de Bellman-Ford resolve o problema de caminhos minimos de uma única

fonte. Um pseudo-código está representado no Algoritmo 10. Como entrada para o

algoritmo deve-se determinar um grafo ponderado orientado ou não G = (V, E , w),

onde V é o conjunto de vértices, E o conjunto de arestas/arcos e w : E → R, e um vértice

de origem s ∈ V . O algoritmo devolve um valor booleano false quando foi encontrado

um ciclo de peso negativo em G. Caso contrário, retorna true, o antecessor de cada

vértice v no caminho mínimo em A v e a peso δ(s, v) em D v .

O algoritmo vai progressivamente diminuindo a estimativa de peso do caminho de

s a v ∈ V até que se obtenha o caminho mínimo e D v = δ(s, v) para todo v ∈ V .

Algoritmo 10: Algoritmo de Bellman-Ford.

Input :um grafo G = (V, E , w), um vértice de origem s ∈ V

// inicialização

1 D v ← ∞ ∀v ∈ V

2 A v ← null ∀v ∈ V

3 Ds ← 0

4 for i ← 1 to |V | − 1 do

5 foreach (u, v) ∈ E do

// relaxamento
¡ ¢
6 if D v > D u + w (u, v) then
¡ ¢
7 D v ← D u + w (u, v)

8 Av ← u

9 foreach (u, v) ∈ E do
¡ ¢
10 if D v > D u + w (u, v) then

11 return (false,null,null)

12 return (true, D, A)
5.2. Bellman-Ford 51

5.2.1 Complexidade de Bellman-Ford

Quanto a complexidade computacional em tempo computacional de Bellman-Ford,

observando as primeiras instruções, têm-se a inicialização que demanda Θ(|V |) pois

as estruturas são inicializadas para cada vértice. A partir do primeiro conjunto de

laços de repetição, há o laço mais externo que repete |V | − 1 vezes. Para cada repetição

desse laço, passa-se por cada aresta em E , logo esse primeiro conjunto de laços dita

(|V | − 1)|E | execuções da comparação na linha 6. O último laço de repetição, faz ao

máximo |E | verificações da comparação na linha 10. Então, o algoritmo de Bellman-

Ford é executado no tempo computacional de O(|V ||E |).

5.2.2 Corretude de Bellman-Ford

Lema 5.2.1. Seja G = (V, E , w) um grafo ponderado e um vértice de origem s ∈ V , su-

ponha que G não possua nenhum ciclo de peso negativo que possa ser alcançado por

s. Então, depois de executar as |V | − 1 iterações nas linhas 4 a 8 com o algoritmo de

Bellman-Ford (Algoritmo 10), têm-se D v = δ(s, v) para todo v ∈ V .

Prova: Prova-se o esse lema através da propriedade de relaxamento de caminho (Lema

5.1.6). Considera-se que qualquer vértice v possa ser atingido por s e seja p = 〈v 1 , v 2 , . . . , v k 〉

um caminho mínimo de s a v, no qual v 1 = s e v k = v. Como caminhos mínimos são

simples, p tem no máximo |V | − 1 arestas/arcos, sendo k ≤ |V | − 1. Cada uma das |V | − 1

iterações do laço da linha 4 relaxa todas as |E | arestas/arcos. Entre as arestas relaxa-

das na i -ésima iteração, para i = 1, 2, . . . k, está (v i −1 , v i ). Então, pela propriedade de

relaxamento de caminho D v = D v k = δ(s, v k ) = δ(s, v). 

Corolário 5.2.2. Seja G = (V, E , w) um grafo ponderado dirigido ou não e s ∈ V o vértice

de origem, supõe-se que G não tenha nenhum ciclo negativo que possa ser atingido

por s. Então, para cada vértice v ∈ V , existe um caminho de s a v sse o algoritmo de

Bellman-Ford termina com D v < ∞ quando é executado para G e s.

52 Capítulo 5. Caminhos Mínimos

Prova: Se v ∈ V pode ser atingido por s, então existe uma aresta/arco (u, v). Então,

δ(s, v) < ∞ através da propriedade de convergência (Lema 5.1.5). 

Teorema 5.2.3. Considera-se o algoritmo de Bellman-Ford (Algoritmo 10) executado

para um grafo G = (V, E , w) e o vértice de origem s ∈ V . Se G não contém nenhum ciclo de

custo negativo, que pode ser alcançado de s, então o algoritmo retorna true, D v = δ(s, v)

para todo v ∈ V e o subgrafo predecessor G π é uma árvore de caminhos mínimos com

raiz em s. Se G contém um ciclo de peso negativo que possa ser atingido por s, então o

algoritmo retorna false.

Prova: Suponha que o grafo G não tenha um ciclo de peso negativo atingível por s.

Primeiro, prova-se que D v = δ(s, v) para todo v ∈ V . Se o vértice v pode ser atingido

por s, então o Lema 5.2.1 prova essa afirmação. Se v não pode ser atingido por s, a

prova decorre da propriedade da inexistência de caminho (Corolário 5.1.4). Portanto,

a afirmação está provada. A propriedade de subgrafo dos predecessores (Lema 5.1.8)

juntamente com essa última afirmação implica que G π é uma árvore de caminhos

mínimos. Agora, usa-se a afirmação para mostrar que Bellman-Ford retorna true. No

término, têm-se para todas as arestas/arcos (u, v) ∈ E ,

D v = δ(s, v)

≤ δ(s, u) + w (u, v) (pela desigualdade triangular – Lema 5.1.2) (5.11)

¡ ¢

¡ ¢
= D u + w (u, v) ,

e, assim, nenhum dos testes na linha 10 serão verdadeiros e Bellamn-Ford retorna false.

Então, ele retorna true.

Agora, suponha que o grafo G contenha o ciclo de peso negativo que possa ser

atingido por s. Seja esse ciclo c = 〈v 1 , v 2 , . . . , v k 〉, onde v 1 = v k . Então,

k
X ¡ ¢
w (v i −1 , v i ) < 0 (5.12)
i =2
5.3. Dijkstra 53

Considere, por contradição, que o algoritmo de Bellman-Ford retorna true. Assim,

¡ ¢
D v i ≤ D v i −1 + w (v i −1 , v i ) para i = 2, 3, . . . , k. Somando as desigualdades em torno do

ciclo c têm-se

k
X k
X ¡ ¢ Xk k
X ¡ ¢
D vi ≤ D v i −1 + w (v i −1 , v i ) = D v i −1 + w (v i −1 , v i ) . (5.13)
i =2 i =2 i =2 i =2

Como v 0 = v k , cada vértice em c aparece exatamente apenas uma vez em cada um

dos somatórios, portanto

k
X k
X
D vi = D v i −1 (5.14)
i =2 i =2

Além disso, pelo Corolário 5.2.2, D v i é finito para i = 2, 3, . . . , k. Assim,

k
X ¡ ¢
0≤ w (v i −1 , v i ) , (5.15)
i =2

o que contradiz a desigualdade da Equação (5.12). Conclui-se que o algoritmo de

Bellman-Ford retorna true se o grafo G não contém nenhum ciclo negativo que possa

ser alcançado a partir da fonte e false caso contrário.

5.3 Dijkstra

O algoritmo de Dijkstra resolve o problema de encontrar um problema de caminho

mínimos de fonte única em um grafo G = (V, E , w) ponderados dirigidos ou não. Para

esse algoritmo, as arestas/arcos não devem ter pesos negativos. Então, a função de

pesos é redefinida como w : E → R+

∗ . A vantagem está em o algoritmo de Dijkstra ser

mais eficiente que o do Bellman-Ford se for utilizada uma estrutura de dados adequada.

O algoritmo repetidamente seleciona o vértice de menor custo estimado até então.

Quando esse vértice é selecionado, ele não é mais atualizado e sua distância é propagada
54 Capítulo 5. Caminhos Mínimos

para suas adjacências. A estrutura de dados C é utilizada no pseudo-código abaixo para

definir se um vértice foi visitado (contém true) ou não (contém false).

Algoritmo 11: Algoritmo de Dijkstra.
Input :um grafo G = (V, E , w : E → R+
∗ ), um vértice de origem s ∈ V

1 D v ← ∞ ∀v ∈ V

2 A v ← null ∀v ∈ V

3 C v ← false ∀v ∈ V

4 Ds ← 0

5 while ∃v ∈ V (C v = false) do

6 u ← arg minv∈V {D v |C v =false}

7 C u ← true

8 foreach v ∈ N (u) : C v =false do

¡ ¢
9 if D v > D u + w (u, v) then
¡ ¢
10 D v ← D u + w (u, v)

11 Av ← u

12 return (D, A)

5.3.1 Complexidade de Dijkstra

Se o algoritmo de Dijkstra manter uma fila de prioridades mínimas para mapear a

distância estimada no lugar de D, o algoritmo torna-se mais eficiente que o Bellman-

Ford. Seria utilizada uma operação do tipo “EXTRACT-MIN” no lugar da que está na

linha 6, para encontrar o vértice com a menor distância. Ao extraí-lo da estrutura de

prioridade, não mais seria necessário. Poderia-se gravar sua distância mínima em uma

estrutura auxiliar e não mais utilizar a estrutura de visitas C . Ao atualizar as distâncias,

poderia-se utilizar a operação de “DECREASE-KEY” da fila de prioridades no lugar da

operação da linha 10.

Para essa fila de prioridades, poderia se utilizar um Heap, como o Heap Binário,

no qual a implementação das operações supracitadas tem complexidade de tempo

computacional O(log2 n) para o “DECREASE-KEY” e O(log2 n) para o “EXTRACT-MIN”.

5.3. Dijkstra 55

Para essa aplicação, n = |V |. Utilizando essa estrutura de dados, sabe-se que no máximo

executa-se O(|E |) operações de “DECREASE-KEY” e O(|V |) operações de “EXTRACT-

¡ ¢
MIN”. Então a complexidade computacional seria O (|V | + |E |) log2 |V | . Com Heap

Fibonacci, consegue-se um tempo ainda melhor para a operação de “DECREASE-KEY”

(em tempo amortizado).

5.3.2 Corretude do Algoritmo de Dijkstra

Teorema 5.3.1. Dado um grafo G = (V, E , w : E → R+

∗ ) e um vértice de origem s ∈ V , o

algoritmo de Dijkstra termina com D v = δ(s, v) para todo v ∈ V .

Prova: Usa-se a seguinte invariante de laço: no início de cada iteração do laço das

linhas 5 – 11, D v = δ(s, v) para todo v o qual C v =true. Para demonstrar isso, diz-se que

D v = δ(s, v) no momento em que v é marcado como visitado, ou seja, na linha 7. Uma

vez demonstrado isso, recorre-se à propriedade do limite superior (Lema 5.1.3) para

demonstrar que a igualdade é válida em todos os momentos a partir desse.

Inicialização: Inicialmente, C u =false para todos u ∈ V . Então, a invariante é trivial-

mente verdadeiro.

Manutenção:

Por contradição, seja u o primeiro vértice para o qual D u 6= δ(s, u) quando C u torna-

se true. O vértice u não pode ser s, pois D s = δ(s, v) = 0 nesse momento. Como u 6= s,

deve existir algum caminho de s a u, senão D u = δ(s, u) = ∞ pela propriedade de

inexistência de caminho (Lema 5.1.4), o que contradiz D u 6= δ(s, u).

Assume-se então que haja um mínimo caminho p de s a u. Antes de C u se tornar

true, o caminho p conecta um vértice v o qual C v =true a u. Decompõe-se o caminho

p1 p2
p em s x→y u, no qual C x =true e C y =false. Afirma-se que D y = δ(s, y) no

momento que C u se torna true. Para provar essa afirmação, observa-se que C x =true.

Então, u foi escolhido como primeiro vértice para o qual D u 6= δ(s, u) quando C u se

torna true, tínha-se D x = δ(s, x) quando C x se tornou true. A aresta/arco (x, y) foi

relaxada naquele momento, e a afirmação decorre da propriedade de convergência

56 Capítulo 5. Caminhos Mínimos

(Lema 5.1.5). Agora, pode-se obter uma contradição para provar que D u = δ(s, u). Como

y aparece antes de u em um caminho mínimo de s a u e todos os pesos das arestas/arcos

são não-negativos, temos δ(s, y) ≤ δ(s, u) e assim,

D y = δ(s, y)

≤ δ(s, u) (5.16)

≤ D u ( pela propriedade do limite superior – Lema 5.1.3).

Porém, como C u =false e C y =false quando u foi escolhido na linha 6, tem-se

D u ≤ D y . Assim, as duas desigualdades da Equação (5.16) são de fato igualdades, o que

dá

D y = δ(s, y) = δ(s, u) = D u . (5.17)

Consequentemente, D u = δ(s, u), o que contradiz a escolha de u. Conclui-se que

D u = δ(s, u) quando C u se torna true e que essa igualdade é mantida até o término do

algoritmo.

Término:

No término, quanto para C v =true para todo v ∈ V , D v = δ(s, v) para todo v ∈ V . 

Corolário 5.3.2. Ao executar algoritmo de Dijkstra (Algoritmo 11) sobre o grafo G =

(V, E , w) ponderado orientado ou não, sem ciclos de peso negativo, para o vértice de

origem s ∈ V , o subgrafo dos predecessores G π será uma árvore de caminhos mínimos em

s.

Prova: Imediata pelo Teorema 5.3.1 e a propriedade do subgrafo dos predecessores

(Lema 5.1.8). 

5.4 Floyd-Warshall

O algoritmo de Floyd-Warshall (Algoritmo 12) encontra o caminho mínimo para um

grafo G(V, E , w) ponderado dirigido ou não para todos os pares de vértices. O algoritmo
5.4. Floyd-Warshall 57

suporta arestas/arcos de pesos negativos, mas não opera em grafos com ciclos de peso

negativo.

A função W (Equation (5.18)) define uma matriz de adjacências1 para o algoritmo

de Floyd-Warshall.



0, se u = v,






³ ´ 
W G(V, E , w) = (5.18)
¡ ¢
uv  w (u, v) , se u 6= v ∧ (u, v) ∈ E ,





∞,
 se u 6= v ∧ (u, v) ∉ E .

O algoritmo define um número de matrizes igual a |V |. Inicialmente, a matriz D (0) é

definida como a matriz de adjacência de G (linha 1). Depois repete-se o procedimento

de criar uma nova matriz e atualizar as distâncias de cada celula da nova matriz por |V |

vezes (linhas 2 a 6).

Algoritmo 12: Algoritmo de Floyd-Warshall.
Input :um grafo G = (V, E , w)
³ ´
1 D (0) ← W G

// Assumindo que os vértices estão rotulados de 1, 2, . . . , |V |

2 foreach k ∈ {1, 2, . . . , |V |} do
¡ (k) ¢
3 seja D (k) = d uv uma nova matriz |V | × |V |

4 foreach u ∈ V do

5 foreach v ∈ V do
n o
(k) (k−1) (k−1) (k−1)
6 d uv ← min d uv , d uk + d kv

7 return D (|V |)

5.4.1 Complexidade de Floyd-Warshall

O algoritmo Floyd-Warshall (Algoritmo 12) demanda |V |2 operações para executar a

linha 1. Como há o aninhamento de três laços limitados a |V | iterações na sequên-

1
Para grafos não-dirigidos, deve-se preencher a matriz resultante de W (G) nas coordenadas (u, v) e
(v, u)
58 Capítulo 5. Caminhos Mínimos

cia, a operação na linha 6 será executada |V |3 vezes. Logo, a complexidade de tempo

computacional de Floyd-Warshall é de Θ(|V |3 ).

Para este algoritmo, é interessante notar que foram utilizadas |V | matrizes de |V |

linhas e |V | colunas. Logo a complexidade de espaço para uma implementação que

utilize o pseudo-código do Algoritmo 12 utilizaria espaço computacional de Θ(|V |3 ).

No entanto, é possível reduzir essa complexidade de espaço computacional em Θ(|V |2 ).

Crie um pseudo-código para o Algoritmo 12 que demande complexidade de espaço

computacional Θ(|V |2 ).

5.4.2 Corretude de Floyd-Warshall

Prove que quando o Floyd-Warshall pára sobre uma entrada G = (V, E , w) ele retornará

as distâncias de caminhos mínimos para todo o par de vértice em V .

5.4.3 Construção de Caminhos Mínimos para Floyd-Warshall

O Algoritmo 13 além do peso dos caminhos mínimos em D, retorna a matriz dos

predecessores Π, ou seja, uma matriz que indica o vértice anterior no caminho de cada
5.4. Floyd-Warshall 59

coordenada u, v.

Algoritmo 13: Algoritmo de Floyd-Warshall com Matriz dos Predecessores.

Input :um grafo G = (V, E , w)
³ ´
1 D (0) ← W G

// Matriz dos predecessores

Π(0)
¡ (0) ¢
2 uv ← πuv uma nova matriz |V | × |V |

3 foreach u ∈ V do

4 foreach v ∈ V do

5 if (u, v) ∈ E then

6 π(0)
uv ← u

7 else

8 π(0)
uv ← null

9 foreach k ∈ V do
¡ (k) ¢
10 seja D (k) = d uv uma nova matriz |V | × |V |

seja Π(k) = π(k)

¡ ¢
11 uv uma nova matriz |V | × |V |

12 foreach u ∈ V do

13 foreach v ∈ V do

// atualizando matriz dos predecessores

(k−1) (k−1) (k−1)

14 if d uv > d uk + d kv then

15 π(k) (k−1)
uv ← πkv

16 else

17 π(k) (k−1)
uv ← πuv
n o
(k) (k−1) (k−1) (k−1)
18 d uv ← min d uv , d uk + d kv

19 return (D (|V |) , Π(|V |) )

A impressão de cada caminho pode ser realizada através do Algoritmo 14, que

recebe como entrada a matriz de predecessores gerada pelo Algoritmo 13, um vértice de

origem u e um de destino v. Ao terminar, o algoritmo terá impresso na tela o caminho

60 Capítulo 5. Caminhos Mínimos

mínimo de u a v.
Algoritmo 14: Print-Shortest-Path.
Input :a matriz dos predecessores Π, um vértice de origem u, um vértice de destino v

1 if u = v then

2 pr i nt (u)

3 else

4 if πuv = null then

5 pr i nt (“Caminho inexistente de u para v”)

6 else

7 P r i nt -Shor t est -P at h(Π, u, πuv )

8 pr i nt (v)
 CAPÍTULO 6
Problemas de Travessia

Em problemas de travessia, os estados possíveis podem ser representados como vértices

de um grafo e as transições de um estado para outro podem ser representados como

arestas ou arcos. Cada estado pode ser considerado como uma solução candidata a

solução esperada. Nesses problemas, espera-se que haja um estado inicial (situação

inicial) que possa atingir um estado final através de um caminho em sucessivos estados

adjacentes. Depois do grafo representar o problema, seus estados e transições, uma das

buscas estudadas aqui podem ser utilizadas para localizar um estado final.

Além da busca em largura e profundidade, há outros algoritmos que podem ser

utilizados para realizar uma “travessia”. Se há uma função que avalia quais vértices

adjacentes aos já visitados são melhores, há a Best First Search ou Busca do Melhor

Primeiro. Uma outra busca muito conhecida em problemas de localização de caminhos

(pathfinding) é o A*, que utiliza duas funções (objetivo e heurística) para determinar

de qual vértice a busca deve continuar. Há várias buscas utilizadas para travessia que

foram reportadas na literatura.

É importante ressaltar que muitos dos problemas de travessia podem ter uma quan-

tidade exponencial de estados em relação ao número de entidades que representem o

tamanho. Nesse caso, se não houver uma estratégia mais eficiente de busca, as buscas

em largura e profundidade podem demandar tempo exponencial determinístico, ou

62 Capítulo 6. Problemas de Travessia

seja, a execução pode demandar tempo mais elevado do que se pode aguardar para a

resposta, mesmo em entradas de tamanho pequeno.

Em muitos casos, não é necessário produzir um grafo. Nesse contexto, a travessia

ocorre em um grafo conceitual, onde os vértices visitados são construídos durante a

busca.

Alguns dos problemas aqui citados foram obtidos a partir de Mariani (2019).

Problemas de menor caminho são um tipo bem específico de problemas de traves-

sia.

6.1 Problema dos Canibais e Missionários

O problema dos canibais e missionários assume que três canibais e três missionários

devem cruzar um rio, mas para isso possuem apenas um barco. Cada canibal e cada

missionário sabe conduzir o barco. O barco suporta apenas dois indivíduos. Ao lado de

cada margem, não poderá permanecer um número maior de canibais do que de missio-

nários, pois há uma alta probabilidade de que os canibais devorem o(s) missionário(s)

(MARIANI, 2019).

Existem várias formas de representar este problema. No contexto de problemas de

travessia, deve-se pensar sobre a representação de cada estado, de modo que parte-se

de um estado com todos os indivíduos de um lado do rio e deseja-se passá-los para

outro lado. A representação de um estado que é utilizada nessa explicação é de uma

dupla (α, β), na qual α, β ∈ {1, 2, 3} e representam o número de canibais e missionários

respectivamente que permanecem no lado indesejado do rio. Enumerando todos os

6.1. Problema dos Canibais e Missionários 63

estados teria-se

©
(0, 0), (0, 1), (0, 2), (0, 3),

(1, 0), (1, 1), (1, 2), (1, 3),

(6.1)
(2, 0), (2, 1), (2, 2), (2, 3),
ª
(3, 0), (3, 1), (3, 2), (3, 3) .

São ao todo 16 estados. O estado (3, 3) representa que três canibais e três missionários

estão do lado indesejado do rio, ou seja, representa o estado inicial. O estado (0, 0)

representa o estado final (MARIANI, 2019).

Em nenhum momento, pode haver mais canibais que missionários em qualquer

uma das margens do rio. Então, o subconjunto de estados {(2, 1), (3, 2), (3, 1)} não podem

ser admitidos, pois haveria um número maior de canibais que o número de missioná-

rios na margem indesejada. Há outros estados inadmissíveis que devem considerar o

número maior de canibais na outra margem. Desse modo, considerando os demais

estados inadmissíveis {(2, 1), (3, 2), (3, 1), (1, 2), (0, 2), (0, 1)}. Todos os demais estados se-

riam os vértices do grafo que representará o problema. Então, o conjunto de vértices

V = {(0, 0), (0, 3), (1, 0), (1, 1), (1, 3), (2, 0), (2, 2), (2, 3), (3, 0), (3, 3)}.

O conjunto de arcos do grafo representaria então a transição possível entre os

estados. Considera-se então um arco (v 1 , v 2 ), no qual v 1 seria o estado de origem e v 2

seria o estado de destino. Considere também que v 1 = (α1 , β1 ) e v 2 = (α2 , β2 ). Para isso,

deve-se considerar três regras básicas do problema:

• α2 ≤ α1 : o número de canibais que voltam é menor ou igual aos que foram

enviados da margem indesejada;

• β2 ≤ β1 : o número de missionários que voltam é menor ou igual aos que foram

enviados da margem indesejada;

• 1 ≤ (α1 + β1 ) − (α2 + β2 ) ≤ 2: pode-se enviar no máximo dois indivíduos de um

barco para outro.

64 Capítulo 6. Problemas de Travessia

Com essas regras, o percurso a ser descoberto deve considerar. Seja i = 1, 2, 3 . . . a ordem

do passo para encontrar um caminho a partir do estado inicial, nos passos ímpares

deve-se seguir o arco em sua orientação original. Em passos pares, deve-se seguir um

arco em sua direção inversa (caminho de volta à margem indesejada).

6.1.1 Construção e Busca

Pode-se realizar a construção do grafo enquanto a busca ocorre. Para isso, considere

a formação de um grafo G = (V, A). (α, β, o) ∈ V , no qual o ∈ {d , e} é a margem do rio (e

para esquerda e d para direita). Considera-se as seguintes possibilidades de transição:

• 1 canibal;

• 1 missionário;

• 2 canibais;

• 2 missionários;

• 1 canibal e 1 missionário.

O conjunto de arcos A = {(v 1 , v 2 ) : v1 = (α1 , β1 , o 1 ), v 2 = (α2 , β2 , o 2 ), o 1 6= o 2 }. O algoritmo

de busca deve respeitar as restrições do problema original.

Defina um algoritmo de busca para encontrar um caminho entre os vértices (3, 3, e) e

(3, 3, d ).

6.2 Problemas dos Potes de Vinho

Considere que temos três potes com capacidades de 8, 5 e 3 litros, respectivamente,

os quais não possuem qualquer marcação. O maior deles esta completamente cheio

enquanto que os outros dois estão vazios. Estamos interessados em dividir o vinho

em duas porções iguais de 4 litros, tarefa esta que pode ser realizada por transvasos

sucessivos de um vaso no outro. Qual o menor número de transvasos necessários para

completar a divisão (NETTO, 2006; MARIANI, 2019)?

6.3. Problema da Fuga dos Ladrões 65

6.3 Problema da Fuga dos Ladrões

Uma quadrilha de 3 ladrões assalta um banco e foge com uma mala de dinheiro para

um aeroporto onde um avião pronto para decolar está à espera. O esconderijo é seguro,

mas a fuga é difícil porque o avião só comporta 170 kg. Só um dos ladrões sabe pilotar

e ele pesa 60 kg. O segundo, que é o guarda-costas do chefe, pesa 100 kg e o chefe

pesa 70 kg. O chefe teme que o piloto fuja com o dinheiro (que pesa 40 kg) se tiver

uma oportunidade. O piloto tem a mesma preocupação em relação ao chefe. Apenas o

guarda-costas merece a confiança de ambos. A quadrilha, no entanto, já elaborou um

plano de fuga capaz de satisfazer a todos. Qual é esse plano (MARIANI, 2019)?

6.4 Problema dos três maridos ciumentos

Três esposas e seus respectivos maridos desejam ir ao centro da cidade em um Corvette,

o qual comporta apenas duas pessoas. Como eles poderiam deslocar-se até o centro

considerando que nenhuma esposa deveria estar com um ou ambos os outros maridos

a menos que seu marido também esteja presente (MARIANI, 2019)?

6.5 Problema de Agrupamento de Indivíduos

Da Silva Mendes, De Santiago e Lamb (2018) definem um problema de agrupamento de

indivíduos através de uma representação em grafo realizando uma travessia através de

um algoritmo semelhante ao A*. No problema, os vértices representam particionamento

disjuntos de um conjunto de indivíduos. Seja I = {i 1 , i 2 , . . . , i n } o conjunto de indivíduos,

e R ⊆ I × I o conjunto de relacionamentos entre os indivíduos, precisa-se saber qual o

vértice que maximiza os relacionamentos entre indivíduos do mesmo grupo 1 .

O grafo considerado é G = (V, E ) no qual:

1
Para aqueles que quiserem mais detalhes sobre esse projeto, basta ler o artigo Da Silva Mendes, De
Santiago e Lamb (2018) ou conversar com o professor, coautor do trabalho
66 Capítulo 6. Problemas de Travessia

• V é o conjunto de soluções, na qual cada solução v ∈ V é uma partição disjunta

composta por todos os indivíduos de I ;

• E é o conjunto de arestas, na qual cada aresta conecta dois vértices (duas soluções)

ditos vizinhos. Para o trabalho, foi considerado que dois vértices são vizinhos se

apenas há um indivíduo em uma posição distinta.

 CAPÍTULO 7
Conectividade

7.1 Componentes Fortemente Conexas

Um grafo conexo é aquele no qual há um caminho entre todos os pares de vértices. É dita

uma componente fortemente conexa de um grafo dirigido não-ponderado G = (V, A) é

um conjunto máximo de vértices C ⊆ V , tal que para todo o par de vértices u, v em C

têm-se u vev u.

Um algoritmo para identificar as Componentes Fortemente Conexas é relatado por

Cormen et al. (2012) e apresentado aqui no Algoritmo 15. Nele, utiliza-se duas vezes

a busca em profundidade sugerida também por Cormen et al. (2012) (Algoritmos 16

(DFS) e 17 (DFS-Visit)). Primeiramente, faz-se a busca em profundidade para descobrir

os caminhos de todos os vértices para todos os outros. Depois, percorre-se os mesmos

caminhos em um grafo transposto (G T ). As árvores representadas como os antecessores

68 Capítulo 7. Conectividade

em A T trarão a resposta: cada árvore é uma componente fortemente conexa.

Algoritmo 15: Algoritmo de Componentes-Fortemente-Conexas
Input :um grafo dirigido não ponderado G = (V, A)

/* Chamar a DFS (do Algoritmo 16) para computar os tempos de término para

cada vértice */

1 (C , T, A 0 , F ) ← DFS(G)

/* Criar grafo transposto de G , chamado de G T . */

2 A T ← {}

3 foreach (u, v) ∈ A do

4 A T ← A T ∪ {(v, u)} /* Inverte-se todos os arcos para G T . */

5 G T ← (V, A T )

/* Chamar a DFS (do Algoritmo 16) alterado para que ele execute o laço da

linha 6, selecionando vértices em ordem decrescente de F */

6 (C T , T T , A 0T , F T ) ← DFS-adaptado(G T )

/* dar saída de cada árvore na floresta em profundidade em A T como uma

componente fortemente conexa. */

7 return A 0T

Algoritmo 16: DFS de Cormen et al. (2012).

Input :um grafo dirigido não ponderado G = (V, E )

// Configurando todos os vértices

1 C v ← false ∀v ∈ V

2 T v ← ∞ ∀v ∈ V

3 F v ← ∞ ∀v ∈ V

4 A v ← null ∀v ∈ V

// configurando o tempo de início

5 tempo ← 0

6 foreach u ∈ V do

7 if C u = false then

// DFS-Visit é especificado no Algoritmo 17

8 DFS-Visit(G, u, C , T , A, F , tempo)

9 return (C , T, A, F )
7.1. Componentes Fortemente Conexas 69

Algoritmo 17: DFS-Visit de Cormen et al. (2012).

Input :um grafo G = (V, E ), vértice de origem v ∈ V , e os vetores C , T , A e F , e uma
variável tempo ∈ Z+∗
1 C v ← true
2 tempo ← tempo +1
3 T v ← tempo
4 foreach u ∈ N + (v) do
5 if C u = false then
6 Au ← v
7 DFS-Visit(G, u, C , T , A, F , tempo)

8 tempo ← tempo +1
9 F v ← tempo

7.1.1 Complexidade do Algoritmo de Componentes Fortemente

Conexas

A complexidade de tempo computacional do Algoritmo 15 é dependente da comple-

xidade de tempo do algoritmo DFS de Cormen et al. (2012) (Algoritmos 16 (DFS) e

17 (DFS-Visit)). Para o algoritmo DFS, as instruções das linhas 1 a 4 demandam uma

quantidade de instruções igual a Θ(|V |). O laço entre as linhas 6 a 8 é executado por

um número de iterações dependente do número de vértices (Θ(|V |)). O procedimento

DFS-Visit é invocado apenas uma vez para cada vértice, graças ao vetor de visitados

C . Como nesse procedimento as adjacências de cada vértice são visitadas, há também

uma dependência do número de arcos saintes em cada vértice. Logo, a complexidade

computacional do Algoritmo 16, e consequentemente, a do algoritmo de Componentes

Fortemente Conexas, é Θ(|V | + |E |).

7.1.2 Corretude do Algoritmo de Componentes Fortemente Cone-

xas

7.1.2.1 Propriedades de Buscas em Profundidade

Teorema 7.1.1. Em qualquer busca em profundidade em um grafo dirigido ou não

G = (V, E ), para quaisquer dois vértices u e v, exatamente uma das três condições é
70 Capítulo 7. Conectividade

válida:

• Os intervalos [Tu , F u ] e [T v , F v ] são completamente disjuntos, e nem u nem v é

descendente do outro na floresta de profundidade.

• O intervalo [Tu , F u ] está contido inteiramente dentro do intervalo [T v , F v ] e u é um

descendente de v em uma árvore de profundidade.

• O intervalo [T v , F v ] está contido inteiramente dentro do intervalo [Tu , F u ] e v é um

descendente de u em uma árvore de profundidade.

Prova: A prova começará com o caso de Tu < T v . Para isso, consideramos dois subcasos:

T v < F u ou não. O primeiro subcaso ocorre quando T v < F u , portanto v foi descoberto

quando C u =true, ou seja, v foi descoberto mais recentemente que u, o que implica que

v é descendente de u. Ao findar a busca de u (linha 9 do Algoritmo 17), todas as arestas

de u foram exploradas, e consequentemente [T v , F v ] está completamente contido no

intervalo [Tu , F u ].

Ainda considerando Tu < T v , mas no subcaso de F u < T v , devido a T w < F w para

todo w ∈ V , Tu < F u < T v < F v , assim os intervalos [Tu , F u ] e [T v , F v ] são disjuntos.

Como os intervalos são disjuntos, nenhum vértice foi descoberto enquanto o outro

ainda não havia findado (linha 9 do Algoritmo 17), então nenhum é descendente do

outro.

O caso de T v < Tu é semelhante, com papéis de u e v invertidos no argumento

anterior. 

Corolário 7.1.2. O vértice v é um descendente adequado do vértice u na floresta em

profundidade para um grafo dirigido ou não G = (V, E ) sse Tu < T v < F v < F u .

Prova: Imediata pelo Teorema 7.1.1. 

Teorema 7.1.3. Em uma floresta em profundidade de um grafo dirigido ou não G = (V, E ),

o vértice v é um descendente do vértice u sse no momento Tu , em que uma busca descobre

u, há um caminho de u a v inteiramente de vértices w marcados com C w =false.

7.1. Componentes Fortemente Conexas 71

Prova: Se v = u, então o caminho de u a v não possui vértices além dele mesmo.

Agora, supõe-se que v seja um descendente próprio de u, que ainda tem C v =false

quando se define o valor de Tu . Pelo Corolário 7.1.2, Tu < T v e portanto C v =false no

tempo Tu . Visto que v pode ser descendente de u, todos os vértices w num caminho

simples de u até v tem C w =false.

Agora, supõe-se que haja um caminho de vértices w marcados com C w =false no

caminho de u a v no tempo Tu , mas v não se torna descendente de u na árvore de

profundidade. Sem prejuízo, considera-se que todo o vértice exceto v ao longo do

caminho se torne um descendente de u. Seja w o predecessor de v no camino, de

modo que w seja um descendente de u. Pelo Corolário 7.1.2, F w < F u . Como v tem

que ser descoberto depois de u ser descoberto, mas antes de w ser terminado, têm-se

Tu < T v < F w < F u . Então o Teorema 7.1.1 implica que o intervalo [T v , F v ] está contido

no intervalo [Tu , F u ]. Pelo Corolário 7.1.2, v deve ser descendente de u. 

7.1.2.2 Propriedades de Componentes Fortemente Conexas

Para as propriedades abaixo, considere que:

• d (S) = minv∈S {T v };

• f (S) = maxv∈S {F v };

Lema 7.1.4. Considerando C e C 0 componentes fortemente conexas distintas em um

grafo dirigido G = (V, A), seja u, v ∈ C e u 0 , v 0 ∈ C 0 e suponha que G tenha um caminho

u u 0 . Então, G não pode conter um caminho v 0 v.

Prova: Se G possui um caminho v 0 v, então contém os caminhos u u0 v0 e

v0 v u em G. Assim, u e v 0 podem ser visitados um a partir do outro, o que

contradiz a hipótese de que C e C 0 são componentes fortemente conexas distintas. 

Lema 7.1.5. Sejam C e C 0 componentes fortemente conexas distintas no grafo dirigido

G = (V, A). Suponha que haja um arco (u, v) ∈ A, no qual u ∈ C e v ∈ C 0 . Então, f (C ) >

f (C 0 ).
72 Capítulo 7. Conectividade

Prova: Considera-se dois casos dependendo qual das componentes fortemente conexas

(C ou C 0 ) têm o primeiro vértice descoberto na busca em profundidade.

Se d (C ) < d (C 0 ), seja x o primeiro vértice descoberto em C . No tempo T x , todos os

vértices em C e C 0 são não visitados (C v =false para todo v ∈ C ∪ C 0 ). Pode-se afirmar

então que há um caminho em x a w para qualquer w ∈ C 0 por causa do arco (u, v) ∈ A,

então x u→v w. Pelo Teorema 7.1.3, todos os vértices em C e C 0 se tornam

descendentes de x ma árvore de profundidade. Pelo Corolário 7.1.2, x tem o tempo de

término mais recente que qualquer um de seus descendentes, portanto F x = f (C ) >

f (C 0 );

Se d (C ) > d (C 0 ), seja y o primeiro vértice descoberto em C 0 . No tempo T y , todos

os vértices w em C 0 têm C w =false e G contém um caminho de y a cada vértice em

C 0 formado apenas por vértices z com C z =false. Pelo Teorema 7.1.3, todos os vértices

em C 0 se tornam descendentes de y na árvore de profundidade. Pelo Teorema 7.1.3,

F y = F (C 0 ). No tempo T y , todos os vértices w em C têm C w =false. Como existe um

arco (u, v) de C a C 0 , o Lema 7.1.4 implica que não pode haver um caminho de C 0 a C .

Consequentemente, nenhum vértice em C pode ser visitado por y. Portanto, no tempo

F y , todos os vértices w em C ainda tem C w =false. Assim, para qualquer vértice em

w ∈ C , têm-se F w > F y , o que implica que f (C ) > f (C 0 ). 

Corolário 7.1.6. Considerando C e C 0 componentes fortemente conexas distintas no

grafo dirigido G = (V, A), suponha que havia um arco (u, v) ∈ A T , no qual u ∈ C e v ∈ C 0 .

Então, f (C ) < f (C 0 ).

Prova: Como (u, v) ∈ A T , têm-se (v, u) ∈ A. Visto que as componentes fortemente cone-

xas em G T são as mesmas, o Lema 7.1.5 implica que f (C ) < f (C 0 ). 

Teorema 7.1.7. O Algoritmo 15 (de Componentes-Fortemente-Conexas) encontra corre-

tamente as componentes fortemente conexas de um grafo dirigido G = (V, A) dado como

sua entrada.
7.2. Ordenação Topológica 73

Prova: A prova é realizada por indução em relação ao número de árvores de busca

encontradas na busca em profundidade de G T na linha 6. Cada árvore forma uma

componente fortemente conexa.

A hipótese da indução é que as primeiras k árvores produzidas na linha 6 são

componentes fortemente conexas.

A base da indução, quando k = 0, é trivial.

No passo da indução, supõe-se que cada uma das k primeiras árvores de profundi-

dade produzidas na linha 6 é uma componente fortemente conexa, e consideramos a

(k + 1)-ésima árvore produzida. Seja u a raiz dessa árvore, e supondo que u esteja na

componente fortemente conexa C . Como resultado do modo que se escolhe a raiz da

árvore na linha 6, F u − f (C ) > f (C 0 ) para qualquer componente fortemente conexa C 0

exceto C que ainda tenha de ser visitada. Pela hipótese de indução, no momento da

busca de u na árvore de profundidade, todos os vértices w em C tem C w =false. Então,

pelo Teorema 7.1.3, todos os outros vértices de C são descendentes de u nessa árvore

de profundidade. Além disso, pela hipótese de indução e pelo Corolário 7.1.6, qualquer

arco em G T que saem de C devem ir até componentes fortemente conexas que já foram

visitadas. Assim, nenhum vértice em uma componente fortemente conexa, exceto C ,

será um descendente de u durante a busca em profundidade de G T . Portanto, os vérti-

ces da árvore de busca em profundidade em G T enraizada em u formam exatamente

uma componente fortemente conexa, o que conclui o passo de indução e a prova. 

7.2 Ordenação Topológica

A ordenação topológica no contexto de grafos, recebe um grafo acíclico dirigido G =

(V, A) e ordena linearmente todos os vértices tal que se existe um arco (u, v) ∈ A então

u aparece antes de v na ordenação. O algoritmo de Ordenação Topológica tem como

base uma busca em profundidade com a adição de uma lista O para inserir os vértices,

como pode ser visto no Algoritmo 19. Os vértices são inseridos sempre no início da lista
74 Capítulo 7. Conectividade

O logo que o algoritmo termina de visitá-lo (linha 10 do Algoritmo 19).

Algoritmo 18: DFS para Ordenação Topológica

Input :um grafo dirigido não ponderado G = (V, A)

// Configurando todos os vértices

1 C v ← false ∀v ∈ V

2 T v ← ∞ ∀v ∈ V

3 F v ← ∞ ∀v ∈ V

// configurando o tempo de início

4 tempo ← 0

// Criando lista com os vértices ordenados topologicamente

5 O ← ()

6 foreach u ∈ V do

7 if C u = false then

// DFS-Visit-OT é especificado no Algoritmo 19

8 DFS-Visit-OT(G, u, C , T , F , tempo, O)

9 return O

Algoritmo 19: DFS-Visit-OT.

Input :um grafo G = (V, E ), vértice de origem v ∈ V , e os vetores C , T e F , e uma

variável tempo ∈ Z+
∗ , uma lista O

1 C v ← true

2 tempo ← tempo +1

3 T v ← tempo

4 foreach u ∈ N + (v) do

5 if C u = false then

6 DFS-Visit-OT(G, u, C , T , F , tempo, O)

7 tempo ← tempo +1

8 F v ← tempo

// Adiciona o vértice v no início da lista O

9 O ← (v) ∪ O
7.2. Ordenação Topológica 75

7.2.1 Complexidade da Ordenação Topológica

Como a inserção no início de uma lista demanda tempo O(1), a complexidade de tempo

da Ordenação Topológica de um grafo acíclico é dependente da Busca em Profundidade.

Logo, a complexidade da Ordenação Topológica é O(|V | + |A|).

7.2.2 Corretude da Ordenação Topológica

Lema 7.2.1. Um grafo dirigido G = (V, A) é acíclico sse uma busca em profundidade de

G não produz nenhum arco de retorno.

Prova: Supondo que uma busca em profundidade produza um arco de retorno (u, v).

Então, o vértice v é um ascendente (ancestral) do vértice u na floresta em profundidade.

Assim, G contém um caminho de v a u, e o arco (u, v) completa o ciclo.

Supondo que G contenha um ciclo c, mostrou-se que uma busca em profundidade

de G produz um arco de retorno. Seja v o primeiro vértice a ser descoberto em c e seja

(u, v) o arco precedente em c. No tempo T v , os vértices em c formam um caminho

de vértices w com C w =false de v a u. Pelo Teorema 7.1.3, o vértice u se torna um

descendente de v na floresta em profundidade. Então (u, v) é um arco de retorno. 

Teorema 7.2.2. O Algoritmo 18 produz uma ordenação topológica de um grafo dirigido

acíclico G = (V, A) dado como entrada.

Prova: Supondo que o algoritmo seja executado sobre um determinado grafo dirigido

acíclico G = (V, A) para determinar os tempos de término para seus vértices. É suficiente

mostrar que, para qualquer par de vértices distintos u, v ∈ V , se G contém um arco de u

a v, então F v < F u . Considere qualquer arco (u, v) explorado no algoritmo. Quando esse

arco é explorado, v ainda não foi visitado (por DFS-Visit-OT), já que v é ascendente

(ancestral) de u e (u, v) é um arco de retorno, o que contradiz o Lema 7.2.1. Portanto, v

já deve ter C v =false ou já foi visitado. Se v tem C v =false, ele se torna um descendente

de u e F v < F u . Se v já foi visitado F v já foi definido, então F v < F u . Assim, para qualquer

arco (u, v) ∈ A, têm-se F v < F u . 

 CAPÍTULO 8
Árvores Geradoras Mínimas

Uma árvore geradora é um subconjunto acíclico (uma árvore) de todos os vértices

de um grafo. Dado um grafo ponderado G = (V, E , w), o problema de encontrar uma

arvore geradora mínima é aquele no qual busca-se encontrar uma árvore que conecte

todos os vértices do grafo G, tal que a soma dos pesos das arestas seja o menor possível.

Seja T uma árvore geradora, diz-se que o custo da árvore geradora de T é dado por
P ¡ ¢
w(T ) = {u,v}∈T w {u, v} .

Este capítulo apresenta dois métodos para encontrar árvores geradoras mínimas:

Kruskal e Prim. Esses dois algoritmos gulosos se baseiam em um método genérico

apresentado por Cormen et al. (2012). Dado um grafo não-dirigido e ponderado G =

(V, E , w), esse método genérico encontra uma árvore geradora mínima.

O Algoritmo 20 apresenta o método genérico para uma árvore geradora mínima

para G. O método se baseia na seguinte invariante de laço: “Antes de cada iteração, A é

um subconjunto de alguma árvore geradora mínima.”. A cada iteração, determina-se

uma aresta que pode ser adicionada a A sem violar a invariante de laço. A aresta segura
78 Capítulo 8. Árvores Geradoras Mínimas

é uma aresta que se adicionada a A mantém a invariante.

Algoritmo 20: Método Genérico de Cormen et al. (2012).
Input :um grafo G = (V, E , w)

1 A ← {}

2 while A não formar uma árvore geradora do

3 encontrar uma aresta {u, v} que seja segura para A

© ª
4 A ← A ∪ {u, v}

5 return A

8.1 Propriedades do Método Genérico

Teorema 8.1.1. Considere um grafo conexo não-dirigido ponderado G = (V, E , w). Seja

A ⊆ E uma árvore geradora mínima de G. Seja (S,V \S) qualquer conjunto de corte de G

que respeita A e seja {u, v} uma aresta leve1 que cruza (S,V \S), então {u, v} é uma aresta

segura para A.

Prova:

Seja T uma árvore geradora mínima que inclui A e suponha que T não contenha

a aresta leve {u, v}, pois se tiver, o processo termina. Constrói-se então outra árvore

geradora mínima T 0 que inclui A ∪ {u, v} usando uma técnica de recortar e colar,
© ª

mostrando assim que {u, v} é uma aresta segura para A.

Desde que u esteja em S e v em V \S, a aresta {u, v} forma um ciclo com as arestas

de caminho simples p de u a v em T . No mínimo uma aresta em T está no caminho

simples p e cruza o corte. Considere que {x, y} seja essa aresta de corte. A aresta {x, y}

não está em A, pois o corte respeita A. Desde que {x, y} está no único caminho de u a v

em T , removê-lo divide T em duas componentes. Adicionar {u, v} o reconecta a forma

de uma nova árvore geradora T 0 = T ∪ {u, v} \ {x, y} .

© ª © ª

Depois, mostra-se que T 0 é uma árvore geradora mínima. Desde que {u, v} é uma
¡ ¢
aresta leve atravessando (S, S\V ) e {x, y} também atravessa esse corte, w {u, v} ≤
1
Arestas de baixo custo/peso.
8.2. Algoritmo de Kruskal 79

¡ ¢
w {x, y} . Por essa razão:

w(T 0 ) = w(T ) + w {u, v} − w {x, y}

¡ ¢ ¡ ¢
(8.1)
0
≤ w(T ).

Mas, T é uma árvore geradora mínima, então w(T ) ≤ w(T 0 ). Desse modo, T 0 precisa ser

uma árvore geradora mínima também.

Falta mostrar que {u, v} é uma aresta segura para A. Têm-se A ⊆ T 0 , desde que A ⊆ T

e {x, y} ∉ A; então A ∪ {u, v} ⊆ T 0 . Consequentemente, desde que T 0 é uma árvore

© ª

geradora mínima, {u, v} é uma aresta segura para A. 

Corolário 8.1.2. Considere um grafo conectado não-dirigido e ponderado G = (V, E , w).

Seja A ⊆ E incluído em alguma árvore geradora mínima de G e seja C = (VC , EC ) um

componente conectado (uma árvore) na floresta G A = (V, A). Se {u, v} é uma aresta leve

conectando C a algum outro componente em G A , então {u, v} é uma aresta segura.

Prova: O corte (VC ,V \VC ) respeita A e {u, v} é uma aresta leve para esse corte. Por essa

razão, {u, v} é uma aresta segura para A (com base no Teorema 8.1.1). 

8.2 Algoritmo de Kruskal

O algoritmo de Kruskal inicia com |V | árvores (conjuntos de um vértice cada). Ele

encontra uma aresta segura e a adiciona a uma floresta, que está sendo montada,

conectando duas árvores na floresta. Essa aresta {u, v} é de peso mínimo. Suponha

que C 1 e C 2 sejam duas árvores conectadas por uma aresta {u, v}. Visto que essa deve

ser uma aresta leve, o Corolário 8.1.2 implica que {u, v} é uma aresta segura para C 1 .

Kruskal é um algoritmo guloso, pois ele adiciona à floresta uma aresta de menor peso

possível a cada iteração.

Um pseudo-código de Kruskal pode ser visualizado no Algoritmo 21. O algoritmo se

inicia definindo as |V | árvores desconectadas; cada uma contendo um vértice (linhas

80 Capítulo 8. Árvores Geradoras Mínimas

2 a 4). Então, cria-se uma lista das arestas E 0 ordenadas por peso (linha 5). Depois,

iterativamente, se tenta inserir uma aresta leve em duas árvores que contém nodos não

foram conectadas ainda (linhas 7 a 9). Quando a inserção ocorre, a estrutura de dados

S v que mapeia a árvore de cada vértice v é é atualizada. O procedimento se repete até

que todas as arestas tenham sido avaliadas no laço.

Algoritmo 21: Algoritmo de Kruskal.
Input :um grafo G = (V, E , w)

1 A ← {}

2 S ← vetor de |V | elementos vazios

3 foreach v ∈ V do

4 S v ← {v}

5 E 0 ← lista de arestas ordenadas por ordem crescente de peso

6 foreach {u, v} ∈ E 0 do

7 if S u 6= S v then

8 A ← A ∪ {{u, v}}

9 x ← Su ∪ S v

10 foreach y ∈ x do

11 Sy ← x

12 return A

8.2.1 Complexidade do Algoritmo de Kruskal

A complexidade de tempo do algoritmo de Kruskal depende da estrutura de dados utili-

zada para implementar o mapeamento das árvores de cada vértice, ou seja, da estrutura

S do Algoritmo 21. Para a implementação mais eficiente, verifique as operações de

conjuntos disjuntos no Capítulo 21 de Cormen et al. (2012). Sabe-se que para ordenar o

conjunto de arestas na linha 5, deve-se executar um algoritmo de ordenação. O mais

eficiente conhecido demanda tempo Θ(|E | log2 |E |).

Qual a estrutura de dado implementa a versão mais eficiente do Algoritmo de Kruskal?

8.3. Algoritmo de Prim 81

8.3 Algoritmo de Prim

O algoritmo de Prim é (também) um caso especial do método genérico apresentado no

Algoritmo 20. O algoritmo de Prim é semelhante ao algoritmo de Dijkstra, como pode

ser observado no pseudo-código do Algoritmo 22. As arestas no vetor A formam uma

árvore única. Essa árvore tem raízes em um vértice arbitrário r . Essa arbitrariedade

não gera problemas de corretudo no algoritmo, pois uma árvore geradora mínima deve

conter todos os vértices do grafo. A cada iteração, seleciona-se o vértice que é atingido

por uma aresta de custo mínimo (linha 7), sendo que o vértice selecionado adiciona

suas adjacências e pesos na estrutura de prioridade Q, que, futuramente, selecionará a

chave de menor custo, ou seja, o vértice conectado a árvore que possui o menor custo.

Pelo Corolário 8.1.2, esse comportamento adiciona-se apenas arestas seguras em A.

©
Antes de cada iteração do laço da linha 6, a árvore obtida é dada por {v, A v } : v ∈
ª
V \{r }\Q . Os vértices que já participam da solução final são V \Q. Além disso, para todo

v ∈ Q, se A v 6=null, então K v < ∞ e K v é o peso de uma resta leve {v, A v } que conecta o

vértice v a algum vértice que já está na árvore que está sendo construída. As linhas 7

e 8 indentificam um vértice u ∈ Q incidente em alguma aresta leve que cruza o corte

(V \Q,Q), exceto na primeira iteração. Ao remover u de Q, o mesmo é acrescido ao

conjunto V \Q na árvore, adicionando a aresta (u, A u ) na solução.

Se G é conexo, para montar a árvore geradora mínima a partir do vetor resultante A,

82 Capítulo 8. Árvores Geradoras Mínimas

© ª
deve-se criar o conjunto {v, A v } : v ∈ V \{r } .
Algoritmo 22: Algoritmo de Prim.
Input :um grafo G = (V, E , w)

1 r ← selecionar um vértice arbitrário em V

// Definindo o vetor dos antecessores A e uma chave para cada vértice K

2 A v ← null ∀v ∈ V

3 K v ← ∞ ∀v ∈ V

4 Kr ← 0

// Definindo a estrutura de prioridade de chave mínima Q

5 Q ← (V, K )

6 while Q 6= {} do

7 u ← arg minv∈Q {K v }

8 Q ← Q\{u}

9 foreach v ∈ N (u) do
¡ ¢
10 if v ∈ Q ∧ w {u, v} < K v then

11 Av ← u
¡ ¢
12 K v ← w {u, v}

13 return A

8.3.1 Complexidade do Algoritmo de Prim

Para implementar o algoritmo de Prim de maneira mais eficiente possível, deve-se

encontrar uma estrutura de prioridade que realize as operações de extração do valor

mínimo e da alteração das chave de maneira rápida.

Qual a complexidade em tempo computacional da versão mais eficiente do Algoritmo

de Prim?
 CAPÍTULO 9
Fluxo Máximo

O problema de fluxo máximo pode ser formalizado da seguinte forma: dado um grafo

dirigido e ponderado (rede residual) G = (V, A, c), um vértice s ∈ V de origem de fluxo e

um vértice de destino t ∈ V , deseja-se despachar um fluxo de s para t de acordo com as

capacidades dos arcos dadas por c no qual a soma total de fluxo que incide em t seja

máxima. Desse modo, o fluxo despachado em cada arco deve ser menor ou igual a sua

capacidade. O fluxo total que chega a um vértice v ∈ V − {s, t } deve ser o mesmo que

sai do vértice (sob pena de acúmulo de fluxo no vértice, que não tem reservatório para

fluxo).

Um exemplo de aplicação pode ser dado para um projeto de malha viária terrestre.

Imagine que G seja a malha de uma cidade nas quais os veículos entram em s e saiam

em t . Deseja-se despachar o máximo de veículos possíveis. Para isso, devemos respeitar

as capacidades de cada via (arcos). Exemplos de aplicação podem ser obtidos para

despacho de líquidos (água, esgoto) ou eletricidade.

9.1 Redes de Fluxo

Uma rede de fluxo, no contexto da Teoria dos Grafos, é um grafo dirigido ponderado

G = (V, A, c), na qual V representa o conjunto de vértices, A o conjunto de arcos e

84 Capítulo 9. Fluxo Máximo

c : V ×V → R+ é a função de capacidade de cada arco. Impõe-se ainda que se há um arco

¡ ¢
(u, v) não há um arco (v, u). Se (u, v) ∉ A, então c (u, v) = 0. Há dois vértices distintos:

o vértice de origem ou fonte, geralmente chamado de s, e o vértice de destino ou

sorvedouro, chamado de t . or conveniência, assume-se que todo o vértices v ∈ V \{s, t },

s v t (CORMEN et al., 2012).

Um fluxo em G é uma função f : V × V → R que satisfaz as seguintes propriedades:

¡ ¢ ¡ ¢
• Restrição de capacidade: para todo u, v ∈ V , 0 ≤ f (u, v) ≤ c (u, v) ;

• Conservação de fluxo: para todo u ∈ V \{s, t },

X ¡ ¢ X ¡ ¢
f (v, u) = f (u, v) .
v∈V v∈V

¡ ¢
Quando (u, v) ∉ A, então f (v, u) = 0.
¡ ¢
A quantidade não negativa f (v, u) é denominada o fluxo do vértice u a v. O valor
P ¡ ¢ P ¡ ¢
de fluxo é dado por F = v∈V f (s, v) − v∈V f (v, s) , ou seja, o total de fluxo que

sai de s menos o total de fluxo que entra em s.

Quando (u, v), (v, u) ∈ A, deve-se remover (u, v) de A, adicionar um novo vértice

v 0 a V , adicionar os arcos (u, v 0 ) e (v 0 , v) a A definido as capacidades c (u, v 0 ) →

¡ ¢

c (u, v) e c (v 0 , v) → c (u, v) e c (u, v) → 0.

¡ ¢ ¡ ¢ ¡ ¢ ¡ ¢

Para múltiplas origens s 1 , s 2 , . . . , s k pode-se adicionar um vértice inicial s 0 a G e os

arcos (s 0 , s i ) com capacidade c (s 0 , s i ) → ∞ para todo i ∈ {1, 2, . . . , k}.

¡ ¢

Para múltiplos destinos t 1 , t 2 , . . . , t l pode-se adicionar um vértice final t 0 a G e os

arcos (t j , t 0 ) com capacidade c (t j , t 0 ) → ∞ para todo j ∈ {1, 2, . . . , l }.

¡ ¢

O problema de fluxo máximo busca encontrar o maior fluxo em G de s a t tal que as

capacidades de cada arco sejam respeitadas.

9.2. Rede Residual 85

9.2 Rede Residual

Uma rede residual consiste em um grafo G f = (V, A f , c f ) composto por arcos com
¡ ¢ ¡ ¢ ¡ ¢
capacidades c f (u, v) = c (u, v) − f (u, v) para todo arco A. Para cada arco (u, v) em
¡ ¢ ¡ ¢
A, têm-se um arco invertido em A f com capacidade c f (v, u) = f (u, v) . Se um arco
¡ ¢
(u, v) ∉ A, então c f (v, u) = 0. Desse modo, |A f | = 2|A|.

9.3 Caminhos Aumentantes

Em uma rede de fluxo G, um caminho aumentante p é um caminho simples de s a t

na rede residal G f . Ele aumenta o fluxo na rede sem ferir as restrições de capacidades
¡ ¢
impostas em c. A capacidade residual de p é c f (p) = min{c f (u, v) : (u, v) ∈ p}.

Lema 9.3.1. Seja G = (V, A, c) uma rede de fluxo com fonte s e sorvedouro em t , seja p

um caminho aumentante em G e seja f um fluxo em G. Defina a função f p : V ×V → {R}

por


¡ ¢ c f (p) se(u, v) ∈ p,

f p (u, v) =

0 caso contrário.


Então, f p é um fluxo em G f com valor c f (p) > 0.

Prova: Página 524 de Cormen et al. (2012).

Corolário 9.3.2. Seja G = (V, A, c) uma rede de fluxo, seja f um fluxo em G e seja p

um caminho aumentante em G f . Considere a função f p e suponha que aumenta-se f

adicionando f p . Então a função f ↑ f p é um fluxo em G.

Prova: Página 525 de Cormen et al. (2012).

9.4 Cortes de Redes de Fluxo

Em uma das estratégias para se obter o fluxo máximo, busca-se caminhos aumentantes

iterativamente. Como saber que quando o algoritmo termina, têm-se realmente o fluxo
86 Capítulo 9. Fluxo Máximo

máximo? O teorema de fluxo máximo/corte mínimo diz que se não houver caminho

aumentante, atingiu-se o fluxo máximo.

Lema 9.4.1. Seja G = (V, A, c) uma rede de fluxo com fonte s e sorvedouro em t , e seja

(S, T ) qualquer corte de G. O fluxo que passa pelo corte é igual a F (o valor do fluxo).

Prova: Página 526 de Cormen et al. (2012).

Corolário 9.4.2. O valor de qualquer fluxo em f em uma rede de fluxo G é limite superior

pela capacidade de qualquer corte de G.

Prova: Página 526 de Cormen et al. (2012).

Teorema 9.4.3. Se f é um fluxo em uma rede de fluxo G = (V, A, c) com fonte s e sorve-

douro t , então as seguintes condições são equivalentes:

1. f é um fluxo máximo em G.

2. A rede residual G f não contém nenhum caminho aumentante.

3. F é a capacidade de corte para algum corte (S, T ).

Prova: Página 527 de Cormen et al. (2012).

9.5 Ford-Fulkerson

O algoritmo de Ford-Fulkerson se baseia em três ideias principais: redes residuais,

¡ ¢
caminhos aumentantes e cortes. Começa-se com f (u, v) = 0 para todo u, v ∈ V . O

método de Ford-Fulkerson aumenta iterativamente o valor de fluxo, identificando os

arcos que podem alterar seu fluxo, consultando suas capacidades. O fluxo aumenta até

que não haja mais caminhos aumentantes.

9.5. Ford-Fulkerson 87

O Algoritmo 23 é demonstrado abaixo.

Algoritmo 23: Algoritmo de Ford-Fulkerson.

Input :um grafo dirigido e ponderado G = (V, A, c), um vértice fonte s, um vértice

sorvedouro t , uma rede residual G f = (V, A f , c f )

1 F ←0

2 while existir um caminho aumentante p na rede residual de s a t do

// Identificando a capacidade do caminho e adicionando-o ao fluxo atual

¡ ¢
3 f p ← min{c f (u, v) : (u, v) ∈ p}

4 F ← F + fp

// Atualizando a capacidade residual

5 foreach (u, v) ∈ p do
¡ ¢ ¡ ¢
6 c f (u, v) ← c f (u, v) − f p
¡ ¢ ¡ ¢
7 c f (v, u) ← c f (v, u) + f p

8 return F

9.5.1 Complexidade

A complexidade de tempo computacional de F or d − F ul ker son depende do fluxo

máximo. A Figura 9.6.1 demonstra um exemplo de um pior caso. O tempo para encontrar

um caminho de s para t é de O(|V | + |A|) = O(|A|). Devido a característica de depender

do valor do fluxo, a quantidade de caminhos que podem ser encontrados é de f ∗ , ou

seja, o valor de fluxo máximo. Então a complexidade de tempo do algoritmo é O(|A| f ∗ ).

00 u 1,0 9 u 1,0 99 u 999

0,0 00, ,99 00, ,9 ,99
1,0
0 000 999 000 999 9
1 1 1
s t s t s 999 t
999 999
1

, ,99 ,
1,0 1,0 999 9 999
00, 000 00,
000 00, 000 1 1 1
v 1,0 v v

(a) (b) (c)

Figura 7 – Exemplo citado por Cormen et al. (2012) para demonstrar o pior caso quanto
a complexidade de tempo.
88 Capítulo 9. Fluxo Máximo

9.6 Edmonds-Karp

Dado a complexidade do algoritmo de Ford-Fulkerson, é impraticável executá-lo para

instâncias muito grandes que caem no caso de caminhos aumentantes pequenos. O

algoritmo Edmonds-Karp propõe uma pequena adaptação para superar esse problema.

No lugar de encontrar um caminho aumentante arbitrário, Edmonds-Karp usa uma

busca em largura descrita no Algoritmo 24.

Algoritmo 24: Busca em Largura para Edmonds-Karp.

Input :um grafo dirigido e ponderado G = (V, A, c), um vértice fonte s, um vértice
sorvedouro t , uma rede residual G f = (V, A f , c f )
// configurando todos os vértices
1 C v ← false ∀v ∈ V
2 A v ← null ∀v ∈ V
// configurando o vértice de origem
3 C s ← true
// preparando fila de visitas
4 Q ← Fila()
// Iniciar busca pela fonte.
5 Q.enqueue(s)
// propagação das visitas
6 while Q.empty() = false do
7 u ← Q.dequeue()
8 foreach v ∈ N + (u) do
¡ ¢
9 if C v = false ∧ c f (u, v) > 0 then
10 C v ← true
11 Av ← u
// Sorvedouro encontrado. Criar caminho aumentante.
12 if v = t then
13 p ← (t )
14 w ←t
15 while w 6= s do
16 w ← Aw
17 p ← (w) ∪ p
18 return p
19 Q.enqueue(v)

20 return null

Lema 9.6.1. Se o algoritmo Edmonds-Karp é executar em uma rede de fluxo G = (V, A, c)

com a fonte s e o sorvedouro sendo t , então para todos os vértices, exceto s e t , a distância
9.6. Edmonds-Karp 89

do caminho mínimo δ f (s, v) na rede residual G f aumenta monotonicamente com cada

aumento de fluxo.

Prova: Página 530 de Cormen et al. (2012).

Teorema 9.6.2. Se o algoritmo Edmonds-Karp é executar em uma rede de fluxo G =

(V, A, c) com a fonte s e o sorvedouro sendo t , então o número total de aumentos de fluxo

executados pelo algoritmo é de no máximo |V | · |A|.

Prova: Página 531 de Cormen et al. (2012).

9.6.1 Complexidade

Como cada caminho aumentante pode ter um arco crítico1 , o número total de arcos

críticos é O(|V | · |A|). Como cada iteração do Ford-Fulkerson pode demandar passar por

no máximo O(|A|) arcos, a complexidade do algoritmo Edmonds-Karp é de O(|V ||A|2 ).

Para pensar

Será que os arcos de retorno ainda fazem sentido para o algoritmo de Edmonds-Karp?

Verifique o seguinte exemplo:

1
Considera-se arco crítico todo arco que define um fluxo para um caminho aumentante (que define o
valor de c f (p) em um caminho p).
90 Capítulo 9. Fluxo Máximo

1
d e
1
1
1 1 1 1
s a b c t
1
1
1 g 1
f h

Figura 8 – Exemplo da importância dos arcos de retorno para Edmonds-Karp.

.
 CAPÍTULO 10
Emparelhamento

10.1 Emparelhamento Máximo em Grafos Bipartidos

Dado um grafo bipartido não dirigido G = (V = X ∪ Y , E ), no qual V é o conjunto de

vértices bipartidos, e E é o conjunto de arestas. Considere que em cada aresta {x, y},

x ∈ X e y ∈ Y . Considere também que X e Y são disjuntos, ou seja, X ∩ Y = ;. Um

emparelhamento M em G é um subconjunto de arestas M ⊆ E tal que cada vértice

aparece no máximo uma vez em M . Nesse problema, deseja-se encontrar um conjunto

M de maior tamanho possível (KLEINBERG; TARDOS, 2005).

10.1.1 Resolução por Fluxo Máximo

De acordo com Kleinberg e Tardos (2005), uma forma de resolver esse problema é

através do uso de algoritmos de fluxo máximo. Para isso,deve-se adaptar o grafo de

entrada. O Algoritmo 25 formaliza essa adaptação. A Figura 12 um exemplo de antes e

depois da adaptação.
92 Capítulo 10. Emparelhamento

Algoritmo 25: Adaptação de entrada de Emparelhamento Máximo para um

algoritmo de Fluxo Máximo.
Input :um grafo bipartido não-dirigido e não-ponderado G = (V = X ∪ Y , E )
// Criando conjunto de vértices, considerando um novo vértice de origem s
e um novo de destino t
1 V 0 ← X ∪ Y ∪ {s, t }
// Criando novo conjunto de arcos
2 A ← {}
// Transformando as arestas de E em arcos
3 foreach {x, y} ∈ E do
4 considere que x ∈ X e y ∈ Y
5 A ← A ∪ {(x, y)}
// Criando arcos entre s e x ∈ X
6 foreach x ∈ X do
7 A ← A ∪ {(s, x)}
// Criando arcos entre s e y ∈ Y
8 foreach y ∈ Y do
9 A ← A ∪ {(y, t )}
// Definindo os pesos de cada arco
10 criar função w : A → 1
11 G 0 ← (V 0 , A, w)
12 return G 0

s t

(a) (b)

Figura 9 – Exemplo citado por Kleinberg e Tardos (2005) na tranformaçao do grafo bipar-
tido não dirigido para um grafo dirigido e ponderado que, ao ser submetido
a um algoritmo de fluxo máximo, obtém-se o emparelhamento máximo.

Depois de adaptada a entrada para o problema de Fluxo Máximo, consegue-se obter

o emparelhamento submetendo-a a um algoritmo de fluxo máximo. Pode-se ainda

utilizar as informações de fluxo para determinar o conjunto M .

10.1. Emparelhamento Máximo em Grafos Bipartidos 93

Algoritmo 26: Resolução de Emparelhamento Máximo através um algoritmo

de Fluxo Máximo.
Input :um grafo bipartido não-dirigido e não-ponderado G = (V = X ∪ Y , E )
1 Obter G 0 a partir do Algoritmo 25 passando por parâmetro o grafo G.
2 Criar rede residual G 0f a partir de G 0
3 Executar algoritmo de fluxo máximo passando por parâmetro: G 0 , como rede de fluxo;
G 0f , como rede residual, s, como vértice de origem; e t como vértice de destino ou
sorvedouro.; // Criando o conjunto de emparelhamento M
4 M ← {}
5 foreach {x, y} ∈ E do
6 considere que x ∈ X e y ∈ Y
¡ ¢
7 if c f (x, y) = 0 then
© ª
8 M ← M ∪ {x, y}

9 return M

10.1.1.1 Complexidade

A tranformação de um grafo bipartido em uma rede de fluxo demanda tempo computa-

cional O(|V |+|E |). Supondo que utilizemos o algoritmo de Ford-Fulkerson para resolver

o problema, a mesma possui a complexidade de tempo O(|A 0 | f ∗ ) G 0 = (V 0 , A 0 , w). Sa-

bendo que o fluxo máximo é o menor entre |X | e |Y |, poderíamos reecrever a função

O(|A 0 ||V |). Analisando o Algoritmo 25, sabe-se que |A 0 | = |E | + |X | + |Y |. Então a com-
¡
plexidade de tempo em usar o algoritmo de Ford-Fulkerson é O |V | + |E | + (|E | + |X | +
¢ ¡ ¢
|Y |)|V | = O (|E | + |X | + |Y |)|V | = O(|E ||V | + |X ||V | + |Y ||V |) = O(|E ||V |).

10.1.2 Algoritmo de Hopcroft-Karp

Um algoritmo mais eficiente do que utilizar algoritmos de Fluxo Máximo é o Hopcroft-

Karp. Ele é demonstrado no Algoritmo 27. Para entender o algoritmo, devemos compre-

ender o conjunto de caminhos aumentantes em seu contexto.

Um caminho aumentante alternante é todo o caminho possui início em vértice livre

em X e o fim em um vértice livre em Y . É dito vértice livre, um vértice que não está em M .

Diferente de outros caminhos que foram vistos na disciplina, um caminho aumentante

aqui é uma sequência de arestas p =< e 1 , e 2 , . . . , e m > no qual e 1 , e 2 , . . . , e m ∈ E .

Na linha 4 do algoritmo, utiliza-se o operador ⊕ (XOR). Em conjuntos A ⊕ B =

94 Capítulo 10. Emparelhamento

(A\B ) ∪ (B \A).

Algoritmo 27: Algoritmo de Hopcroft-Karp.

Input :um grafo bipartido não-dirigido e não-ponderado G = (V = X ∪ Y , E )
1 M ← {}
2 repeat
3 P ← conjunto de caminhos aumentantes alternantes p 1 , p 2 , . . . , p k
S
4 M ← M ⊕ p∈P p
5 until P = {}
6 return M

10.1.2.1 Algoritmo detalhado

Algoritmo 28: Algoritmo de Hopcroft-Karp detalhado.

Input :um grafo bipartido não-dirigido e não-ponderado G = (V = X ∪ Y , E )

1 D v ← ∞ ∀v ∈ V

2 mat e v ← null ∀v ∈ V

// tamanho do emparelhamento

3 m←0

4 while B F S(G, mat e, D) =true do

5 foreach x ∈ X do

6 if mat e x = null then

7 if DF S(G, mat e, x, D) = true then

8 m ← m +1

9 return (m, mat e)

10.1. Emparelhamento Máximo em Grafos Bipartidos 95

Algoritmo 29: BFS

Input :um grafo bipartido não-dirigido e não-ponderado G = (V = X ∪ Y , E ), um vetor
de emparelhamento mat e, um vetor de distâncias D
1 Q ← Fila()
2 foreach x ∈ X do
3 if mat e x = null then
4 Dx ← 0
5 Q.enqueue(x)
6 else
7 Dx ← ∞

8 D nul l ← ∞
9 while Q.empty() = false do
10 x ← Q.dequeue()
11 if D x < D nul l then
12 foreach y ∈ N (x) do
13 if D mat e y = ∞ then
14 D mat e y ← D x + 1
15 Q.enqueue(mat e y )

16 return D nul l 6= ∞

Algoritmo 30: DFS

Input :um grafo bipartido não-dirigido e não-ponderado G = (V = X ∪ Y , E ), um vetor

de emparelhamento mat e, um vértice x ∈ X , um vetor de distâncias D

1 if x 6= null then

2 foreach y ∈ N (x) do

3 if D mat e y = D x + 1 then

4 if DF S(G, mat e, mat e y , D) = true then

5 mat e y ← x

6 mat e x ← y

7 return true

8 Dx ← ∞

9 return false

10 return true
96 Capítulo 10. Emparelhamento

10.1.2.2 Complexidade

Cada fase do algoritmo consiste em uma busca em largura e uma em profundidade.

p
Então, uma única fase pode utilizar tempo O(|E |). Como há apenas |V | caminhos
p
aumentantes alternante, a complexidade de tempo é O( |V ||E |).

10.2 Emparelhamento Máximo em Grafos

O emparelhamento máximo em grafos não-dirigidos e não-ponderados é o problema

de encontrar o maior conjunto independente de arestas. A chave para este emparelha-

mento está nos caminhos aumentantes alternantes. No entanto, ao tentar encontrar

esses caminhos, pode-se encontrar um ciclo que não pode ser excluído. Em 1965, Ed-

monds descobriu uma forma de resolver isso, mesclando os vértices desse ciclo recursi-

vamente (blossom), tornando a instância de entrada menor (SCHRIJVER, 2004). Nessa

seção, se conhecerá o algoritmo presente no livro Papadimitriou e Steiglitz (1982), com

complexidade de tempo O(|V |4 ), mas há algoritmos muito mais eficientes: Algoritmo

de Balinski O(|V |3 ), Algoritmo de Even-Kariv O(|V |5/2 ), e o Algoritmo de Micali-Vazirani

p
O( |V ||E |).
10.2. Emparelhamento Máximo em Grafos 97

Algoritmo 31: Emparelhamento máximo para grafos não-dirigidos e não-

ponderados.
Input :um grafo não-dirigido e não-ponderado G = (V, E )

// Vetor que identifica o par do emparelhamento

1 M v ← null ∀v ∈ V

// Vetor que identifica se o vértice foi visitado ou não

2 C v ← false ∀v ∈ V

// Criando o vetor de expostos

3 X v ← null ∀v ∈ V

// Criando o vetor de vértices vistos

4 S v ← false ∀v ∈ V

// Criando o vetor de rótulos

5 L v ← null ∀v ∈ V

6 while ∃u ∈ V : C u = false ∧ M u =null do

7 u ← selecionar um u ∈ V , o qual C u = false ∧ M u =null

8 C u ← true

9 A ← {}

// populando o vetor de expostos

10 X v ← null ∀v ∈ V

// Fazer no sentido v para w e w para v

11 foreach {v, w} ∈ E do

12 if M w = null ∧ w 6= u then

13 Xv ← w

14 else

15 if M w ∉ {v,null} then

16 A ← A ∪ {(v, M w )}

17 S v ← false ∀v ∈ V

18 Q ← {u}

19 L u ← null

20 if X u 6= null then

21 AumentanteAlternante(G, u, M , X , L)

22 else

23 while Q 6= {} do

24 v ← selecione um vértice em Q

25 Q ← Q\{v}

26 foreach w ∈ V : L w =null∧(v, w) ∈ A do

27 Q ← Q ∪ {w}

28 Lw ← v

29 S M w ← true

30 if X w 6= null then

31 AumentanteAlternante(G, w, M , X , L)

32 Q ← {}

33 break

34 else

35 if S w = true then

36 Blossom(G, w)

37 return M
98 Capítulo 10. Emparelhamento

Algoritmo 32: AumentanteAlternante

Input :um grafo não-dirigido e não-ponderado G = (V, E ), um vértice v, os vetores M ,
X, L
1 if L v = null then
2 Mv ← X v
3 X Mv ← v
4 else
5 X Lv ← Mv
6 Mv ← X v
7 MXv ← v
8 AumentanteAlternante(G, L v , M , X , L)

Algoritmo 33: Blossom

Input :um grafo não-dirigido e não-ponderado G = (V, E ), um vértice b, os vetores M ,
X , L, B , Y
1 T ← buscar conjunto de vértices que estão no ciclo envolvendo b, incluindo-o
2 Yb ← ciclo de b
3 foreach t ∈ T do
4 Bt ← b
// Mesclando os vértices de B
5 Substituir qualquer instância do nodo x ∈ B no grafo auxiliar A, na fila Q e no vetor label
por um novo vértice v b que representa o “blossom” de b
 CAPÍTULO 11
Coloração de Grafos

O problema da coloração de grafos busca encontrar um conjunto de “cores” a serem

atribuídos aos vértices, sem que vértices adjacentes tenham a mesma cor. O problema

tem como entrada um grafo não-dirigido e não-ponderado G = (V, E ). Sua versão de

decisão busca recebe além de G um valor inteiro k e deseja-se saber se é possível

encontrar um conjunto de “cores” (ou valores/números cromáticos) com tamanho

menor ou igual a k. Na sua versão de otimização, geralmente tenta-se encontrar o

conjunto mínimo de cores para G.

O problema de decisão com k > 3 é NP-Completo e o problema de otimização é

NP-Difícil o que significa que não existe um algoritmo executado em tempo polinomial

para os mesmos a não ser que P = N P .

11.1 Aplicações

As aplicações da coloração de grafos estão associadas a problemas de alocaçao. Seguem

alguns exemplos citados por Kleinberg e Tardos (2005):

• Suponha uma coleção de n tarefas em um sistema que pode processá-los para-

lelamente, mas certos pares de tarefas não podem ser processados ao mesmo

tempo, pois usam algum mesmo recurso. Deseja-se executar em k unidades de

100 Capítulo 11. Coloração de Grafos

tempo todos os recursos. Então, cria-se um grafo G no qual os vértices são as

tarefas e as arestas ligam duas tarefas que não podem ser executadas no mesmo

tempo. Ao submeter G e k a um algoritmo de decisão da coloração, pode-se obter

em que unidade de tempo cada tarefa deve ser executada.

• Suponha que deseja-se construir um compilador e no processo de compilação

deve-se associar cada variável a um de k resgistradores disponíveis. Aqui, para

o grafo G, os vértices seriam as variáveis e as arestas conectam dois vértices

correspondentes a duas variáveis que estão em uso ao mesmo tempo em algum

momento do programa. Um algoritmo de coloração de decisão ajudará a escolher

qual o registrador seguro para cada variável.

• Deseja-se um dos k comprimentos de onda (transmissão sem fio) para cada n

dispositivos, mas se dois dispositivos estiverem muito próximos, dois compri-

mentos de onda devem ser atribuídos para evitar interferências. Um algoritmo de

coloração indicará qual comprimento de onda deve ser atribuído a cada um dos

n dispositivos.

11.2 Algoritmo de Lawler

O algoritmo de Lawler resolve o problema de otimização e encontra o número cor-

respondente a menor quantidade de cores em G (LAWLER, 1976). O algoritmo usa os

conjuntos independentes maximais1 identificados a partir de subgrafos formados por

subconjuntos de vértices.

O algoritmo de Lawler é representado no Algoritmo 34. Nesse algoritmo, S possui

todos os subconjuntos de vértices possíveis (2|V | subconjuntos). Cada subconjunto

1
Um conjunto independente maximal é um conjunto de vértices no qual cada vértice não está co-
nectado a cada outro, e não exista outro vértice no grafo que poderia pertencer a esse conjunto
conservando essa propriedade.
11.2. Algoritmo de Lawler 101

é utilizado para identificar qual a coloração mínima considerando os vértices que

pertence a ele. Isso se baseia na recorrência



¡ ¢ 0
 se S={},
OP T G = (S, E ) = n ³
 ª¢´o
1 + minI ∈I(G) OP T G 0 = S\I , {u, v} ∈ E : u, v ∈ S\I
¡ ©
caso contrário.


Nessa recorrência, I(G) é um algoritmo que retorna os conjuntos independentes maxi-

mais do grafo (ou subgrafo) G.

Ainda quanto ao algoritmo, a função f : 2V → Z+

∗ mapeia um subconjunto do

conjunto de vértices em um número inteiro obtido a partir de uma representação

binária ordenada do conjunto de vértices. O vetor X é indexado de acordo com esse

número inteiro obtido por f (·). X f (S) possui o coloração mínima possível considerando

o subconjunto de vértices S.

Algoritmo 34: Algoritmo de Lawler

Input :um grafo não-dirigido e não-ponderado G = (V, E )
1 X ← vetor indexado entre 0 e 2|V | − 1
2 X0 ← 0
3 S ← 2V
// Suponha que S corresponde a ordem crescente dada por f (·)
foreach S ∈ S\ {} do
© ª
4
5 s ← f (S)
6 Xs ← ∞
G 0 ← S, {u, v} ∈ E : u, v ∈ S
¡ © ª¢
7
8 foreach I ∈ I(G 0 ) do
9 i ← f (S\I )
10 if X i + 1 < X s then
11 Xs ← Xi + 1

12 return X 2|V | −1

11.2.1 Complexidade

O algoritmo demanda complexidade de tempo O(|V ||E |2.4423|V | ). Isso devido ao uso

da função de encontrar o conjunto indenpendente. Para maiores detalhes sobre esse e

outros algoritmos de coloração de grafos, veja De Lima e Carmo (2019).

102 Capítulo 11. Coloração de Grafos

11.3 Listar Conjuntos Independentes Maximais

Algoritmo 35: Listar Conjuntos Independentes Maximais

Input :um grafo não-dirigido e não-ponderado G = (V, E )
// S é uma lista de todos os subconjuntos possíveis de vértices de V ,
ordenados na ordem decrescente pela cardinalidade (tamanho) de cada
subconjunto.
1 S ← 2V
2 R ← {}
3 foreach X ∈ S do
// Verifica se X é um conjunto independente
4 c ← true
5 foreach v ∈ X do
6 foreach u ∈ X do
7 if {u, v} ∈ E then
8 c ← false
9 break

10 if c = true then
11 remover todos os subconjuntos de X de S
© ª
12 R ←R ∪ X

13 return R
 CAPÍTULO 12
Caminho Crítico

Método do Caminho Crítico (CPM - Critical Path Method) e a técnica de revisão e avalia-

ção de programa (PERT - Program Evaluation and Review Technique) são métodos para

tratar grafos de planejamento de projetos. Um projeto é definido como um conjunto

de atividades, sendo que cada atividade consome tempo e recursos determinados. O

objetivo dos métodos é fornecer maneiras analíticas de resolver a programação das

atividades do projeto (TAHA, 2006).

Tanto para o CPM quanto para PERT, divide-se as fases de planejamento de projeto

nas seguintes etapas:

1. Definição das atividades do projeto, seus tempos e recursos;

2. Construção do grafo representando as atividades seus tempos de execução as

interdependências entre as tarefas;

3. Cálculo do caminho crítico;

4. Programação temporal das tarefas.

Segundo Taha (2006), CPM e PERT foram desenvolvidas independentemente uma

da outra. A diferença entre elas é que CPM considera durações determinísticas para as

atividades e PERT durações probabilísticas.

104 Capítulo 12. Caminho Crítico

Cada atividade do projeto será um arco no grafo. Os vértices do grafo estabelecem

as precedências entre as atividades. Há duas regras para se construir o grafo:

1. Cada atividade é representada por apenas um arco;

2. Para manter a corretude das relações de precedência, precisa-se responder às

seguintes perguntas: (i) quais atividades devem preceder imediatamente a ativi-

dade atual; (ii) quais atividades devem vir depois da atividade atual; e (iii) quais

atividades devem ocorrer concorrentemente da atividade atual.

Para responder as perguntas da segunda regra, pode-se ter que criar atividades fictícias

para garantir correta precedência. Na Figura 10, há um esquema de como resolver

conflito de recorrência entre duas atividades, criando uma atividade inexistente com

duração que demanda 0 unidades de tempo (arcos tracejados), de acordo com Taha

(2006).

2 2
A
A
B B
1 3 1 3

2 2
B
B

1 3 1 3
A A

Figura 10 – Utilização de atividade fictícia para representar atividades concorrentes

(TAHA, 2006).
12.1. Listar Conjuntos Independentes Maximais 105

Algoritmo 36: Listar Conjuntos Independentes Maximais

Input :um grafo não-dirigido e não-ponderado G = (V, E )
// S é uma lista de todos os subconjuntos possíveis de vértices de V ,
ordenados na ordem descrescente pela cardinalidade (tamanho) da cada
subconjunto.
1 S ← 2V
2 R ← {}
3 foreach X ∈ S do
// Verifica se X é um conjunto independente
4 c ← true
5 foreach x ∈ X do
6 foreach u ∈ X do
7 if {u, v} ∈ E then
8 c ← false
9 break

10 if c = true then
© ª
11 remover todos os subconjuntos de X de S R ← R ∪ X

12 return R

12.1 Listar Conjuntos Independentes Maximais

12.2 Cálculo do caminho crítico

De acordo com Taha (2006), executam-se cálculos com o objetivo de encontrar a du-

ração total necessária para concluir o projeto e a classificação das atividades entre

críticas1 ou não-críticas.

Considerando que evento é um ponto no tempo em que algumas tarefas são con-

cluídas e outras são iniciadas, define-se:

• E j é o tempo mais cedo da ocorrência de um evento j ;

• T j é o tempo mais tarde da ocorrência de um evento j ;

• D i j é a duração da atividade representada pelo arco (i , j ).

O cálculo do caminho crítico envolve dois passos: o forward-pass, que define E j , e o

backward-pass, que define T j .

1
Uma atividade é considerada crítica se há apenas como executá-la em um tempo inicial e final
determinados cujo intervalo é igual a duração da referida tarefa.
106 Capítulo 12. Caminho Crítico

Forward-pass

Inicialmente, determina-se E 1 = 0 para indicar que o evento inicial é o ponto de partida.

Depois, considera-se o vértice do evento j . Dados de arcos/atividades entrantes no

vértice j , calcula-se

© ª
E j = maxv∈N − ( j ) E v + D v j . (12.1)

O processo é concluído quando todos os vértices/eventos j tiverem seus valores E j

calculados.

Backward-pass

Após a conclusão do forward-pass, inicia-se o backward-pass do vértice n, que repre-

senta o evento no qual todas as atividades já foram concluídas.

Inicialmente, define-se Tn = E n . Depois, para cada evento j , calcula-se

© ª
T j = minv∈N + ( j ) T v − D j v . (12.2)

O processo é concluído no evento 1, quando define-se que E 1 = T1 = 0.

Folgas

De acordo com Taha (2006), folgas ou flutuações são os tempos disponíveis dentro do

intervalo de tempo para uma atividade não crítica. Geralmente calcula-se a folga total e

a folga livre.

A folga total é vinculada a cada atividade e é definida como T F i j = T j − E i − D i j . Ela

representa o excesso de tempo definido entre a ocorrência mais cedo do evento i e a

ocorrência mais tarde do evento j considerando a duração da atividade (i , j ).

A folga livre é também vinculada a cada atividade e é definida como F F i j = E j −E i −

D i j . Ela representa o excesso de tempo definido desde a ocorrência mais cedo do vento

i até a ocorrência mais cedo do evento j considerando a duração da atividade (i , j ).

 Agradecimentos

Agradeço o Prof. Antônio Carlos Mariani pelo apoio e suporte quando a disciplina de

Grafos fora cedida aos meus cuidados.

 Referências

CORMEN, T. H. et al. Algoritmos: teoria e prática. Rio de Janeiro: Elsevier, 2012. Citado
19 vezes nas páginas 5, 7, 19, 23, 25, 28, 41, 67, 68, 69, 77, 78, 80, 84, 85, 86, 87, 89 e 113.

Da Silva Mendes, R. F.; De Santiago, R.; Lamb, L. C. Novel parallel anytime a* for graph
and network clustering. In: 2018 IEEE Congress on Evolutionary Computation (CEC).
[S.l.: s.n.], 2018. p. 1–6. Citado na página 65.

De Lima, A. M.; CARMO, R. Exact Algorithms for the Graph Coloring Problem. Revista
de Informática Teórica e Aplicada, v. 25, n. 4, p. 57, 2019. ISSN 01034308. Citado na
página 101.

GIUSCA, B. Map of Konigsberg in Euler’s time showing the actual layout of the
seven bridges, highlighting the river Pregel and the bridges. 2005. Disponível em:
<https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg#/media/File:
Konigsberg_bridges.png>. Citado na página 32.

GROSS, J. T.; YELLEN, J. Graph Theory and Its Applications. FL: CRC Press, 2006. Citado
na página 31.

KLEINBERG, J.; TARDOS, E. Algorithm Design. Boston, MA, USA: Addison-Wesley

Longman Publishing Co., Inc., 2005. ISBN 0321295358. Citado 3 vezes nas páginas 91,
92 e 99.

LAWLER, E. L. A note on the complexity of the chromatic number problem. Inf. Process.
Lett., v. 5, p. 66–67, 1976. Citado na página 100.

MARIANI, A. C. Problemas de Travessia. 2019. Disponível em: <https://www.inf.ufsc.br/

grafos/temas/travessia/travessia.htm>. Acesso em: 09 abr 2019. Citado 4 vezes nas
páginas 62, 63, 64 e 65.

NETTO, P. O. B. Grafos: teoria, modelos, algoritmos. São Paulo: Edgard Blucher, 2006.
Citado 4 vezes nas páginas 12, 13, 16 e 64.

PAPADIMITRIOU, C. H.; STEIGLITZ, K. Combinatorial Optimization: Algorithms and

Complexity. Englewood Cliffs, NJ: Prentice Hall, 1982. ISBN 0131524623 9780131524620
0486402584 9780486402581. Citado na página 96.

SCHRIJVER, A. A Course in Combinatorial Optimization. [S.l.: s.n.], 2004. Citado na

página 96.
110 Referências

TAHA, H. A. Operations Research: An Introduction (8th Edition). Upper Saddle River, NJ,
USA: Prentice-Hall, Inc., 2006. ISBN 0131889230. Citado 4 vezes nas páginas 103, 104,
105 e 106.
 APÊNDICE A
Revisão de Matemática Discreta

Conjuntos é uma coleção de elementos sem repetição em que a sequência não importa.
No Brasil, utilizamos a seguinte notação para enumerar todos os elementos de um
conjunto. Na Equação (A.1), é possível visualizar a representação de um conjunto
denominado A, formado pelos elementos e 1 , e 2 , . . ., e n . Devido ao uso da vírgula como
separador de decimais, usa-se formalmente o ponto-e-vírgula. Para essa disciplina,
podemos utilizar a vírgula como o separador de elementos em um conjunto, desde
que utilizados o ponto como separador de decimais1 . Para dar nome a um conjunto,
geralmente utiliza-se uma letra maiúscula ou uma palavra com a inicial em maiúscula.
© ª
A = e1; e2; . . . ; en (A.1)

Há duas formas de definir conjuntos. A forma por enumeração por elementos,

utiliza notação semelhante a da Equação (A.1). São exemplos de definição de conjuntos
por enumeração:

• N = {♦, ♠, ♥, ♣};

• V = {a, e, i , o, u};

• G = {α, β, γ, δ, ², ζ, η, θ, ι, κ, λ, µ, ν, ξ, π, ρ, σ, τ, υ, φ, χ, ψ, ω};

• R = {−100.9, 12.432, 15.0};

• D = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

A forma por descrição de propriedades utiliza-se de uma notação que evidencia a natu-
reza de cada elemento pela descrição de um em um formato genérico. Por exemplo o
conjunto D, descrito na Equação (A.2), denota um conjunto com os mesmos elementos
em {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

D = {x ∈ Z|x > 1 ∧ x ≤ 10} (A.2)

. Então para que complicar utilizando uma notação não enumerativa? Por dois motivos:
por questões de simplicidade, dado a quantidade de conjuntos; ou para representar
conjuntos infinitos, como no exemplo dos inteiros pares Pares = {x ∈ Z|x ≡ 0( mod 2)}.
1
Nas anotações
© presentesªnesse documento, utiliza-se a “notação americana”. Para a Equação (A.1) ,
teria-se A = e 1 , e 2 , . . . , e n .
112 Apêndice A. Revisão de Matemática Discreta

Para o conjunto dos pares, ainda podemos utilizar uma descrição mais informal, mas
que é dependente da conhecimento sobre a linguagem Portuguesa: Pares = {x ∈ Z| x é
inteiro e par }.
Para denotar a cardinalidade (quantidade de elementos) de um conjunto, utilizamos
o símbolo “|”. Para os conjuntos apresentados acima, é correto afirmar que:

• |N | = 4;

• |V | = 5;

• |R| = 3;

• |D| = 10;

• |Pares| = ∞.

A cardinalidade pode ser utilizada para identificar quantos símbolos são necessários
para representar um elemento. Por exemplo, |12, 66| = 5
Para denotar conjuntos vazios, adota-se duas formas de representação: {} ou ;.
Utilizando o operador de cardinalidade, têm-se |{}| = |;| = 0.
Como principais operações entre conjuntos, pode-se destacar:

• União (∪): união de dois conjuntos. Exemplo: {1, 2, 3, 4, 5}∪{2, 4, 6, 8} = {1, 2, 3, 4, 5, 6, 8};

• Intersecção (∩): intersecção de dois conjuntos. Exemplo: {1, 2, 3, 4, 5} ∪ {2, 4, 6, 8} =

{2, 4};

• Diferença (− ou \): diferença de dois conjuntos. Exemplo {1, 2, 3, 4, 5}\{2, 4, 6, 8} =

{1, 3, 5};

• Produto cartesiano (×): Exemplo {1, 2, 3}×{A, B } = {(1, A), (2, A), (3, A), (1, B ), (2, B ), (3, B )};

• Conjunto de partes (ou power set): o conjunto de todos os subconjuntos dos

elementos de um conjunto. Para o conjunto A = {1, 2, 3} o conjunto das partes
seria 2 A = P (A) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Funções são representadas de forma diferente na matemática discreta. Busca-se

estabelecer a relação entre um conjunto de domínio (entrada da função) e um con-
tradomínio (resposta da função). A Equação (A.3) exibe a forma como é utilizada para
formalizar uma função. Nesse formato, passa-se a natureza da entrada e da saída de
um problema. Por exemplo, a função que gera a correspondência entre o domínio dos
inteiros positivos em base decimal para base binária seria f : x ∈ Z + → {0, 1}log2 (|x|+1) .

nome da funcao : dominio → contradominio (A.3)

Para representar uma coleção de itens onde a sequência importa e a repetição
pode ocorrer, utiliza-se as tuplas. Uma tupla é representada da forma demonstrada na
Equação (A.4).
A = (e 1 , e 2 , . . . , e n ) (A.4)
. Um exemplo de uma tupla, pode ser lista de chamada de uma turma ordenada lexico-
graficamente.
 APÊNDICE B
Estruturas de Dados Auxiliares

B.1 Conjuntos Disjuntos

Para o algoritmo de Kruskal, é interessante manter um conjunto de conjuntos disjuntos,
no qual cada subconjunto representa um dos elementos de uma subárvore que comporá
a Árvore Geradora Mínima. Para representar esses conjunto disjuntos, utiliza-se uma
estrutura de dados sugerida no livro de (CORMEN et al., 2012).
Para a estrutura de conjuntos disjuntos, imagina-se que cada conjunto disjunto será
uma árvore composta por nodos que serão representados pela tripla (p, r ank, d at a),
na qual p é o nodo pai, r ank é um limite superior da altura da árvore e d at a é o dado
armazenado naquele nodo.