MAC0328  Algoritmos em Grafos

Por | Em

OBJETIVOS:  Estudar algoritmos para problemas fundamentais em grafos.

PROGRAMA RESUMIDO:  Conexão de grafos e digrafos. Emparelhamentos máximos. Fluxo máximo. Coloração de vértices. Circuitos hamiltonianos. Tópicos opcionais.

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.

PRÉ-REQUISITOS:  MAC0121.

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: 

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

OBSERVAÇÃO:  Disciplina optativa eletiva no currículo do BCC.

 

[Veja dados da disciplina no JúpiterWeb]

Oferecimentos da disciplina: 1999/2, 2000/1, 2001/1.