Grafos

 Aulas:

• Aula 00: Apresentação da Disciplina:
  • [download dos slides];

• Aula 01: Introdução e História dos Grafos.

[download dos slides]   [download da vídeo aula]

• Aula 02: Introdução - Conceitos básicos

[download dos slides]   [download da vídeo aula]

• Aula 03: Introdução - Representação computacional

[download dos slides]   [download da vídeo aula]

• Aula 04: Busca em Profundidade (DFS)

[download dos slides]   [download da vídeo aula]

• Aula 05: Busca em Largura (BFS)

[download dos slides]   [download da vídeo aula]

• Aula 06: Propriedades da BFS e da DFS

[download dos slides]   [download da vídeo aula]

• Aula 07: Trabalho prático 01

[download dos slides]   [download da vídeo aula]

• Aula 08: Árvore Geradora Mínima - Algoritmo Genérico

[download dos slides]   [download da vídeo aula]

• Aula 09: Árvore Geradora Mínima - Algoritmo de Kruskal

[download dos slides]   [download da vídeo aula]

• Aula 10: Árvore Geradora Mínima - Algoritmo de Prim

[download dos slides]   [download da vídeo aula]

• Aula 11: Conectividade

[download dos slides]   [download da vídeo aula]

• Aula 12: Caminhos Mais Curtos de origem única - Algoritmo de Bellman-Ford

[download dos slides]   [download da vídeo aula]

• Aula 13: Caminhos Mais Curtos de origem única em grafos acíclicos

[download dos slides]   [download da vídeo aula]

• Aula 14: Caminhos Mais Curtos de origem única - Algoritmo de Dijkistra

[download dos slides]   [download da vídeo aula]

• Aula 15: Fluxo Máximo
  [download dos slides]

• Aula 16: Algoritmo de Ford-Fulkerson
  [download dos slides]  

• Aula 17: O Problema do Emparelhamento Bipartido Máximo
  [download dos slides]

Trabalho Prático 01 :

• Assista a aula 07 para entender o que é para ser feito no TP1;

• Código base: [baseTP1.zip];

• Deve ser feita uma interface gráfica para facilitar a apresentação do TP. Nesta interface deve ser fácil escolher qual representação computacional será utilizada, bem como o algoritmo a ser executado. Indicado o arquivo para leitura do grafo, a interface deve apresentar de forma simples o retorno da função escolhida.

• Prazo: O trabalho deve ser enviado até o dia 29/09/2010 - 22h.
  06/10/2010 - 23h 59min.
  Email para envio: tpgrafos@bcc.unifal-mg.edu.br
  
  
• O TP1 deve ser apresentado presencialmente nos dias 30/09 e 01/10.
  Dia 31/09 (07/10) - Pessoas com primeiro nome de A até N.
  Dia 01/10 (08/10) - Pessoas com primeiro nome de O até Z.
• Local:
  • D-303
• Horários:
  • 07/10 - 15h00min;
  • 08/10 - 16h00min.
    
    
• Intâncias para a turma do dia 07/10/2010:
  • download.
• Intâncias para a turma do dia 08/10/2010:
  • download.

Trabalho Prático 02 :

• 24/11/2010 - Implementar as seguintes funcionalidaes;
  • agmUsandoKruskall;
  • agmUsandoPrim;
  • custoDaArvoreGeradora;
  • ehArvoreGeradora;
• Enviar até o dia 23/11/2010 para o e-mail do monitor de Grafos.
• Local:
  • D303
• Horário:
  • 18h
• As instâncias de entrada são equivalentes as instancias utilizadas no TP1. Vale lembrar que na árvore geradora não existe diferença entre as arestas (u,v) e (v,u).
• Instâncias para testes no dia do trabalho: <download>.