Este é o programa oficial da disciplina MAC5770 (Introdução à Teoria dos Grafos), versão 5 (ativada em 27/1/2011). Confira no sistema Janus.
Total: 120 h
Teórica: 4 h
Prática: 2 h
Estudos: 4 h
Créditos: 8
Duração: 12 semanas
Introduzir o estudante aos problemas e métodos e à linguagem da teoria dos grafos.
Esta é uma disciplina básica para as áreas de Teoria da Computação, Combinatória e Otimização Combinatória.
Grafos. Isomorfismo. Caminhos e circuitos. Subgrafos. Cortes e pontes. Grafos conexos. Grafos eulerianos. Árvores. Emparelhamentos em grafos bipartidos. Teorema de Menger. Grafos hamiltonianos. Conjuntos estáveis e cliques. Coloração de arestas. Coloração de vértices. Noções de planaridade.
1. B. Bollobás, Modern Graph Theory, Springer-Verlag, 1998.
2. J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008.
3. R. Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, 173.
Springer-Verlag, Berlin, 2005.
4. P. Feofiloff, Exercícios de Teoria dos Grafos, 2009,
http://www.ime.usp.br/~pf/grafos-exercicios/
5. P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi,
Uma Introdução Sucinta à Teoria dos Grafos, 2004,
http://www.ime.usp.br/~pf/teoriadosgrafos/
6. R. Wilson, Introduction to Graph Theory, 4th ed., Prentice Hall, 1996.
Listas de exercícios e provas