Pré-requisito: Estrutura de Dados I.
Carga horária: 60h.

EMENTA:

  • Funções Geradoras.
  • Relações de Recorrência.
  • Teoria dos Grafos – Conceitos Básicos.
  • Grafos e Subgrafos.
  • Conectividade.
  • Representações.
  • Listas e Matrizes de Adjacências.
  • Árvores e Florestas.
  • Grafos e Árvores Geradoras.
  • Circuitos Eulerianos.
  • Ciclos Hamiltoniano.
  • Emparelhamento em Grafos.
  • Cliques e Conjuntos Independentes.
  • Número e Índice Cromático.
  • Coloração de Vértices e Arestas.
  • Planaridade.
  • Grafos Direcionados.
  • Classes de Grafos e Caracterizações.
  • Método de Busca em Largura.
  • Busca em Profundidade.
  • Busca em Largura Lexicográfica.
  • Algoritmos de Caminho Mínimo.
  • Algoritmos de Fluxo Máximo e Multifluxo.
  • Algoritmos de Fluxo de Custo Mínimo e Aplicações.

 

BIBLIOGRAFIA BÁSICA:
1.T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Algoritmos – Tradução da 2a Edição Americana – Teoria e Prática. Ed. Campus, 2002.
2.J.L. Szwarcfiter. Grafos e Algoritmos Computacionais. Ed. Campus, 1986.
3.J.P.O. Santos, M.P. Mello, I.T.C. Murari. Introdução à Análise Combinatória. UNICAMP, 2002.
 
BIBLIOGRAFIA COMPLEMENTAR:
1.J.A. Bondy, U.S.R. Murty. Graph Theory with Applications. Elsevier, 1982.
2.P.O. Boaventura Netto. Grafos: Teoria, Modelos, Algoritmos. 4a Ed., Edgard Blucher,2006.
3.N. Maculan Filho, R.E. Campello. Algoritmos e Heurísticas: Desenvolvimento e Avaliação de Performance. Niterói: Editora da UFF, 1994.
4.A. Gibbons. Algorithmic Graph Theory. Cambridge University Press, 1985.