Teoria dos Grafos

Objetivos

- Fornecer embasamento teórico para capacitar os alunos a identificar e solucionar problemas de Teoria dos Grafos encontrados em diversas áreas da computação.

- Promover a abordagem e o tratamento de uma ampla classe de problemas de maneira sistemática e formal.

- Habilitar o aluno a construir soluções computacionais para diversos problemas modelados através de grafos.

Ementa

1. Conceitos básicos sobre grafos
2. O Problema do Isomorfismo
3. Conectividade em grafos
4. Cadeias de Markov e caminhadas aleatórias
5. O modelo Pagerank
6. Árvores
7. O problema da árvore geradora mínima: Algoritmo de Kruskal
8. O problema da árvore geradora mínima: Algoritmo de Prim
9. Busca em grafos: Busca em Largura (BFS)
10. Busca em grafos: Busca em Profundidade (DFS)
11. Caminhos ótimos em grafos: o algoritmo de Dijkstra e A*
12. Grafos Eulerianos
13. Grafos Hamiltonianos
14. O Problema do Caixeiro viajante
15. Grafos Planares
16. Coloração de vértices e problemas relacionados
17. Emparelhamentos
18. Emparelhamentos estáveis: o algoritmo de Gale-Shapley
19. Fluxo em redes

Notas de Aula

Apostila com notas de aula sobre Teoria dos Grafos com algoritmos computacionais

Bibliografia

Graph Theory and Complex Networks: An Introduction. Maarten van Steen, 2010.

Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest and Clifford Stein, 2 ou 3. ed., The MIT Press, 2009.

Fundamentos da Teoria dos Grafos para Computação. Nicoletti, M.C.; Hruschka Jr., E. R., 2 ed., Série Apontamentos, EdUFSCar, 2009.

Introduction to Graph Theory. West, Douglas, 2 ed., Prentice Hall, 2001.

Wilson, Robin. Introduction to Graph Theory, 3 ed., Longman Scientific & Technical, 1985.

Matemática Discreta - Uma Introdução. Edward R. Scheinerman, Thomson Learning, 2003.

Grafos: conceitos, algoritmos e aplicações. M. Goldbarg e E. Goldbarg, Elsevier, 2012.

A First Look at Graph Theory. John Clark & Derek Allan Holton, World Scientific, 1998.

Algorithmic Design. Jon Kleinberg and Éva Tardos, Addison Wesley, 2005.

Projeto de algoritmos com implementações em Pascal e C. Nivio Ziviani, 3 ed., Cengage Learning, 2010

Graphs and Applications: An Introductory Approach. Aldous, J. M. & Wilson, R. J., Springer, 2000.

Networks: An Introduction. Newman, M., Oxford University Press, 2010.

Introduction to Graph Theory. Robin J. Wilson, Prentice Hall, England, 1996.

An Introduction to Discrete Mathematics. Steven Roman, Harcourt College Publishers, 1985.

Introduction to Graph Theory. Douglas B. West, 2nd. ed., Prentice-Hall, 2001.