Teoria dos Grafos Livro Wikipedia

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Teoria dos Grafos
Grafos individuais
Conteúdo
1 Introdução - Teoria dos Grafos 1
1.1 Sete pontes de Königsberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Histórico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Definições de grafos e dígrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.3 Representação gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.4 Armazenamento de grafos em memória . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.5 Definições de teoria dos grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.6 Tipos de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.7 Problemas que envolvem grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.8 Algoritmos importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.9 Generalizações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.10 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.11 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.12 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Conceitos Básicos e Definições 9
2.1 Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Histórico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Definições de grafos e dígrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Representação gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4 Armazenamento de grafos em memória . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.5 Definições de teoria dos grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.6 Tipos de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.7 Problemas que envolvem grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.8 Algoritmos importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.9 Generalizações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.10 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.11 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.12 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Vértice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
i
ii CONTEÚDO
2.2.1 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Aresta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Tipos de arestas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Relação de adjacência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.4 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Aresta múltipla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.1 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Ciclos em um grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.1 Definição matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6 Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6.1 Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.2 Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.3 Ciência da Computação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.4 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.5 Notas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.6 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.7 Links Externos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6.8 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6.9 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 O grau de um grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.1 Lema do aperto de mãos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.2 Sequência de graus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.3 Valores especiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.4 Propriedades globais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.5 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.8 Grafo bipartido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.8.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.2 Testando biparticidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.3 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.4 Modelagem de multigrafos e hipergrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.5 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.8.6 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.8.7 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.8.8 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.9 Grafo bipartido completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.9.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.9.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.9.3 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
CONTEÚDO iii
2.9.4 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.9.5 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.10 Grafo caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.10.1 Ver também .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.10.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.10.3 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.11 Grafo completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.11.1 Número de arestas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.11.2 Planaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.11.3 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.12 Grafo cúbico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.12.1 Simetria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.12.2 Coloração e conjuntos independentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.12.3 Hamiltonicidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.12.4 Outras propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.12.5 Algoritmos e complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.12.6 História . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.12.7 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.13 Grafo Estrela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.13.1 Relação com outras famílias de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.13.2 Outras aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.13.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.14 Grafo nulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.14.1 Grafo sem arestas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.15 Grafo orientado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.15.1 Terminologia básica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.15.2 Graus de saída e graus de entrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.15.3 Conectividade de digrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.15.4 Classes de digrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.15.5 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.15.6 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.15.7 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.16 Grafo simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.16.1 Número de arestas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.17 Grafo valorado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.17.1 Representação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.17.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.17.3 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.18 Homomorfismo de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.18.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.18.2 Generalização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
iv CONTEÚDO
2.18.3 Observações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.18.4 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.18.5 Veja também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.19 Isomorfismo de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.19.1 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.19.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.19.3 Reconhecimento de isomorfismo de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.19.4 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.19.5 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.20 Laço . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.20.1 Grau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.20.2 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.20.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.20.4 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.21 Pseudografo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.21.1 Etiquetas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.21.2 Notas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.21.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.22 Pseudografo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.22.1 Etiquetas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.22.2 Notas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.22.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.23 Quiver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.23.1 Representações de quivers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.23.2 Teorema de Gabriel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.23.3 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.23.4 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.24 Vértice de corte (teoria dos grafos) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.24.1 Encontrando Vértices de corte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.24.2 Algoritmo em C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.24.3 Vértices de corte em árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.24.4 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.24.5 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.24.6 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.25 Vizinhança . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.25.1 Propriedades locais em grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.25.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . 39
3 Árvores 40
3.1 Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.1 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.2 Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
CONTEÚDO v
3.1.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Árvore de extensão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.1 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Árvore de extensão mínima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.3 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Representação de Grafos 43
4.1 Matriz de adjacência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1.1 Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.1.2 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Matriz de incidência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.1 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Lista de adjacência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.1 Aplicação em ciência da computação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.2 Conflitos de escolha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5 Automorfismo de grafos 47
5.1 Automorfismo de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.1 Complexidade computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.2 Exibindo a Simetria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.3 Famílias de grafos definidas pelos seus automorfismos . . . . . . . . . . . . . . . . . . . . 47
5.1.4 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Grafo regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2.1 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2.3 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3 Grafo fortemente regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3.1 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3.3 Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.3.4 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4 Grafo distância-regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4.1 Números Intersecção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4.2 Matrizes de adjacência distância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4.3 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.4.4 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.5 Grafo distância-transitivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.5.1 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
vi CONTEÚDO
5.6 Grafo simétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.6.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.6.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.6.3 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.7 Grafo meio-transitivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.7.1 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.8 Grafo semissimétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.8.1 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.9 Grafo aresta-transitivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.9.1 Exemplos e propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.9.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.10 Grafo vértice-transitivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.10.1 Exemplos finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.10.2 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.10.3 Exemplos infinitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.10.4 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.10.5 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.11 Grafo de Cayley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.11.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.11.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.11.3 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.11.4 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.11.5 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.12 Grafo antissimétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.12.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.12.2 Grafos switch e grafos bipartidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.12.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.13 Grafo assimétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.13.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.13.2 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.13.3 Grafos aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.13.4 Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.13.5 Referências . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6 Algoritmos em Grafos 60
6.1 Busca em largura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.1.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.1.2 Características . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.1.3 Pseudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.4 Exemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.5 Exemplo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.6 Exemplo de Implementação em Object Pascal . . . . . . . . . . . . . . . . . . . . . . . . 62
CONTEÚDO vii
6.1.7 Usos e extensões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.1.8 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2 Busca em profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2.1 Definição Formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2.2 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2.3 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2.4 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2.5 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2.6 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.3 Caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.3.1 Definição matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.3.2 Tipos de caminhos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.3.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.4 Caminho euleriano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.4.1 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.4.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.5 Caminho hamiltoniano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.5.1 Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.5.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.5.3 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.5.4 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.5.5 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.5.6 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.6 Ordenação topológica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.6.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.6.2 Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.6.3 Unicidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.6.4 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.6.5 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.6.6 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.7 Algoritmo de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.7.1 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.7.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.7.3 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.8 Algoritmo A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.8.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.8.2 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.9 Algoritmo de Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.9.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.9.2 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.9.3 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
viii CONTEÚDO
6.10 Algoritmo de Johnson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.10.1 Descrição do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.10.2 Veja também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.10.3 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7 Algoritmos para obter a árvore de extensão mínima 72
7.1 Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.1.1 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.1.2 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.2 Algoritmo de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.2.1 Descrição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.2.2 Pseudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.2.3 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.2.4 Exemplo de execução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.2.5 Implementações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.2.6 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.2.7 Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.2.8 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.3 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.3.1 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.3.2 Problemas relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.3.3 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.3.4 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.3.5 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.4 Algoritmo de Boruvka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.4.1 Ver também . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.4.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8 Grafos individuais 77
8.1 Grafo de Biggs-Smith . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.1.1 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.1.2 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.1.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.2 Grafo de Brouwer-Haemers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.2.1 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.3 Grafo de Desargues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.3.1 Construções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.3.2 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.3.3 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.3.4 Outras propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.3.5 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.3.6 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
CONTEÚDO ix
8.4 Grafo de Folkman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.4.1 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.4.2 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.4.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.5 Grafo de Foster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.5.1 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.5.2 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.5.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.6 Grafo de Frucht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.6.1 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.6.2 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.6.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.7 Grafo de Gray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.7.1 Construção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.7.2 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.7.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.7.4 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.7.5 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.8 Grafo de Heawood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.8.1 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.8.2 Incorporado em um Toro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.8.3 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.8.4 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.9 Grafo de Higman-Sims . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.9.1 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.9.2 Dentro da malha de Leech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.9.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.10 Grafo de Hoffman-Singleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.10.1 Construção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.10.2 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.10.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.11 Grafo de Holt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.11.1 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.11.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.12 Grafo de Ljubljana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.12.1 Construção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.12.2 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.12.3 História . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.12.4 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.12.5 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.13 Grafo de Nauru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
x CONTEÚDO
8.13.1 Construção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.13.2 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.13.3 Propriedades topológicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.13.4 Propriedades geométricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.13.5 História . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.13.6 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.14 Grafo de Papo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.14.1 Propriedades algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.14.2 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.14.3 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.15 Grafo de Petersen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.15.1 Construções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
8.15.2 Incorporações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
8.15.3 Simetrias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
8.15.4 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
8.16 Grafo de Shrikhande . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.16.1 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.16.2 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.16.3 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.16.4 Galeria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.17 Grafos de Chang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 89
8.17.1 Ligações externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
9 Fontes, contribuidores e licenças de texto e imagem 90
9.1 Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
9.2 Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
9.3 Licença . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Capítulo 1
Introdução - Teoria dos Grafos
1.1 Sete pontes de Königsberg
Esquema de pontes.
Grafo estilizado das pontes.
Sete pontes de Königsberg, ou, na sua forma portu-
guesa, de Conisberga, é um famoso problema histórico
da matemática resolvido por Leonhard Euler em 1736,
cuja solução negativa originou a teoria dos grafos.[1]
O problema é baseado na cidade de Königsberg (territó-
rio da Prússia até 1945, atual Kaliningrado), que é cor-
tada pelo Rio Prególia, onde há duas grandes ilhas que,
juntas, formam um complexo que na época continha sete
pontes, conforme mostra a figura ao lado. Das sete pon-
tes originais, uma foi demolida e reconstruída em 1935,
duas foram destruídas durante a Segunda Guerra Mun-
dial e outras duas foram demolidas para dar lugar a uma
única via expressa. Atualmente apenas duas pontes são
da época de Leonhard Euler.
Discutia-se nas ruas da cidade a possibilidade de atra-
vessar todas as pontes sem repetir nenhuma. Havia-se
tornado uma lenda popular a possibilidade da façanha
quando Euler, em 1736, provou que não existia caminho
que possibilitasse tais restrições.
Euler usou um raciocínio muito simples. Transformou os
caminhos em linhas e suas intersecções em pontos, cri-
ando possivelmente o primeiro grafo da história. Então
percebeu que só seria possível atravessar o caminho in-
teiro passando uma única vez em cada ponte se houvesse
exatamente zero ou dois pontos de onde saísse um nú-
mero ímpar de caminhos. A razão de tal coisa é que de
cada ponto deve haver um número par de caminhos, pois
será preciso um caminho para “entrar” e outro para “sair”.
Os dois pontos com caminhos ímpares referem-se ao iní-
cio e ao final do percurso, pois estes não precisam de um
para entrar e um para sair, respectivamente. Se não hou-
ver pontos com número ímpar de caminhos, pode-se (e
deve-se) iniciar e terminar o trajeto no mesmo ponto, po-
dendo esse ser qualquer ponto do grafo. Isso não é pos-
sível quando temos dois pontos com números ímpares de
caminhos, sendo obrigatoriamente um o início e outro o
fim.
Duas das sete pontes originais da cidade foram destruídas
durante o bombardeamento de Königsberg em agosto de
1944.[2]
1.1.1 Referências
[1] Leonhard Euler: Solutio problematis ad geometriam situs
pertinentis
[2] Peter Taylor (2000). Australian Mathematics Trust, : .
«What Ever Happened to Those Bridges?». Consultado
em 12 de abril de 2010.
1.1.2 Ver também
• Caminho euleriano
1
2 CAPÍTULO 1. INTRODUÇÃO - TEORIA DOS GRAFOS
1.2 Grafo
Grafo com 4 vértices e 6 arestas. É um grafo completo, conexo e
planar.
A teoria dos grafos é um ramo da matemática que es-
tuda as relações entre os objetos de um determinado con-
junto. Para tal são empregadas estruturas chamadas de
grafos, G(V,E), onde V é um conjunto não vazio de obje-
tos denominados vértices e E é um subconjunto de pares
não ordenados de V, chamados arestas.
Dependendo da aplicação, arestas podem ou não ter dire-
ção, pode ser permitido ou não arestas ligarem um vértice
a ele próprio e vértices e/ou arestas podem ter um peso
(numérico) associado. Se as arestas têm uma direção as-
sociada (indicada por uma seta na representação gráfica)
temos um dígrafo (grafo orientado). Um grafo com um
único vértice e sem arestas é conhecido como grafo tri-
vial.
Estruturas que podem ser representadas por grafos estão
em toda parte e muitos problemas de interesse prático
podem ser formulados como questões sobre certos grafos.
Por exemplo, a estrutura de ligações da Wikipédia pode
ser representada por um dígrafo: os vértices são os artigos
daWikipédia e existe uma aresta do artigoA para o artigo
B se e somente se A contém um link para B. Dígrafos
são também usados para representar máquinas de estado
finito. O desenvolvimento de algoritmos para manipular
grafos é um tema importante da ciência da computação.
1.2.1 Histórico
O artigo de Leonhard Euler, publicado em 1736, sobre
o problema das sete pontes de Königsberg, é considerado
o primeiro resultado da teoria dos grafos.[1] É também
considerado um dos primeiros resultados topológicos na
geometria; isto é, não dependente de quaisquer medidas.
O problema das pontes de Königsberg
Isso ilustra a profunda conexão entre a teoria dos grafos
e topologia.
Mais de um século após a publicação do artigo de Euler
sobre as pontes de Königsberg e enquanto Listing intro-
duzia o conceito de topologia, Cayley foi levado por um
interesse em formas analíticas particulares decorrentes do
cálculo diferencial para estudar uma classe particular de
grafos, as árvores[2]. Esse estudo teve diversas implica-
ções na química teórica. As técnicas usadas por ele eram
relacionadas a enumeração de grafos com propriedades
particulares.
O primeiro livro didático sobre teoria dos grafos foi es-
crito por Dénes König e publicado em 1936[3].
Um dos problemas mais conhecidos em teoria dos gra-
fos é problema das quatro cores: "É possível que qual-
quer mapa desenhado num plano, dividido em regiões,
pode ser colorido com apenas quatro cores de tal forma
que as regiões vizinhas não partilhem a mesma cor?". O
primeiro a notar o problema das quatro cores foi August
Ferdinand Möbius em 1840. Em 1852, Francis Guthrie
escreveu em uma carta para seu irmão Frederick, estu-
dante na University College London, sobre o problema.
Mas nenhum deles conseguiu resovê-lo. Então Frederick
perguntou a um de seus professores, DeMorgan[4].
1.2.2 Definições de grafos e dígrafos
Na literatura, as definições básicas da teoria dos grafos
variam bastante. Aqui estão as convenções usadas nesta
enciclopédia.
Um grafo direcionado (também chamado dígrafo ou
quiver) consiste de
• um conjunto V de vértices,
• um conjunto E de arestas e
• mapas s, t : E → V, onde s(e) é a fonte e t(e) é o alvo
da aresta direcionada e.
1.2. GRAFO 3
Um grafo não direcionado (ou simplesmente grafo) é
dado por
• um conjunto V de vértices,
• um conjunto E de arestas e
• uma função w : E → P(V) que associa a cada aresta
um subconjunto de dois ou de um elemento de V,
interpretado como os pontos terminais da aresta.
Em um grafo ou dígrafo com pesos, uma função adi-
cional E → R associa um valor a cada aresta, o que
pode ser considerado seu “custo"; tais grafos surgem em
problemas de rota ótima tais como o problema do caixeiro
viajante.
1.2.3 Representação gráfica
1
23
54
6
Um grafo com 6 vértices e 7 arestas
Os grafos são geralmente representados graficamente da
seguinte maneira: é desenhado um círculo para cada vér-
tice, e para cada aresta é desenhado um arco conectando
suas extremidades. Se o grafo for direcionado, seu sen-
tido é indicado na aresta por uma seta.
O grafo de exemplo exibido à direita é um grafo simples
com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um
conjunto de arestas E = { {1,2}, {1,5}, {2,3}, {2,5},
{3,4}, {4,5}, {4,6} } (com o mapeamento w sendo a
identidade).
Note que essa representação gráfica não deve ser confun-
dida com o grafo em si (a estrutura abstrata, não-gráfica).
Diferentes representações gráficas podem corresponder
ao mesmo grafo.[5] O que importa é quais vértices estão
conectados entre si por quantas arestas.
O trabalho pioneiro de William Thomas Tutte foi de
grande influência no desenho de grafos. Entre outras rea-
lizações, ele introduziu o uso
de técnicas da álgebra linear
para desenhar grafos.
Convenções alternativas para a representação de grafos
incluem representações por adjacência como empacota-
mento de círculos, onde vértices são representados como
regiões disjuntas no plano e arestas são representadas por
adjacências entre regiões; representações por intersecção
no qual vértices são representados como objetos geomé-
tricos não disjuntos e arestas são representadas por suas
intersecções; representações por visibilidade onde vérti-
ces são representados por regiões no plano e arestas são
representadas por regiões com uma linha de visão desobs-
truída para cada vértice; desenhos confluentes, nos quais
arestas são curvas suaves dentro de trilhos de trem; tex-
turas onde vértices são linhas horizontais e arestas são li-
nhas verticais[6]; e visualizações da matriz de adjacência
de um grafo.
O desenho de grafos em superfícies diferentes do plano é
também estudado.
1.2.4 Armazenamento de grafos em me-
mória
Há diversas maneiras de armazenarmos grafos em com-
putadores. A estrutura de dados usada dependerá tanto
da estrutura do grafo quanto do algoritmo usado para
manipulá-lo. Teoricamente, podemos dividir entre estru-
turas do tipo lista e do tipo matriz, mas em aplicações re-
ais, a melhor estrutura é uma combinação de ambas. Es-
truturas do tipo lista são frequentemente usadas em gra-
fos esparsos (grafos que possuem um pequeno número de
arestas em relação ao número de vértices, oposto ao grafo
denso, onde o número de arestas se aproxima do máximo
de arestas possível) já que exigemmenor uso damemória.
Por outro lado, estruturas do tipo matriz fornecem um rá-
pido acesso em algumas aplicações, mas podem consumir
uma grande quantidade de memória.
Estruturas do tipo lista incluem a lista de adjacência que
associa a cada vértice do grafo uma lista de todos os ou-
tros vértices com os quais ele tem uma aresta e a lista
de incidência, que armazena para cada vértice uma lista
de objetos que representam as arestas incidentes a esse
vértice[7][8].
Estruturas do tipo matriz incluem a matriz de incidência,
uma matriz de 0’s e 1’s com suas linhas representando
vértices e suas colunas as arestas e a matriz de adjacência
onde ambas linhas e colunas possuem vértices. Em am-
bos casos um 1 indica dois objetos adjacentes e 0 indica
dois objetos não adjacentes.
1.2.5 Definições de teoria dos grafos
Relações de incidência e de adjacência
Se uma aresta conecta dois vértices, então esses dois vér-
tices são ditos incidentes à aresta. Usando o grafo ao
lado como exemplo temos: 1 é incidente a 2 e 5, mas não
é incidente a 3, 4 ou 6; 4 é incidente a 5, 3 e 6, mas não
a 2 nem a 1.
Dois vértices são considerados adjacentes se uma aresta
4 CAPÍTULO 1. INTRODUÇÃO - TEORIA DOS GRAFOS
existe entre eles. No grafo acima, os vértices 1 e 2 são
adjacentes, mas os vértices 2 e 4 não são. O conjunto
de vizinhos de um vértice consiste de todos os vértices
adjacentes a ele. No grafo-exemplo, o vértice 1 possui 2
vizinhos: vértice 2 e vértice 5.
Na computação, um grafo finito direcionado ou não-
direcionado (com, digamos, n vértices) é geralmente re-
presentado por sua matriz de adjacência: uma matriz
n-por-n cujo valor na linha i e coluna j fornece o número
de arestas do i-ésimo ao j-ésimo vértices.
Valência (Grau)
A valência (ou grau) de um vértice é o número de arestas
incidentes a ele. Se houver laços, serão contados duas
vezes. No grafo de exemplo os vértices 1 e 3 possuem
uma valência de 2, os vértices 2, 4 e 5 têm a valência de
3 e o vértice 6 tem a valência de 1. Se E é finito, então a
valência total dos vértices é o dobro do número de arestas.
Em um dígrafo, distingue-se o grau de saída (o número
de arestas saindo de um vértice) e o grau de entrada
(o número de arestas entrando em um vértice). O grau
de um vértice em um dígrafo é igual à soma dos graus
de saída e de entrada. O grau de um vértice é definido
somente quando o número de arestas incidentes sobre o
vértice é finito.
• Lema do aperto de mãos diz que se os convidados
de uma festa apertarem as mãos quando se encon-
trarem pela primeira vez, o número de convidados
que apertam a mão um número ímpar de vezes é
par. Também em grafos não direcionados a soma
dos graus de todos os vértices é igual ao dobro do
número de arestas.
Passeio
Grafo com 5 vértices e 9 arestas
Um passeio p entre dois vértices A e B , definido como
p(A,B) , é uma lista alternada de vértices e arestas
p(A,B) = v0, e1, v1, e2, v2, ..., ek, vk tal que
• A = v0 e B = vk
• existe no mínimo uma aresta
• para 1 ≤ i ≤ k a aresta ei incide sobre vi−1 e vi
O tamanho de um passeio, definido por |p| corres-
ponde ao número de arestas que possui, incluindo as
repetições[9]. Na figura ao lado, um passeio do vér-
tice a até o vértice d possível é a lista p(a, d) =
a, e9, c, e2, b, e1, a, e9, c, e8, d de tamanho 5 . Note que
a aresta e9 se repete. É necessário listarmos as arestas
em um passeio para distinguirmos entre as diversas ares-
tas existentes quando estamos trabalhando em um grafo
que não é simples. Em um grafo simples, basta listarmos
os vértices[9].
Caminho
Caminho é uma sequência de vértices tal que de cada
um dos vértices existe uma aresta para o vértice seguinte.
Um caminho é chamado simples se nenhum dos vérti-
ces no caminho se repete. O comprimento do caminho
é o número de arestas que o caminho usa, contando-se
arestas múltiplas vezes. O custo de um caminho num
grafo balanceado é a soma dos custos das arestas atraves-
sadas. Dois caminhos são independentes se não tiverem
nenhum vértice em comum, exceto o primeiro e o último.
No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho
com comprimento 5, e (5, 2, 1) é um caminho simples de
comprimento 2.
• Caminho euleriano em um grafo é o caminho que
usa cada aresta exatamente uma vez. Se tal cami-
nho existir, o grafo é chamado traversável. Um ciclo
euleriano é um ciclo que usa cada aresta exatamente
uma vez.
• Caminho hamiltoniano em um grafo é o caminho
que visita cada vértice exatamente uma vez. Um
ciclo hamiltoniano é um ciclo que visita cada vér-
tice uma só vez. O grafo do exemplo contém um
caminho hamiltoniano. Enquanto determinar se um
dado grafo contém um caminho ou ciclo euleriano
é trivial, o mesmo problema para caminhos e ciclos
hamiltonianos é trabalhoso.
Ciclo (ou circuito) é um caminho que começa e acaba
com o mesmo vértice. Ciclos de comprimento 1 são la-
ços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ci-
clo de comprimento 6. Um ciclo simples é um ciclo que
tem um comprimento pelo menos de 3 e no qual o vértice
inicial só aparece mais uma vez, como vértice final, e os
outros vértices aparecem só uma vez. No grafo acima, (1,
5, 2, 1) é um ciclo simples. Um grafo chama-se acíclico
se não contém ciclos simples.
Laço (loop) num grafo ou num dígrafo é uma aresta e em
E cujas terminações estão no mesmo vértice.
1.2. GRAFO 5
1.2.6 Tipos de grafos
• Grafo simples é um grafo não direcionado, sem la-
ços e existe no máximo uma aresta entre quaisquer
dois vértices (sem arestas paralelas). Para um grafo
simples, o número de vizinhos de um vértice é igual
à sua valência.
• Grafo completo é o grafo simples em que, para
cada vértice do grafo, existe uma aresta conectando
este vértice a cada um dos demais. Ou seja, todos
os vértices do grafo possuem mesmo grau. O grafo
completo de n vértices é frequentemente denotado
por Kn. Ele tem n(n−1)/2 arestas (correspondendo
a todas as possíveis escolhas de pares de vértices).
• Grafo nulo é o grafo cujo conjunto de vértices é
vazio.
• Grafo vazio é o grafo cujo conjunto de arestas é
vazio.
• Grafo trivial é o grafo que possui apenas um vértice
e nenhuma aresta.
• Grafo regular é um grafo em que todos os vértices
tem o mesmo grau.
• Multigrafo é um grafo que permite múltiplas ares-
tas ligando
os mesmos vértices (arestas paralelas).
• Pseudografo é um grafo que contém arestas para-
lelas e laços.
• Grafo conexo um grafo é conexo se for possível
estabelecer um caminho de qualquer vértice para
qualquer outro vértice de um grafo. Se for sempre
possível estabelecer um caminho de qualquer vér-
tice para qualquer outro vértice mesmo depois de
remover k−1 vértices, então diz-se que o grafo está
k-conexo. Note que um grafo está k-conexo se, e
somente se, contém k caminhos independentes en-
tre qualquer par de vértices. O grafo de exemplo
acima é conexo (e portanto 1-conexo), mas não é 2-
conexo. Em um grafo genérico G, o corte associado
a um conjunto X de vértices é o conjunto de todas
as arestas que têm uma ponta em X e outra em V(G)
- X, onde V(G) é o conjunto de todos os vértices
pertencentes ao grafo G.
• Ponto de articulação ou Vértice de corte é um
vértice cuja remoção desliga um grafo. Uma ponte
é uma aresta cuja remoção desliga um grafo. Um
componente biconectado é um conjunto máximo
de arestas tal que qualquer par de arestas do con-
junto fazem parte de um ciclo simples comum. O
contorno de um grafo é o comprimento do ciclo
simples mais curto no grafo. O contorno de um
grafo acíclico é, por definição, infinito.
• Árvore é um grafo simples acíclico e conexo. Às
vezes, um vértice da árvore é distinto e chamado de
raiz. As árvores são muito usadas como estruturas
de dados em informática (veja estrutura de dados em
árvore).
• Floresta é um conjunto de árvores; equivalente-
mente a uma floresta, em algum grafo acíclico.
• Subgrafo de um grafo G é um grafo cujo conjunto
dos vértices é um subconjunto do conjunto de vér-
tices G, cujo conjunto de arestas é um subconjunto
do conjunto de arestas de G, e cuja função w é uma
restrição da função de G
• Subgrafo gerador é aquele obtido pela remoção de
uma ou mais arestas de um outro grafo, dizemos en-
tão que este novo grafo obtido é gerador do primeiro,
• Subgrafo induzido é obtido pela remoção de vérti-
ces e consequente das arestas relacionadas com ele
de um outro grafo, dizemos que este novo grafo é
um grafo induzido do original.
• Grafo parcial de um grafo G é um subgrafo com
o mesmo conjunto de vértices que G. Uma árvore
parcial é um grafo parcial que é árvore. Todo grafo
tem pelo menos uma árvore parcial.
• Clique em um grafo é um subgrafo que também é
um grafo completo. No grafo do exemplo acima, os
vértices 1, 2 e 5 formam um clique.
• Conjunto independente em um grafo é um con-
junto de vértices não adjacentes entre si. No exem-
plo acima, os vértices 1, 3 e 6 formam um conjunto
independente e 3, 5 e 6 são outro conjunto indepen-
dente.
• Grafo planar é aquele que pode ser representado
em um plano sem qualquer intersecção entre arestas.
O grafo do exemplo é planar; o grafo completo de n
vértices, para n> 4, não é planar.
• Grafo bipartido é o grafo cujos vértices podem ser
divididos em dois conjuntos, nos quais não há ares-
tas entre vértices de um mesmo conjunto. Para um
grafo ser bipartido ele não pode conter circuitos de
comprimento ímpar.
1. Se um grafo G é bipartido, todo o circuito
de G possui comprimento par.Sejam V1 e
V2 os dois conjuntos em que, de acordo com
a definição de grafo bipartido, se particiona
V(G). Toda a aresta de G conecta um vértice
em V1 com outro em V2. Assim sendo, se X
for um vértice de V1, para “voltar” a esse vér-
tice terá de se ir a V2 e voltar a V1 um número
indeterminado de vezes, e de cada vez serão
percorridas duas arestas, uma de um vértice
em V1 para um vértice em V2 e outra de um
vértice em V2 para um vértice em V1. Logo,
o número de arestas a percorrer será par, ou
seja, o comprimento do circuito é par.
6 CAPÍTULO 1. INTRODUÇÃO - TEORIA DOS GRAFOS
2. Se todo o circuito de um grafo G possui
comprimento par, então o grafo é bipar-
tido.Seja G um grafo em que todo o circuito
tem comprimento par, e seja X um vértice de
G. Denotemos por V1 o conjunto formado por
X e por todos os vértices cuja distância a X é
par. Seja V2 = V(G)\V1 (isto é, o conjunto
formado pelos vértices de G que não perten-
cem aV1). Pretendemostrar-se que não existe
qualquer aresta que conecte vértices de V1 ou
vértices de V2. Suponhamos a existência de
tal aresta, isto é, suponhamos a existência de
dois vértices em V1 (ou V2), digamos Xi e Xj,
conectados por uma aresta. Ora existe já um
caminho de comprimento par entre Xi e Xj,
já que existem caminhos, ambos de compri-
mento par (ou ímpar, no caso de Xi e Xj per-
tencerem a V2), entre Xi e X e entre X e Xj.
Se a esse caminho juntarmos a aresta {Xi;Xj}
obtemos um circuito de comprimento ímpar o
que contraria a hipótese de apenas existirem
circuitos de comprimento par.
• Grafo bipartido completo é o grafo bipartido, cujo
qualquer vértice do primeiro conjunto é adjacente a
todos vértices do segundo conjunto
• Grafo k-partido ou grafo de k-coloração é um
grafo cujos vértices podem ser particionados em k
conjuntos disjuntos, nos quais não há arestas en-
tre vértices de um mesmo conjunto. Um grafo 2-
partido é o mesmo que grafo bipartido.
• Emparelhamento de grafos consiste em partir o
grafo em conjuntos de vértices a qual não compar-
tilham nenhuma aresta entre eles.
• Teorema das quatro cores é baseado no problema
das cores necessárias para se colorir um mapa sem
que os países vizinhos compartilhem da mesma cor.
Transformando o mapa em um grafo pode-se provar
que pode-se representar qualquer mapa (um grafo
planar) com apenas 4 cores (4 partições).
Buscas em Árvores
Percurso em árvores
• • É possível percorrer de modo sistemático to-
dos os vértices e arestas do grafo. O grafo pode
ser dirigido ou não.
• O percurso em árvores é o processo de visitar
cada nó da árvore exatamente uma vez.
• O percurso pode ser interpretado como colo-
car todos os nós em uma linha, não existe uma
ordem para ser seguida.
• Existem n percursos diferentes, quase todos
caóticos.
• Os básicos são percurso em profundidade e
percurso em largura
• Fila: busca em largura
• Pilha: busca em profundidade
• Busca em extensão ou largura: (Breadth-First Se-
arch ou BFS). A propriedade especial está no fato
de a árvore não possuir ciclos: dados dois vértices
quaisquer, existe exatamente 1 caminho entre eles.
Um percurso em extensão é visitar cada nó come-
çando do menor nível e move-se para os níveis mais
altos nível após nível, visitando cada nó da esquerda
para a direita. Sua implementação é direta quando
uma fila é utilizada. Depois que um nó é visitado,
seus filhos, se houver algum, são colocados no final
da fila e o nó no início da fila é visitado. Assim, os
nós do nível n+1 serão visitados somente depois de
ter visitados todos os nós do nível n. Computa a me-
nor distância para todos os vértices alcançáveis. O
sub-grafo contendo os caminhos percorridos é cha-
mado de breadth-first tree.
• Busca em profundidade (Depth-first search ou
DFS). Um algoritmo de busca em profundidade re-
aliza uma busca não-informada que progride através
da expansão do primeiro nó filho da árvore de busca,
e se aprofunda cada vezmais, até que o alvo da busca
seja encontrado ou até que ele se depare com um nó
que não possui filhos (nó folha). Então a busca retro-
cede (backtrack) e começa no próximo nó. Numa
implementação não-recursiva, todos os nós expan-
didos recentemente são adicionados a uma pilha,
para realizar a exploração. A complexidade espa-
cial de um algoritmo de busca em profundidade é
muito menor que a de um algoritmo de busca em
largura. A complexidade temporal de ambos algo-
ritmos são proporcionais ao número de vértices so-
mados ao número de arestas dos grafos aos quais
eles atravessam. Quando ocorrem buscas em gra-
fos muito grandes, que não podem ser armazenadas
completamente na memória, a busca em profundi-
dade não termina, em casos onde o comprimento
de
um caminho numa árvore de busca é infinito. O sim-
ples artifício de “ lembrar quais nós já foram visita-
dos ” não funciona, porque pode não haver memória
suficiente. Isso pode ser resolvido estabelecendo-se
um limite de aumento na profundidade da árvore.
1.2.7 Problemas que envolvem grafos
• Coloração de grafos: o Teorema das quatro cores
• Conjuntos de Grafos
• Conjunto independente
• Clique
• Problemas de roteamento:
1.2. GRAFO 7
• Sete pontes de Königsberg
• Árvore de extensão mínima
• Problema do caminho mínimo
• Problema da inspeção de rotas (também co-
nhecido como o "Problema do carteiro chi-
nês")
• Problema do caixeiro viajante
• Fluxos de rede:
• Teorema do mínimo corte-máximo fluxo
• conjectura da reconstrução
• Problemas de Isomorfismo (casamento de grafos)
• Rotulação canônica?
• Isomorfismo de subgrafos e monomorfismos.
• Máximo subgrafo comum
1.2.8 Algoritmos importantes
• algoritmo de Dijkstra
• algoritmo de Kruskal
• algoritmo do vizinho mais próximo
• algoritmo de Prim.
1.2.9 Generalizações
Num hipergrafo uma aresta pode conectar mais que dois
vértices.
Um grafo não-direcionado pode ser visto como um
complexo simplicial consistindo de símplices de uma di-
mensão (as arestas) e símplices de dimensão zero (os vér-
tices). Ou seja, complexos são generalizações de grafos
que permitem símplices de maiores dimensões.
1.2.10 Referências
[1] Biggs, N.; Lloyd, E. and Wilson, R. (1986), Graph The-
ory, 1736-1936, Oxford University Press
[2] Cayley, A. (1857), “On the theory of the analytical forms
called trees”, Philosophical Magazine, Series IV 13 (85):
172–176, doi:10.1017/CBO9780511703690.046
[3] Tutte, W.T. (2001),Graph Theory, Cambridge University
Press, p. 30, ISBN 978-0-521-79489-3, https://books.
google.com/books?id=uTGhooU37h4C&pg=PA30, vi-
sitado em 2016-03-14
[4] «The Four Color Theorem». Mathpages.com. Consul-
tado em 03 de junho de 2016.
[5] Di Battista, Giuseppe; Eades, Peter; Tamassia, Ro-
berto; Tollis, Ioannis G. (1994), “Algorithms for
Drawing Graphs: an Annotated Bibliography”, Compu-
tational Geometry: Theory and Applications 4: 235–282,
doi:10.1016/0925-7721(94)00014-x
[6] Longabaugh, William (2012), “Combing the hair-
ball with BioFabric: a new approach for visua-
lization of large networks”, BMC Bioinformatics
13: 275, doi:10.1186/1471-2105-13-275, PMID
23102059, http://www.biomedcentral.com/content/pdf/
1471-2105-13-275.pdf
[7] Goodrich, Michael T.; Tamassia, Roberto (2001). Estru-
turas de Dados e Algoritmos em Java 2ª ed. (Porto Alegre:
Bookman). p. 502-503. ISBN 85-363-0043-4.
[8] Goodrich, Michael T.; Tamassia, Roberto (2004). Pro-
jeto de Algoritmos. Fundamentos, Análise e Exemplos da
Internet (Porto Alegre: Bookman). p. 299-303. ISBN
85-363-0303-4.
[9] West, Douglas Brent (2001). «Chapter 1 - Fundamental
Concepts». Introduction to Graph Theory 2nd ed. (USA:
Prentice Hall). p. 20. ISBN 0-13-014400-2.
1.2.11 Ver também
• Estrutura de dados árvore ordenada - DAGs, árvores
binárias e outras formas especiais de grafos.
• Rede complexa
• Teoria espectral de grafos
• Redes de pequeno mundo
• Modelo de Watts e Strogatz
1.2.12 Ligações externas
• Uma Introdução Sucinta à Teoria dos Grafos
• Graph theory tutorial (em inglês)
• Graph theory Algorithms (em inglês) — algoritmos
em pseudocódigo
• Algorithm Animations (em inglês)
• Graph Theory Software (em inglês)
• Lista de algoritmos de grafos (em inglês)— com re-
ferências e links para bibliotecas de implementação
de grafos
Ferramentas de grafos populares
• Graph Visualization Software (em inglês) — ferra-
menta para visualizar e interagir com diagramas de
grafos
• Visualization of Compiler Graphs (em inglês)
8 CAPÍTULO 1. INTRODUÇÃO - TEORIA DOS GRAFOS
• Data Visualization Software (em inglês)
• Planarity Game (em inglês) — jogo sobre Grafos
Planares
Capítulo 2
Conceitos Básicos e Definições
2.1 Grafo
Grafo com 4 vértices e 6 arestas. É um grafo completo, conexo e
planar.
A teoria dos grafos é um ramo da matemática que es-
tuda as relações entre os objetos de um determinado con-
junto. Para tal são empregadas estruturas chamadas de
grafos, G(V,E), onde V é um conjunto não vazio de obje-
tos denominados vértices e E é um subconjunto de pares
não ordenados de V, chamados arestas.
Dependendo da aplicação, arestas podem ou não ter dire-
ção, pode ser permitido ou não arestas ligarem um vértice
a ele próprio e vértices e/ou arestas podem ter um peso
(numérico) associado. Se as arestas têm uma direção as-
sociada (indicada por uma seta na representação gráfica)
temos um dígrafo (grafo orientado). Um grafo com um
único vértice e sem arestas é conhecido como grafo tri-
vial.
Estruturas que podem ser representadas por grafos estão
em toda parte e muitos problemas de interesse prático
podem ser formulados como questões sobre certos grafos.
Por exemplo, a estrutura de ligações da Wikipédia pode
ser representada por um dígrafo: os vértices são os artigos
daWikipédia e existe uma aresta do artigoA para o artigo
B se e somente se A contém um link para B. Dígrafos
são também usados para representar máquinas de estado
finito. O desenvolvimento de algoritmos para manipular
grafos é um tema importante da ciência da computação.
2.1.1 Histórico
O problema das pontes de Königsberg
O artigo de Leonhard Euler, publicado em 1736, sobre
o problema das sete pontes de Königsberg, é considerado
o primeiro resultado da teoria dos grafos.[1] É também
considerado um dos primeiros resultados topológicos na
geometria; isto é, não dependente de quaisquer medidas.
Isso ilustra a profunda conexão entre a teoria dos grafos
e topologia.
Mais de um século após a publicação do artigo de Euler
sobre as pontes de Königsberg e enquanto Listing intro-
duzia o conceito de topologia, Cayley foi levado por um
interesse em formas analíticas particulares decorrentes do
cálculo diferencial para estudar uma classe particular de
grafos, as árvores[2]. Esse estudo teve diversas implica-
ções na química teórica. As técnicas usadas por ele eram
relacionadas a enumeração de grafos com propriedades
particulares.
O primeiro livro didático sobre teoria dos grafos foi es-
crito por Dénes König e publicado em 1936[3].
Um dos problemas mais conhecidos em teoria dos gra-
9
10 CAPÍTULO 2. CONCEITOS BÁSICOS E DEFINIÇÕES
fos é problema das quatro cores: "É possível que qual-
quer mapa desenhado num plano, dividido em regiões,
pode ser colorido com apenas quatro cores de tal forma
que as regiões vizinhas não partilhem a mesma cor?". O
primeiro a notar o problema das quatro cores foi August
Ferdinand Möbius em 1840. Em 1852, Francis Guthrie
escreveu em uma carta para seu irmão Frederick, estu-
dante na University College London, sobre o problema.
Mas nenhum deles conseguiu resovê-lo. Então Frederick
perguntou a um de seus professores, DeMorgan[4].
2.1.2 Definições de grafos e dígrafos
Na literatura, as definições básicas da teoria dos grafos
variam bastante. Aqui estão as convenções usadas nesta
enciclopédia.
Um grafo direcionado (também chamado dígrafo ou
quiver) consiste de
• um conjunto V de vértices,
• um conjunto E de arestas e
• mapas s, t : E → V, onde s(e) é a fonte e t(e) é o alvo
da aresta direcionada e.
Um grafo não direcionado (ou simplesmente grafo) é
dado por
• um conjunto V de vértices,
• um conjunto E de arestas e
• uma função w : E → P(V) que associa a cada aresta
um subconjunto de dois ou de um elemento de V,
interpretado como os pontos terminais da aresta.
Em um grafo ou dígrafo com pesos, uma função adi-
cional E → R associa um valor a cada aresta, o que
pode ser considerado seu “custo"; tais grafos
surgem em
problemas de rota ótima tais como o problema do caixeiro
viajante.
2.1.3 Representação gráfica
Os grafos são geralmente representados graficamente da
seguinte maneira: é desenhado um círculo para cada vér-
tice, e para cada aresta é desenhado um arco conectando
suas extremidades. Se o grafo for direcionado, seu sen-
tido é indicado na aresta por uma seta.
O grafo de exemplo exibido à direita é um grafo simples
com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um
conjunto de arestas E = { {1,2}, {1,5}, {2,3}, {2,5},
{3,4}, {4,5}, {4,6} } (com o mapeamento w sendo a
identidade).
Note que essa representação gráfica não deve ser confun-
dida com o grafo em si (a estrutura abstrata, não-gráfica).
1
23
54
6
Um grafo com 6 vértices e 7 arestas
Diferentes representações gráficas podem corresponder
ao mesmo grafo.[5] O que importa é quais vértices estão
conectados entre si por quantas arestas.
O trabalho pioneiro de William Thomas Tutte foi de
grande influência no desenho de grafos. Entre outras rea-
lizações, ele introduziu o uso de técnicas da álgebra linear
para desenhar grafos.
Convenções alternativas para a representação de grafos
incluem representações por adjacência como empacota-
mento de círculos, onde vértices são representados como
regiões disjuntas no plano e arestas são representadas por
adjacências entre regiões; representações por intersecção
no qual vértices são representados como objetos geomé-
tricos não disjuntos e arestas são representadas por suas
intersecções; representações por visibilidade onde vérti-
ces são representados por regiões no plano e arestas são
representadas por regiões com uma linha de visão desobs-
truída para cada vértice; desenhos confluentes, nos quais
arestas são curvas suaves dentro de trilhos de trem; tex-
turas onde vértices são linhas horizontais e arestas são li-
nhas verticais[6]; e visualizações da matriz de adjacência
de um grafo.
O desenho de grafos em superfícies diferentes do plano é
também estudado.
2.1.4 Armazenamento de grafos em me-
mória
Há diversas maneiras de armazenarmos grafos em com-
putadores. A estrutura de dados usada dependerá tanto
da estrutura do grafo quanto do algoritmo usado para
manipulá-lo. Teoricamente, podemos dividir entre estru-
turas do tipo lista e do tipo matriz, mas em aplicações re-
ais, a melhor estrutura é uma combinação de ambas. Es-
truturas do tipo lista são frequentemente usadas em gra-
fos esparsos (grafos que possuem um pequeno número de
arestas em relação ao número de vértices, oposto ao grafo
denso, onde o número de arestas se aproxima do máximo
de arestas possível) já que exigemmenor uso damemória.
Por outro lado, estruturas do tipo matriz fornecem um rá-
pido acesso em algumas aplicações, mas podem consumir
2.1. GRAFO 11
uma grande quantidade de memória.
Estruturas do tipo lista incluem a lista de adjacência que
associa a cada vértice do grafo uma lista de todos os ou-
tros vértices com os quais ele tem uma aresta e a lista
de incidência, que armazena para cada vértice uma lista
de objetos que representam as arestas incidentes a esse
vértice[7][8].
Estruturas do tipo matriz incluem a matriz de incidência,
uma matriz de 0’s e 1’s com suas linhas representando
vértices e suas colunas as arestas e a matriz de adjacência
onde ambas linhas e colunas possuem vértices. Em am-
bos casos um 1 indica dois objetos adjacentes e 0 indica
dois objetos não adjacentes.
2.1.5 Definições de teoria dos grafos
Relações de incidência e de adjacência
Se uma aresta conecta dois vértices, então esses dois vér-
tices são ditos incidentes à aresta. Usando o grafo ao
lado como exemplo temos: 1 é incidente a 2 e 5, mas não
é incidente a 3, 4 ou 6; 4 é incidente a 5, 3 e 6, mas não
a 2 nem a 1.
Dois vértices são considerados adjacentes se uma aresta
existe entre eles. No grafo acima, os vértices 1 e 2 são
adjacentes, mas os vértices 2 e 4 não são. O conjunto
de vizinhos de um vértice consiste de todos os vértices
adjacentes a ele. No grafo-exemplo, o vértice 1 possui 2
vizinhos: vértice 2 e vértice 5.
Na computação, um grafo finito direcionado ou não-
direcionado (com, digamos, n vértices) é geralmente re-
presentado por sua matriz de adjacência: uma matriz
n-por-n cujo valor na linha i e coluna j fornece o número
de arestas do i-ésimo ao j-ésimo vértices.
Valência (Grau)
A valência (ou grau) de um vértice é o número de arestas
incidentes a ele. Se houver laços, serão contados duas
vezes. No grafo de exemplo os vértices 1 e 3 possuem
uma valência de 2, os vértices 2, 4 e 5 têm a valência de
3 e o vértice 6 tem a valência de 1. Se E é finito, então a
valência total dos vértices é o dobro do número de arestas.
Em um dígrafo, distingue-se o grau de saída (o número
de arestas saindo de um vértice) e o grau de entrada
(o número de arestas entrando em um vértice). O grau
de um vértice em um dígrafo é igual à soma dos graus
de saída e de entrada. O grau de um vértice é definido
somente quando o número de arestas incidentes sobre o
vértice é finito.
• Lema do aperto de mãos diz que se os convidados
de uma festa apertarem as mãos quando se encon-
trarem pela primeira vez, o número de convidados
que apertam a mão um número ímpar de vezes é
par. Também em grafos não direcionados a soma
dos graus de todos os vértices é igual ao dobro do
número de arestas.
Passeio
Grafo com 5 vértices e 9 arestas
Um passeio p entre dois vértices A e B , definido como
p(A,B) , é uma lista alternada de vértices e arestas
p(A,B) = v0, e1, v1, e2, v2, ..., ek, vk tal que
• A = v0 e B = vk
• existe no mínimo uma aresta
• para 1 ≤ i ≤ k a aresta ei incide sobre vi−1 e vi
O tamanho de um passeio, definido por |p| corres-
ponde ao número de arestas que possui, incluindo as
repetições[9]. Na figura ao lado, um passeio do vér-
tice a até o vértice d possível é a lista p(a, d) =
a, e9, c, e2, b, e1, a, e9, c, e8, d de tamanho 5 . Note que
a aresta e9 se repete. É necessário listarmos as arestas
em um passeio para distinguirmos entre as diversas ares-
tas existentes quando estamos trabalhando em um grafo
que não é simples. Em um grafo simples, basta listarmos
os vértices[9].
Caminho
Caminho é uma sequência de vértices tal que de cada
um dos vértices existe uma aresta para o vértice seguinte.
Um caminho é chamado simples se nenhum dos vérti-
ces no caminho se repete. O comprimento do caminho
é o número de arestas que o caminho usa, contando-se
arestas múltiplas vezes. O custo de um caminho num
grafo balanceado é a soma dos custos das arestas atraves-
sadas. Dois caminhos são independentes se não tiverem
nenhum vértice em comum, exceto o primeiro e o último.
No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho
com comprimento 5, e (5, 2, 1) é um caminho simples de
comprimento 2.
• Caminho euleriano em um grafo é o caminho que
usa cada aresta exatamente uma vez. Se tal cami-
nho existir, o grafo é chamado traversável. Um ciclo
12 CAPÍTULO 2. CONCEITOS BÁSICOS E DEFINIÇÕES
euleriano é um ciclo que usa cada aresta exatamente
uma vez.
• Caminho hamiltoniano em um grafo é o caminho
que visita cada vértice exatamente uma vez. Um
ciclo hamiltoniano é um ciclo que visita cada vér-
tice uma só vez. O grafo do exemplo contém um
caminho hamiltoniano. Enquanto determinar se um
dado grafo contém um caminho ou ciclo euleriano
é trivial, o mesmo problema para caminhos e ciclos
hamiltonianos é trabalhoso.
Ciclo (ou circuito) é um caminho que começa e acaba
com o mesmo vértice. Ciclos de comprimento 1 são la-
ços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ci-
clo de comprimento 6. Um ciclo simples é um ciclo que
tem um comprimento pelo menos de 3 e no qual o vértice
inicial só aparece mais uma vez, como vértice final, e os
outros vértices aparecem só uma vez. No grafo acima, (1,
5, 2, 1) é um ciclo simples. Um grafo chama-se