Este é o programa oficial da disciplina MAC0320 (Introdução à Teoria dos Grafos). Confira no Sistema Júpiter.
Créditos Aula: 4
Créditos Trabalho: 0
Carga Horária Total: 60h
Tipo: Semestral
Ativação: 1/1/2010
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.
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.
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.
MAC0122 (Princípios de Desenvolvimento de Algoritmos)