MAC5770  Introdução à Teoria dos Grafos

Livros

Principais

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.

    Por algum motivo, não gosto muito...

  • Ronald J. Gould,
    Graph Theory,
    Benjamin/Cummings, 1988.

    Não gosto muito. Entre outras coisas, por causa dos erros.

  • Jonathan L. Gross, Jay Yellen,
    Handbook of Graph Theory,
    CRC Press, 2003.

    Ainda não conheço.

Antigos clássicos

  • Claude Berge,
    The Theory of Graphs and Its Applications,
    Mathuen & John Wiley, 1962.
  • Frank Harary,
    Graph Theory,
    Addison-Wesley, 1972.

    Harary nasceu em 1921 e faleceu em 4/1/2005.

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

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.  Tenho uma cópia local.

  • 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 muitas 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...)

 

cover of Wilson cover of Bollobas cover of Wilson's book cover of Sedgewick, part 5


Algoritmos

Os livros da lista abaixo têm um caráter mais algorítmico que os outros.

  • 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

Os detalhes da implementação dos algoritmos não receberão muita atenção em MAC5770. Mas existe excelente material para os interessados no assunto:

  • 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.  •  Copiei o código de todos os programas.

  • 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.

  • LINK: A Software System for Discrete Mathematics. Desenvolvido no DIMACS.

Como escrever matemática

Uma das finalidades secundárias de MAC5770 é desenvolver a habilidade de argumentar com precisão, ou seja, a habilidade de escrever "provas matemáticas".  Eis alguns livros que podem ajudar:

  • Frank M. Steward,
    Introduction do Linear Algebra,
    Van Nostrand, 1963.

    Os apêndices do livro são muito bons!

  • Daniel J. Velleman,
    How to Prove It,
    Cambridge University Press, 1994.
  • Nicholas J. Higham,
    Handbook of Writing for the Mathematical Sciences,
    SIAM, 1993.
  • Donald E. Knuth, Tracy Larrabee, Paul M. Roberts,
    Mathematical Writing,
    MAA, 1989.
  • Norman E. Steenrod, Paul R. Halmos, Menahem M. Schiffer, Jean A. Dieudonné,
    How to Write Mathematics,
    AMS, 1973.
  • E.W. Dijkstra,
    "The notational conventions I adopted, and why",
    manuscrito.
  • Imre Lakatos,
    Proofs and Refutations,
    Cambridge University Press, 1976.

    Trata da questão "O que é uma prova?". Vai longe demais para as necessidades de MAC5770, mas é muito interessante.

Miscelânea

  • Michel Goossens, Sebastian Rahtz,
    The LaTeX Web Companion: Integrating TeX, HTML, and XML,
    Addison Wesley Longman, 1999.
  • Thomas Merz,
    Web Publishing with Acrobat/PDF,
    Springer-Verlag, 1998.

 


Catálogo on line da Biblioteca do IME-USP   |   Livrarias:  Cultura, Amazon
URL of this site: www.ime.usp.br/~pf/mac5770-2004/
Last modified: Fri Dec 2 10:24:30 BRST 2005
Paulo Feofiloff
IME-USP