Estudo e resolução de problemas que utilizam grafos. Desenvolvimento e implementação de algoritmos clássicos sobre grafos.
Conceitos fundamentais: representações; operações básicas; travessias, buscas, ordenação topológica, caminhos mínimos, árvores geradoras mínimas, fluxo em redes. Aplicações. Análise dos algoritmos.
Grafos: conceitos fundamentais; representação via matriz de adjacência, representação via listas de adjacências, outras representações; operações básicas sobre grafos, busca em largura e em profundidade. Aplicações de busca em profundidade: detecção de ciclos, componentes conexos e fortemente conexos, pontes e vértices de articulação, ordenação topológica. Árvores geradoras mínimas, caminhos mínimos, fluxo em rede, noções de redes complexas, aplicações em Computação e outras áreas, análise dos algoritmos.
· Livro Texto:- CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Editora Campus.2002.- SEDGEWICK. R. Algorithms in C, Part 5 – Graph Algorithms. 3rd edition. Addison-Wesley, 2002.- ZIVIANI, N. - Projeto de algoritmos: com implementações em Pascal e C. 2a. Edição. Pioneira Thomson Learning, 2005.· Bibliografia Complementar:- AHO,A.V.; HOPCROFT,J.E.; ULLMAN,J.D. Data Structure and Algorithms. Readings, Addison Wesley, 1982.- HOROWITZ,E.; SAHNI,S. Fundamentals of Data Structures in Pascal, Computer Science Press, 1990.- SCHRIBER,T.J. An Introduction to Simulation using GPSS/H, John Wiley & Sons, 1991.- SZWARCFITER,J.L. Grafos e Algoritmos Computacionais. Editora Campus, 1983.- TENEMBAUM,A.M. et alli Data Structures Using C, Prentice-Hall, 1990.