Este é o programa oficial da disciplina MAC0328 (Algoritmos em 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/2003
Estudo de problemas básicos da teoria dos grafos. Análise e desenvolvimento de algoritmos para esses problemas.
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.
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.
MAC0122 (Princípios de Desenvolvimento de Algoritmos)