Luís Felipe Ignácio Cunha

Algoritmos em Grafos -- com códigos em Python

Ementa:

Conceitos fundamentais e representações de grafos. Grafos bipartidos e árvores. Busca em profundidade e busca em largura, suas propriedades e aplicações. Grafos direcionados, componentes fortemente conexas e ordenação topológica. Caminhos mínimos: algoritmos de Dijkstra, Bellman–Ford e Floyd–Warshall. Árvores geradoras mínimas: algoritmos de Kruskal, Prim e Borůvka. Emparelhamentos em grafos. Fluxo em redes. Grafos e caminhos eulerianos e o problema do Carteiro Chinês. Grafos e ciclos hamiltonianos e o problema do Caixeiro Viajante.

Bibliografia:

  1. Szwarcfiter, Jayme L.; Oliveira, Fabiano S.; Pinto, Paulo E. D. Teoria Computacional de Grafos: Os Algoritmos. Elsevier, 2018.
  2. Szwarcfiter, Jayme L. Grafos e Algoritmos Computacionais. Campus, 1986.
  3. Dasgupta, Sanjoy; Papadimitriou, Christos H.; Vazirani, Umesh V. Algorithms. McGraw-Hill, 2008.
  4. Kleinberg, Jon; Tardos, Éva. Algorithm Design. Pearson, 2013.
  5. Bondy, J. A.; Murty, U. S. R. Graph Theory with Applications. American Elsevier, New York, 1979.
  6. West, Douglas B. Introduction to Graph Theory. 2. ed. Prentice Hall, 2002.

Observação: Há inúmeros outros livros e sites sobre Grafos, por exemplo GraphClasses.org.


Slides - Todo o curso:

Atividades:



Se você tem alguma dúvida ou sugestão, sinta-se à vontade em me mandar uma mensagem. E-mail.