MAC0328: Ementa oficial
Esta é a ementa oficial da disciplina
MAC0328 (Algoritmos em Grafos)
para 2016.
Objetivos
Estudar algoritmos para problemas fundamentais em grafos.
Programa
-
Conexão de grafos: componentes, grafos biconexos.
-
Digrafos fortemente conexos
(algoritmo de Kosaraju-Sharir,
algoritmo de Tarjan).
-
Emparelhamentos máximos em grafos bipartidos.
-
Emparelhamentos em grafos arbitrários (algoritmo de Edmonds).
-
Fluxo máximo (algoritmo de Ford-Fulkerson).
-
Coloração de vértices.
-
Circuitos hamiltonianos.
-
Tópicos opcionais: link analysis, network analysis, redes aleatórias.
Carga horária semanal e número de créditos
Créditos Aula: 4
Carga Horária Total: 60h
Tipo: Semestral
Ativação: 1/1/2015
Critério de avaliação
Média ponderada de provas e exercícios.
Bibliografia
-
J.A. Bondy, U.S. Rama Murty,
Graph Theory,
Springer, 2007.
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
Introduction to Algorithms, 3rd ed.,
McGraw-Hill, 2009.
-
D. Easley, J. Kleinberg,
Networks, Crowds, and Markets:
Reasoning About a Highly Connected World,
Cambridge University Press, 2010.
-
D.E. Knuth,
The Stanford GraphBase,
Addison-Wesley, 1993.
-
D. Joyner, M. Van Nguyen, N. Cohen,
Algorithmic Graph Theory,
http://code.google.com/p/graph-theory-algorithms-book/,
Google Code, 2010.
-
R. Sedgewick,
Algorithms in C (part 5: Graph Algorithms), 3rd ed.,
Addison-Wesley/Longman, 1998.
-
R. Sedgewick, K. Wayne,
Algorithms, 4th. ed.,
Addison-Wesley, 2011.
-
M. van Steen,
Graph Theory and Complex Networks: An Introduction,
Maarten van Steen, 2010.
Pré-Requisitos