TEORIA COMPUTACIONAL DE GRAFOS

Notação
Índice de Algoritmos
Índice de Programas
Lista de Figuras
1 Introdução
	1.1 Breve Descrição do Conteúdo
	1.2 Os Grafos: Um Pouco de História
	1.3 Apresentação dos Algoritmos
	1.4 Complexidade de Algoritmos
	1.5 Estruturas de Dados
	1.6 A Linguagem Python
	1.7 Implementações
	1.7.1 Algoritmo 1.3: Ordenação de Sequências
	1.8 Exercícios
	1.9 Notas Bibliográficas
2 Uma Iniciação à Teoria dos Grafos
	2.1 Introdução
	2.2 Os Primeiros Conceitos
	2.3 Árvores
	2.4 Conectividade
	2.5 Planaridade
	2.6 Ciclos Hamiltonianos
	2.7 Coloração
	2.8 Grafos Direcionados
	2.9 Representação de Grafos
	2.10 Implementações em Python: Operações Básicas
	2.10.1 Algoritmo 2.1: Centro de Árvore
	2.11 Exercícios
	2.12 Notas Bibliográficas
3 Técnicas Básicas
	3.1 Introdução
	3.2 Processo de Representação
	3.3 Adjacências
	3.4 Ordenação de Vértices ou Arestas
	3.5 Coloração Aproximada
	3.6 Ordenação Topológica
	3.7 Recursão
	3.8 Árvores de Decisão
	3.9 Limite Inferior para Ordenação
	3.10 Programas em Python
	3.10.1 Algoritmo 3.3: Coloração Aproximada
	3.10.2 Algoritmo 3.4: Ordenação Topológica
	3.11 Exercícios
	3.12 Notas Bibliográficas
4 Buscas em Grafos
	4.1 Introdução
	4.2 Algoritmo Básico
	4.3 Busca em Profundidade
	4.4 Biconectividade
	4.5 Busca em Profundidade – Digrafos
	4.6 Componentes Fortemente Conexas
	4.7 Busca em Largura
	4.8 Busca em Largura Lexicográfica
	4.9 Reconhecimento dos Grafos Cordais
	4.10 Busca Irrestrita
	4.11 Programas em Python
	4.11.1 Algoritmo 4.2: Busca em Profundidade
	4.11.2 Algoritmo 4.4: Busca em Profundidade em Digrafos
	4.11.3 Algoritmo 4.5: Componentes Fortemente Conexas
	4.11.4 Algoritmo 4.6: Busca em Largura
	4.11.5 Algoritmo 4.7: Busca em Largura Lexicográfica
	4.11.6 Algoritmo 4.8: Busca Irrestrita
	4.12 Exercícios
	4.13 Notas Bibliográficas
5 Outras Técnicas
	5.1 Introdução
	5.2 Algoritmo Guloso
	5.3 Árvore Geradora Mínima
	5.4 Programação Dinâmica
	5.5 Particionamento de Árvores
	5.6 Alteração Estrutural
	5.7 Número Cromático
	5.8 Programas em Python
	5.8.1 Algoritmo 5.1: Árvore Geradora Mínima
	5.8.2 Algoritmo 5.2: Particionamento de Árvore
	5.8.3 Algoritmo 5.3: Número Cromático
	5.9 Exercícios
	5.10 Notas Bibliográficas
6 Fluxo Máximo em Redes
	6.1 Introdução
	6.2 O Problema do Fluxo Máximo
	6.3 O Teorema do Fluxo Máximo – Corte Mínimo
	6.4 Um Primeiro Algoritmo
	6.5 Um Algoritmo O(nm2)
	6.6 Um Algoritmo O(n2m)
	6.7 Um Algoritmo O(n3)
	6.8 Programas em Python
	6.8.1 Algoritmo 6.1: Fluxo Máximo
	6.8.2 Algoritmo 6.3: Fluxo Máximo - Rede de Camadas
	6.9 Exercícios
	6.10 Notas Bibliográficas
7 Caminhos Mínimos
	7.1 Introdução
	7.2 As Equações de Bellman
	7.3 Algoritmo de Dijkstra
	7.4 O Algoritmo de Bellman-Ford
	7.5 O Algoritmo de Floyd
	7.6 k -ésimos Caminhos Mínimos
	7.7 k -ésimos Caminhos Mínimos Simples
	7.8 Detecção de ciclos negativos
	7.9 Programas em Python
	7.9.1 Algoritmo 7.1: Dijkstra
	7.9.2 Algoritmo 7.2: Bellman–Ford
	7.9.3 Algoritmo 7.3: Floyd
	7.9.4 Algoritmo 7.4: k -ésimo mínimo (passeio)
	7.9.5 Algoritmo 7.5: k -ésimo mínimo (caminho simples)
	7.9.6 Algoritmo 7.6: Detecção de Ciclos Negativos
	7.10 Exercícios
	7.11 Notas Bibliográficas
8 Emparelhamentos Máximos em Grafos
	8.1 Introdução
	8.2 Emparelhamentos Perfeitos
	8.3 Caminhos Alternantes
	8.4 Grafos Bipartidos sem Pesos: Cardinalidade Máxima
	8.5 O Método Húngaro
	8.6 Emparelhamentos e Coberturas por Vértices
	8.7 Grafos Bipartidos Ponderados
	8.8 Grafos Gerais sem Peso
	8.9 Programas em Python
	8.9.1 Algoritmo 8.1: Emparelhamento Bipartido (com Digrafo)
	8.9.2 Algoritmo 8.2: Emparelhamento Bipartido (Método Húngaro)
	8.9.3 Algoritmo 8.3: Emparelhamento Bipartido Ponderado
	8.9.4 Algoritmo 8.4: Emparelhamento Geral
	8.10 Exercícios
	8.11 Notas Bibliográficas
9 Problemas NP-Completos
	9.1 Introdução
	9.2 Problemas de Decisão
	9.3 A Classe P
	9.4 Alguns Problemas Aparentemente Difíceis
	9.5 A Classe NP
	9.6 A Questão P = NP
	9.7 Complementos de Problemas
	9.8 Transformações Polinomiais
	9.9 Alguns Problemas NP-Completos
	9.10 Restrições e Extensões de Problemas
	9.11 Algoritmos Pseudopolinomiais
	9.12 Complexidade de um Problema Numérico
	9.13 Programas em Python
	9.13.1 Algoritmo 9.1: Subconjunto Soma
	9.14 Exercícios
	9.15 Notas Bibliográficas
Referências
Posfácio