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