| Ementa/Descrição: |
Grafos, grafos simples, subgrafos. Isomorfismo de grafos. Representação computacional. Algoritmos de buscas. Grafos orientados. Trilhas, caminhose ciclos. Distância. Caminho mínimo. Conectividade de vértices e arestas. Grafos hamiltonianos.Problema do caixeiro viajante. Grafos eulerianos.Problema do carteiro chinês. Árvores, árvore geradora mínima. Teoria do NP-completo. Classes P, NP, NP-completo, NP-Díficil. Reduções polinomiais. Provas de NP-completude. Noções de planaridade. Noções de coloração de vértices. Número cromático. Noções de casamentos. Casamentos perfeitos. Noções de fluxos em redes. |
| Referências: |
J. Bondy e U. Murty, Graph Theory with Applications. Elsevier, 1979. Douglas West. Introduction to Graph Theory. Prentice Hall, 2001. Cormen, Leiserson, Rivest. Introduction to Algorithms. MIT Press, 2001.
Garey, D. Johnson. Computers and Intractability. WH Freeman & Co, 1979.
Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989. Robin J. Wilson, Introduction to Graph Theory, segunda edição, Longman, 1979.
Diestel. Graph Theory. Springer, 2005.
Cláudio L. Lucchesi e outros, Aspectos Teóricos da Computação, Parte C: Teoria dos Grafos, projeto Euclides, 1979.
Jayme Luiz Szwarcfiter, Grafos e Algoritmos Computacionais, edt. Campus, 1984.
Paulo O. B. Neto, Grafos: teoria, modelos e algoritmos, edt. Edgard Blücher Ltda., 2a. Ediçao, 1996.
Artigos de bases científicas (ACM, IEEE, Periódicos CAPES, dentre outros)
|
