A teoria dos grafos é usada na modelagem de muitos problemas computacionais. Esta disciplina tem o objetivo de introduzir o aluno à linguagem e aos problemas básicos da teoria. A disciplina complementa MAC0328 Algoritmos em Grafos, que trata dos aspectos mais algorítmicos da teoria.
Conceitos básicos da teoria dos grafos. Árvores. Grafos eulerianos. Grafos hamiltonianos. Emparelhamentos em grafos bipartidos. Coloração de arestas e de vértices. Teorema de Menger. Grafos planares.
Grafos. Isomorfismo. Caminhos e circuitos. Subgrafos. Cortes e pontes. Grafos conexos. Grafos bipartidos. Árvores. Grafos eulerianos. Grafos hamiltonianos. Emparelhamentos em grafos bipartidos. Coloração de arestas. Coloração de vértices. Teorema de Menger. Grafos planares.
Bibliografia Básica: J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, MacMillan, London, 1976. J. A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008. B. Bollobás, Modern Graph Theory, Springer-Verlag, 1998. P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos, 2004, «http://www.ime.usp.br/~pf/teoriadosgrafos/» Bibliografia Complementar: R. Wilson, Introduction to Graph Theory, 4rd.ed., Prentice Hall, 1996. D.B. West, Introduction to Graph Theory, 2nd. ed., Prentice Hall, 2001.
