Sumário

Capítulo 1: Introdução

Capítulo 2: Principais noções
2.1 Definições iniciais
2.2 Definição geral de grafo e definições acessórias
2.3 Algumas considerações necessárias
2.4 Esquema e rotulação de um grafo
2.5 Valoração
2.6 Igualdade e isomorfismo
2.7 Partição de grafos
2.8 Representação de grafos
2.9 Operações com grafos
2.10 Relações de adjacência
2.11 Grafos simétrico, antissimétrico e completo
2.12 Grafo complementar de um grafo
2.13 Percursos em um grafo
2.14 Grafo de interseção, grafo adjunto, menor de um grafo
2.15 Grafos de Kneser, grafos-círculo, grafos-grade

Capítulo 3: Conexidade e conectividade
3.1 Discussão preliminar sobre conexidade
3.2 Tipos de conexidade
3.3 Componentes f-conexas
3.4 Dois resultados sobre f-conexidade
3.5 Grafo reduzido
3.6 Teoremas sobre conexidade
3.7 Algoritmos para decomposição por conexidade
3.8 Vértices peculiares em grafos não fortemente conexos
3.9 Discussão sucinta sobre aplicações
3.10 Conectividade e conjuntos de articulação
3.11 Pontos de articulação e antiarticulação

Capítulo 4: Distância, localização, caminhos
4.1 Conteúdo e importância
4.2 Teorema de Festinger e aplicações
4.3 Distância em um grafo
4.4 Centros, medianas, anticentros
4.5 Algumas generalizações e outras questões
4.6 Resultados relativos a raios e diâmetros
4.7 Grafos extremais de problemas de diâmetro
4.8 Problemas de caminho mínimo
4.9 Algoritmos de caminho mínimo
4.10 O problema do labirinto
4.11 O problema da exploração total
4.12 Partição de grafos em percursos

Capítulo 5: Grafos sem circuitos e sem ciclos
5.1 Grafos sem circuitos
5.2 O método PERT
5.3 O grafo potenciais-atividades
5.4 Outras questões referentes a grafos sem circuitos
5.5 Grafos sem ciclos: florestas e árvores
5.6 Outros problemas de árvores parciais
5.7 Bases de ciclos e de cociclos: coárvores
5.8 Fatoração em árvores e arboricidade
5.9 Grafos sem ciclos: arborescências
5.10 Problemas de enumeração e contagem
5.11Problemas e resultados correlacionados

Capítulo 6: Alguns problemas de subconjuntos de vértices
6.1 Introdução
6.2 Conjuntos independentes
6.3 Partição cromática e número cromático
6.4 Dominância
6.5 Outros critérios para dominância; irredundância
6.6 Aplicações da dominância simples
6.7 Núcleo de um grafo

Capítulo 7: Fluxos em grafos
7.1 Introdução
7.2 O modelo linear de fluxo
7.3 O problema do fluxo máximo
7.4 Temas relacionados à maximização do fluxo
7.5 Fluxos em grafos com limites inferiores quaisquer
7.6 O problema do fluxo de custo mínimo
7.7 Fluxo dinâmico ou θ-fluxo
7.8 Algumas aplicações

Capítulo 8: Acoplamentos
8.1 Introdução
8.2 O problema do acoplamento máximo
8.3 Acoplamentos em grafos bipartidos
8.4 Acoplamentos em grafos quaisquer
8.5 Uso de técnicas de fluxo
8.6 O problema do b-acoplamento
8.7 Existência de um acoplamento perfeito
8.8 Aplicações
8.9 Alguns resultados

Capítulo 9: Percursos abrangentes
9.1 Introdução
9.2 Existência de percursos abrangentes para ligações
9.3 O Problema do Carteiro Chinês
9.4 Problemas hamiltonianos
9.5 O Problema do Caixeiro-Viajante

Capítulo 10: Grafos planares e temas correlacionados
10.1 Introdução
10.2 Algumas definições e resultados
10.3 Caracterização da planaridade
10.4 Outras questões envolvendo planaridade
10.5 Grafos planares hamiltonianos
10.6 Algoritmos para caracterização da planaridade
10.7 O teorema das quatro cores
10.8 O problema grau máximo-diâmetro em grafos planares
10.9 Grafos quaseplanares
10.10 Menores percursos disjuntos em grafos planares
10.11 O número de grafos não imersíveis em outras superfícies

Capítulo 11: Extensões do problema de coloração
11.1 Introdução
11.2 Invariantes de vértices
11.3 Coloração de arestas
11.4 Números cromáticos total e geral, outros critérios de coloração
11.5 Polinômios cromáticos
11.6 Grafos perfeitos
11.7 O problema da T-coloração

Capítulo 12: Alguns temas selecionados
12.1 Introdução
12.2 Operações binárias com grafos
12.3 Introdução à teoria espectral de grafos
12.4 Indices topológicos
12.5 Centralidades em grafos
12.6 Vulnerabilidade em grafos
12.7 O uso de software investigativo em grafos
12.8 Problemas de roteamento
12.9 Traçado de grafos
12.10 Jogos em grafos
12.11 A expansão das aplicações
12.12 As grandes redes