MAC5770 Introdução à Teoria dos Grafos

Livros

Principais

John A. Bondy, U.S. Rama Murty, Graph Theory with Applications, Macmillan, 1976.
Clássico. Antigo, mas ainda muito bom. Murty visita o Brasil (especialmente a UNICAMP) com regularidade.
Robin J. Wilson, Introduction to Graph Theory, 4th.ed., Prentice Hall, 1996.

Jonathan Gross, Jay Yellen, Graph Theory and Its Applications, CRC Press, 1998.
P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Teoria dos Grafos: uma Introdução Sucinta, livro sobre alguns tópicos de teoria dos grafos, 2004.

Antigos clássicos

Claude Berge, The Theory of Graphs and Its Applications, Mathuen & John Wiley, 1962.
Berge nasceu em 1926 e morreu em 2002.
Frank Harary, Graph Theory, Addison-Wesley, 1972.
Harary nasceu em 1921 e morreu em 4/1/2005.

Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall, 1974.

Outros

Cláudio L. Lucchesi, Introdução à Teoria dos Grafos, IMPA, 1979.
Livro do 12.o Colóquio Brasileiro de Matemática.
Douglas B. West, Introduction to Graph Theory, 2nd. ed., Prentice Hall, 2001.
Dizem que a primeira edição tinha muitos erros. Não sei se foram todos corrigidos na segunda.
Gary Chartrand, Linda Lesniak, Graphs & Digraphs, 3rd. edition, Chapman & Hall, 1996.

Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory, CRC Press, 2003.
Ainda não conheço.
F. Buckley, M. Lewinter, A Friendly Introduction to Graph Theory, 2003.
Não li.
E. Goodaire, M. Parmenter, Discrete Math with Graph Theory, 3rd.ed., 2006.
Não li.

Livros mais avançados

Excelentes livros que vão além do nível de MAC5770:

Reinhard Diestel, GraphTheory, 2nd. ed., (Graduate Texts in Mathematics, 173), Springer, 2000.
Excelente. Usei na edição 2000 de MAC5827.
Béla Bollobás, Graph Theory: an Introductory Course, (Graduate Texts in Mathematics, 63), Springer-Verlag, 1979.
Clássico. Tem caráter mais matemático que os outros.
Béla Bollobás, Modern Graph Theory, (Graduate Texts in Mathematicas, 184), Springer-Verlag, 1998.
Edição ampliada do Graph Theory: an Introductory Course do mesmo autor. Discute conexões da teoria dos grafos com outros ramos da matemática.

Lásló Lovász, Combinatorial Problems and Exercises, 2nd. ed., North-Holland, 1993.
Aprenda teoria dos grafos fazendo exercícios! A segunda parte do livro traz as soluções de muitos dos exercícos. O livro foi escrito por um dos maiores matemáticos da atualidade.
László Lovász, Michael D. Plummer, Matching Theory, (Annals of Discrete Mathematics, 29), North-Holland, 1986.
Tudo sobre emparelhamentos e muito mais. Excelente! (Mas o índice remissivo poderia ser melhor...)

Livros de caráter mais algorítmico

Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
Shimon Even, Graph Algorithms, Computer Science Press, 1979.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 2nd edition, MIT Press & McGraw-Hill, 2001. [Veja também o sítio dos autores.]
Não é um livro de teoria dos grafos, mas as seções 5.4 e 5.5 e os capítulos 23 a 27 podem ser relevantes. Há uma edição em português (Algoritmos - Teoria e Prática, Campus, 2002), mas a tradução não é boa ("loop invariante" no lugar de loop invariant e outras bobagens).

Software

Em MAC5770, os algoritmos sobre grafos serão discutidos em nível alto de abstração, sem os detalhes de implementação. Mas há excelente material para os interessados em implementações:

Robert Sedgewick, Algorithms in C, 3rd. edition, part 5: Graph Algorithms, Addison-Wesley, 2002.
As figuras são excelentes. A organização do texto — nem tanto. O código dos programas tem um lamentável defeito: a documentação não diz o que cada função faz.

Donald E. Knuth, The Stanford GraphBase, ACM Press e Addison-Wesley, 1993.
O livro documenta o pacote de software Stanford GraphBase (SGB), que está instalado nas redes UNIX e Linux do IME. Veja o extended abstract [ps, pdf] que descreve o livro e o software. Veja também minha página sobre o SGB.

Catálogo on line da Biblioteca do IME-USP | Livrarias: Cultura, Amazon, Student Bookworld

URL of this site: http://www.ime.usp.br/~pf/mac5770-2005/
Last modified: Thu Dec 13 06:46:51 BRST 2012
Paulo Feofiloff
IME-USP