MAC0320 Introdução à Teoria do Grafos

Por | Em

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:  MAC0121.

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]

Oferecimentos recentes da disciplina: 2009.