Algoritmos
em Grafos - TCC-00.284
Segundo Período de 2017 - Turma A-1
Prof. Fábio Protti - fabio@ic.uff.br
Horário e Local
Segundas e
quartas, das 9:00 às 11:00
Sala 204
Programa da disciplina
Introdução a grafos.
Definições básicas. Conceitos importantes de Teoria de Grafos. Grafos como
estruturas de dados.
Grafos Eulerianos. Algoritmo para Trilhas Eulerianas.
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.
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.
Emparelhamentos.
Algoritmo dos caminhos aumentantes. Método Húngaro
para emparelhamentos em grafos bipartidos.
O Problema do
Caixeiro Viajante (PCV). Algoritmo exato para o PCV. Algoritmos aproximativos
para o PCV.
Estrutura do Curso
Aulas Teóricas.
Lista de
exercícios sugeridos (não são para entregar, mas recomendo a resolução).
Exercícios de
implementação (não são para entregar).
Calendário de Provas
Primeira Prova:
dia 9 de outubro de 2017
Segunda Prova:
dia 29 de
novembro de 2017
Segunda
Chamada: dia 6
de dezembro de 2017 (só para
quem perdeu P1 ou P2 - abrange todo o conteúdo da disciplina!)
VS: dia 13 de dezembro
de 2017
Trabalho
Entrega: até
dia 3 de
dezembro
Enviar por e-mail:
·
membros da equipe
·
código fonte do programa
·
código executável do programa
(ou explicação de como executar)
Avaliação
Seja M = max{ (2*P1+2*P2+T)/5 ,
(P1+P2)/2 }
Se M >= 6,0,
o aluno está aprovado.
Se M < 4,0,
o aluno está reprovado.
Se 4 <= M
< 6,0, o aluno deve fazer a VS.
A nota da VS deverá ser
maior ou igual a 6,0.
Exercícios de
implementação (não são para entregar)
Use o site http://uva.onlinejudge.org
A linguagem de
implementação pode ser Pascal, C, C++ ou
Java.
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.
Downloads
Aula Inicial sobre Aplicações em Grafos
Conceitos Introdutórios sobre Grafos