Uma Introdução Sucinta à
Teoria dos Grafos

Paulo Feofiloff
Yoshiharu Kohayakawa
Yoshiko Wakabayashi

Este é o sítio do livro Uma Introdução Sucinta à Teoria dos Grafos, originalmente escrito para um minicurso na II Bienal da SBM realizado em Salvador de 25 a 29 de outubro de 2004 sob os auspícios da Sociedade Brasileira de Matemática.

Os autores do livro — Yoshiko, Yoshiharu e Paulo — são professores do Departamento de Ciência da Computação do Instituto de Matemática e Estatística da Universidade de São Paulo.

A Teoria dos Grafos estuda objetos combinatórios conhecidos como grafos. O livro pretende introduzir o leitor aos problemas, aos métodos, e à linguagem dessa teoria.  O enfoque do texto é mais matemático que computacional.

Muitos problemas sobre grafos tornaram-se célebres porque ocorrem em diversas áreas da matemática, da informática, e em muitas aplicações industriais. O livro procura introduzir a teoria dos grafos examinando quatro problemas intimamente relacionados: os problemas dos conjuntos estáveis, dos emparelhamentos, da coloração de vértices e da coloração de arestas. Ao longo da discussão desses problemas, o livro procura indicar a relação da teoria dos grafos com ramos clássicos da matemática como a álgebra linear, a álgebra abstrata e a teoria da probabilidade.

Conteúdo do livro

1. Prefácio
2. Conceitos básicos
   • Grafos
   • Alguns exemplos de grafos
   • Isomorfismo
   • Vizinhanças, cortes e graus
   • Caminhos e circuitos
   • Subgrafos
   • Grafos conexos e componentes
   • Grafos aleatórios
3. Conjuntos estáveis, cliques e coberturas
4. Coloração de vértices
5. Emparelhamentos
6. Coloração de arestas
7. Pequeno dicionário de termos técnicos

Conteúdo deste sítio

• Livro  Uma Introdução Sucinta à Teoria dos Grafos   [PDF]
• Índice remissivo do livro
• Transparências: aulas 1 e 2 (pdf) aula 3 (ps)
• Dicionário de termos técnicos
• Outros livros de teoria dos grafos
• Recursos de teoria dos grafos na teia WWW

Busca no sítio Teoria dos Grafos