MAC-328 ALGORITMOS EM GRAFOS

• OBJETIVOS: Estudo de problemas básicos da teoria dos grafos. Análise e desenvolvimento de algoritmos para esses problemas.

• CONTEÚDO: 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: MAC-122.

• CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos.

• 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.