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.