MAC0320 Introdução à Teoria do Grafos
OBJETIVOS: 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.
RESPONSÁVEIS: Paulo Feofiloff, Yoshiharu Kohayakawa e Yoshiko Wakabayashi.
PROGRAMA: 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.
PRÉ-REQUISITOS: MAC0122.
CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-trabalho.
CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.
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.
- P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos, 2004, «http://www.ime.usp.br/~pf/teoriadosgrafos/»
- R. Wilson, Introduction to Graph Theory, 4rd.ed., Prentice Hall, 1996.
- B. Bollobás, Modern Graph Theory, Springer-Verlag, 1998.
- D.B. West, Introduction to Graph Theory, 2nd. ed., Prentice Hall, 2001.
OBSERVAÇÃO: Disciplina optativa eletiva no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]