Sumário

Capítulo 1: Primeiras ideias

1.1 Um rápido histórico

1.2 Um ponto muito importante: o modelo

1.3 Os modelos de grafo

1.4 Matemática discreta, computação e algoritmos



Capítulo 2: Conceitos básicos de grafos

2.1 Rotulação e representação de grafos

2.2 Alguns conceitos importantes

2.3 Alguns grafos especiais

2.4 Conexidade

2.5 Conectividade

Exercícios



Capítulo 3: Problemas de caminhos

3.1 Problemas de caminho mínimo

3.2 Algorítmos para achar caminhos mínimos

3.3 Uma aplicação a problemas de localização

3.4 Problemas de caminho máximo

Exercícios



Capítulo 4: Problemas de interligação

4.1 Árvores e arborescências

4.2 Árvores e interligação

4.3 O problema da árvore parcial de custo mínimo

4.4 Algoritmos gulosos

4.5 A questão da complexidade

4.6 Outros problemas de interligação

Exercícios



Capítulo 5: Subconjuntos especiais

5.1 Subconjuntos independentes

5.2 Expressão de problemas de subconjuntos de grafos por programação linear inteira

5.3 Conjuntos dominantes

5.4 Acoplamentos

5.5 Acoplamentos em grafos bipartidos

5.6 O problema de alocação linear – o algorítmo húngaro

5,7 O problema do transporte

5.8 Transporte com baldeação

Exercícios



Capítulo 6: Problemas de coloração

6.1 Coloração de vértices

6.2 Coloração de arestas

Exercícios



Capítulo 7: Fluxos em grafos

7.1 Introdução

7.2 Um exemplo simples

7.3 De quais fluxos estaremos falando?

7.4 Um pouco de formalização

7.5 O problema do fluxo máximo como um PLI

7.6 O problema do fluxo máximo

7.7 O teorema de Ford e Fulkerson

7.8 Grafo de aumento de fluxo, ou grafo de folgas

7.9 Fluxos com custo

7.10 Problemas práticos associados ao problema de fluxo com custo

Exercícios



Capítulo 8: Ciclos e aplicações

8.1 Problemas eulerianos em grafos não orientados

8.2 O problema do carteiro chinês

8.3 Problemas eulerianos em grafos orientados

8.4 Exemplos completos

8.5 Problemas hamiltonianos

8.6 O problema do caixeiro-viajante

Exercícios



Capítulo 9: Grafos planares

9.1 Definições e resultados simples

9.2 Teorema de Kuratowski

9.3 Dualidade

9.4 O problema das 4 cores

Exercícios

Referências

Índice remissivo