6898 Algoritmos em Grafos

Nesta disciplina vamos estudar definições, propriedades e algoritmos em grafos.

Veja o [programa](http://www.din.uem.br/graduacao/programas-e-criterios/6898-Algoritmos em Grafos-2013.pdf) e o [critério de avaliação](http://www.din.uem.br/graduacao/programas-e-criterios/6898-Algoritmos em Grafos-crit 2013.pdf) da disciplina.

Os alunos desta disciplina devem inscrever-se no grupo uem-grafos para receberem informações e discutirem o conteúdo da disciplina. Por favor, use o seu nome verdadeiro na lista para o professor poder identificá-lo.

Avaliações

• Exame
  • 26/06 - Prova escrita (conteúdo: primeira e segunda parte)
• 3° avaliação (peso 4)
  • 07/06 - Prova escrita (conteúdo: segunda parte).
• 4° avaliação (peso 1)
  • 16/06 - Trabalho graphard.
• 1° avaliação (peso 4)
  • 10/04 - Prova escrita (conteúdo: primeira parte).
• 2° avaliação (peso 1)
  • 05/05 - Trabalho grafun.

Material

O livro base para esta disciplina é Algoritmos: Teoria e Prática, 3ª edição.

Os materiais utilizados em sala de aula estão disponíveis para download logo abaixo. O estudo utilizando apenas este material não é suficiente para o acompanhamento da disciplina. Recomendamos a leitura das referências no final de cada apresentação e a resolução (por parte do aluno) de todos os exercícios listados no material.

Aulas

Segunda parte

• Caminhos mínimos de todos os pares (19/04)
• Caminho euleriano e o problema do carteiro chinês (Material professor Ademir) (24/06 e 26/06)
• Caminho hamiltoniano e o problema do caixeiro viajante (Material professor Ademir) (03/05 e 08/05)
• Implementação do trabalho (10/05 e 15/05)
• Grafos planares (17/05)
• Implementação do trabalho (22/05)
• Correção do trabalho 1 (25/05)
• Fluxo em redes (29/05 e 05/06)
• Implementação do trabalho (07/06)
• Implementação do trabalho (reposição da aula do dia 12/04) (10/06)
• 2° avaliação (12/06)
• Resolução da 2° avaliação (reposição da aula do dia 31/05) (17/06)

Primeira parte

• Apresentação da disciplina (06/02)
• Introdução (histórico, definições e propriedades) (08/02, 15/02)
• Representações computacional - Exemplo simples de implementação (20/02, 22/02, 27/02)
• Busca em largura (01/03)
• Busca em profundidade (06/03)
• Ordenação topológica (08/03)
• Componentes fortemente conexos (13/03)
• Exercícios (15/03)
• Árvores geradoras mínimas (20/03 e 22/03)
• Apresentação do trabalho (27/03)
• Caminhos mínimos de única origem (03/04 e 05/04)
• 1° avaliação (10/04)
• Resolução da 1° avaliação (17/04)