Grafos são estruturas matemáticas que podem ser usadas para modelar muitos problemas computacionais. Esta disciplina tem o objetivo de introduzir o aluno à linguagem e aos problemas e teoremas básicos da teoria de grafos. Esta disciplina complementa a disciplina MAC0328 - Algoritmos em Grafos, que trata dos aspectos mais algorítmicos de vários problemas sobre grafos.
Conceitos básicos da teoria dos grafos. Árvores. Grafos eulerianos. Grafos hamiltonianos. Emparelhamentos. Coloração de arestas e de vértices. Teorema de Menger. Grafos planares
Grafos. Isomorfismo. Caminhos e circuitos. Subgrafos. Cortes e pontes. Grafos bipartidos (caracterização). Árvores. Grafos eulerianos. Grafos hamiltonianos. Emparelhamentos (Teorema de Berge, Teorema de Hall, Teorema min-max de König). Coloração de arestas. Coloração de vértices. Teorema de Menger. Grafos planares (Fórmula de Euler, Teorema de Kuratowski).
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.
