Teoria dos Grafos:
uma introdução sucinta

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. 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 to texto é mais matemático que computacional. 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. Material neste sítio Este sítio contém o seguinte material: Versão atualizada do livro (pdf) Transparências: aulas 1 e 2 (pdf) aula 3 (ps) Bibliografia Recursos na teia WWW Pequeno dicionário de termos técnicos Para ler os arquivos pdf, você deve dispor de software apropriado, como o  Acrobat Reader (veja "Downloads" para instalar o software)  ou o  GNU/Linux gpdf.

Conteúdo do livro 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. Introdução 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 Conjuntos estáveis, cliques e coberturas Coloração de vértices Emparelhamentos Coloração de arestas Pequeno dicionário de termos técnicos