Prof. Carlos Martinhon -
IC/UFF
|
Disciplina de Algoritmos em Grafos
a)
Programa:
- Conceitos e definições
de grafos: Adjacência, incidência,
caminhos, ciclos, diâmetros, diâmetro, grau, subgrafo
gerador e induzido, conexidade, árvores, grafos orientados;
- Representação
de Grafos: Matrizes de
adjacência, matriz de incidência e lista de Adjacências.
Vantagens e desvantagens de cada representação.
- Busca em grafos: Busca em largura, busca em profundidade,
determinação dos componentes fortemente conexos,
ordenação topológica.
- Árvore geradora mínima:
Definição.
Algoritmos de Kruskal, Prim e Sollin.
- Caminhos
Mínimos: Definição.
Algoritmos de Dijkstra, Floyd, Belman Moore d´Esopo.
- Fluxo máximo e multifluxo:
Definição
de Rede Residural, Algoritmo de Ford-Fulkerson. Teorema de corte
mínimo e fluxo máximo.
- Fluxo
de custo mínimo: Algoritmo
dos ciclos de custo negativo, Algoritmo de Busacken e Gowen.
|
b)
Bibliografia:
- T. H. Cormem, C. E. Leiserson, R. L. Rivest,
C. Stein [2002], Introduction to Algorithms (Second
Edition), MIT Press and McGraw-Hill.
- R. K. Ahuja, T. L. Magnanti, J. B. Orlin [1993], Network
Flows: Theory, Algorithms and Applications, Prentice Hall.
- M. Syslo, N. Deo, J. Kowalik [1983], Discrete Optimization Algorithms with
Pascal Programs, Prentice Hall.
|
c) Outros:
- Avaliação: Total de 2 provas e um trabalho de
implementação: (peso das provas 4,5 - peso do trabalho
1).
Aprovação acima de
6,0.
- Listas de Exercícios (em PDF):
Lista1, Lista 2
- Notas (2o Semestre -
200?).
- Trabalhos de
implementação
- Tópicos interessantes
|