Algoritmos em Grafos (2016)
Horário: Segundas e Quartas das 09:00 às 11:00
Local: sala 204
Monitor: Alan Diego (aaurelio@ic.uff.br)
Programa do Curso
- Introdução a grafos. Definições básicas. Conceitos importantes de Teoria de Grafos. Grafos como estruturas de dados.
- Busca em profundidade em grafos. Algoritmo para determinar articulações e blocos de um grafo.
- Conceito de digrafo (grafo direcionado). Busca em profundidade em digrafos.
- Algoritmo para determinar componentes fortemente conexas de um digrafo.
- Busca em largura em grafos. Algoritmo de Dijkstra para caminhos mínimos em digrafos.
- Grafos Eulerianos. Algoritmo para Trilhas Eulerianas.
- Algoritmo de Floyd-Warshall para caminhos mínimos entre todos os pares de vértices de um digrafo.
- Programação Dinâmica para caminhos mínimos.
- Algoritmos de Kruskal e Prim para determinação de árvores geradoras mínimas.
- Algoritmos de ordenação topológica de um dígrafo acíclico.
- Fluxos em redes.
- Problema do Carteiro Chinês
Bibliografia
1) Jayme L. Szwarcfiter. Grafos e Algoritmos Computacionais. Campus, Rio de Janeiro, 1986. 2) Alan Gibbons. Algorithmic Graph Theory. . Cambridge University Press, 1985. 3) T. H. Cormen e outros. Algoritmos (tradução da 2a. Edição Americana). Campus, RJ, 2002.Listas
Notas da P2, VR e Ponto extra das listas
Material Complementar
-
Slides da aula
- (Aula Inicial sobre Aplicações em Grafos)
- (Definições)
- (Slides) Livro sobre Teoria dos Grafos: J.A.Bondy and U.S.R.Murty, Graph Theory with Applications, North-Holland, 1976
- http://book.huihoo.com/pdf/graph-theory-With-applications/pdf/GTWA.pdf
- http://www.math.ualberta.ca/~nastos/m322/GTWA.pdf
- http://www.iro.umontreal.ca/~hahn/IFT3545/GTWA.pdf
(This book is out of print. Students are asked to download their personal copy from the web pages:)