MAC0328 Algoritmos em Grafos
OBJETIVOS: Estudo de problemas básicos da teoria dos grafos. Análise e desenvolvimento de algoritmos para esses problemas.
PROGRAMA: Grafos: estruturas de dados para representação de grafos. Caminhos de comprimento mínimo. Árvores: árvores geradoras de grafos. Grafos conexos: componentes e cortes. Grafos biconexos: pontes, circuitos. Grafos orientados: grafos fortemente conexos. Emparelhamentos: emparelhamentos máximos em grafos bipartidos. Introdução ao problema do fluxo máximo. Alguns problemas difíceis: coloração de vértices, coloração de arestas, circuitos hamiltonianos.
PRÉ-REQUISITOS: MAC0122.
CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.
CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.
BIBLIOGRAFIA BÁSICA:
- D.E. Knuth, The Stanford GraphBase, Addison-Wesley, 1993.
- J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
- B. Bollobás, Graph Theory: an Introductory Course, Springer Verlag, 1979.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 1990.
BIBLIOGRAFIA ADICIONAL (ainda não consta no Júpiter):
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 2nd ed., McGraw-Hill, 2001.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Algoritmos: Teoria e Prática, Campus, 2002.
OBSERVAÇÃO: Disciplina obrigatória no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]