MAC-328 Algoritmos em Grafos

IME - BCC

Segundo semestre de 2023

Aulas

  1.   9/8 - Blá geral. Definições básicas. Algumas estruturas de dados. Slides.
  2. 10/8 - Acessibilidade. Busca em profundidade. Procurar um ciclo. Slides.
  3. 16/8 - DAGs e ordenação topológica. Grafos e componentes, como encontrar. DFS em grafos.Slides.
  4. 18/8 - Grafos biconexos, pontes e blocos. Algoritmo de Hopcroft. Slides.
  5. 23/8 - Grafos fortemente conexos, componentes fortes. Algoritmos de Tarjan, Gabow e Kosaraju. Slides.
  6. 25/8 - Alguns parâmetros de grafos: χ, ω, α, κ. Grafos bipartido, seu reconhecimento e caracterização. Emparelhamentos, Teorema de Berge. Slides.
  7. 30/8 - Emparelhamentos em grafos bipartidos. Teoremas de Hall e Konig. Grafos perfeitos. Slides.
  8.   1/9 - Emparelhamentos em geral. Algoritmo de Edmonds. Teorema de Tutte. Slides.
  9. 13/9 - Distâncias, caminhos mínimos, BFs. Caminhos de custo mínimo: potenciais. Slides.
  10. 15/9 - Caminhos de custo mínimo. O problema com ciclos negativos. Caminhos em digrafos acíclicos. Algoritmo de Dijkstra.Slides.
  11. 20/9 - Algoritmo de Bellman-Ford. Algoritmo de Floyd-Warshall.Slides.
  12. 25/10 - Fluxos em redes. Caminhos aumentadores.Slides
  13. 27/10 - Fluxos em redes. Teorema do fluxo máximo corte mínimo.Slides
  14. 1/11 - Fluxos em redes - algumas aplicações..Slides

Última modificação: Wed Nov 1 10:02:09 -03 2023 por am