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.
Grafos. Isomorfismo. Caminhos e circuitos. Subgrafos. Cortes e pontes. Grafos conexos. Árvores. Grafos aresta-biconexos. Grafos bipartidos. Grafos eulerianos. Grafos hamiltonianos. Emparelhamentos em grafos bipartidos. Conjuntos estáveis e cliques. Coloração de arestas. Coloração de vértices. Noções de planaridade.
Bibliografia Básica: 1. J. A. Bondy, U.S.R. Murty, Graph Theory with Applications, MacMillan, London, 1976. 2. J. A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008. 3. B. Bollobás, Modern Graph Theory, Springer-Verlag, 1998. 4. P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos, 2004. Disponível em: http://www.ime.usp.br/~pf/teoriadosgrafos/ Bibliografia Complementar: 1. R. Wilson, Introduction to Graph Theory, 4rd ed., Prentice Hall, 1996. 2. D.B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001.
