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: 

• R. Sedgewick, Algorithms in C (part 5: Graph Algorithms), 3rd ed., Addison-Wesley/Longman, 1998.
• D.E. Knuth, The Stanford GraphBase, Addison-Wesley, 1993.
• 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.
• 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.

OBSERVAÇÃO:  Disciplina obrigatória no currículo do BCC.

[Veja dados da disciplina no JúpiterWeb]