Portal do Ementário

Apresentar os principais conceitos e definições da teoria dos grafos, bem como algumas das propriedades e casos especiais de grafos. [Familiaridade] Apresentar as formas de se representar grafos. [Familiaridade] Demonstrar diferentes métodos de percurso em grafos. [Uso] Apresentar os conceitos de árvores, grafos ponderados e árvores geradoras. [Familiaridade] Explicar como construir uma árvore geradora de um grafo. [Uso] Identificar se dois grafos são isomórficos. [Avaliação] Determinar a coloração mínima de arestas e vértices de um grafo. [Avaliação] Estudar algoritmos para problemas fundamentais em grafos. [Uso] Apresentar e estudar as aplicações de grafos. [Uso]

Conceitos e definições de grafos e subgrafos. Grafos direcionados e não-direcionados. Conectividade. Ciclos. Hipergrafos. Isomorfismo. Grafos bipartidos. Grafos Eulerianos e Hamiltonianos. Representação de grafos. Algoritmos de percurso em grafos. Coloração de arestas e de vértices. Árvores, grafos ponderados e árvore geradora. Problemas de caminhos mínimos. Emparelhamentos. Noções de planaridade. Fluxo em redes. Aplicações.

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos. Teoria e Prática. 3a ed. Rio de Janeiro: Elsevier - Campus, 2012. DIESTEL, Reinhard. Graph Theory. 4th ed. Heidelberg: Springer, 2010. NICOLETTI, Maria do Carmo; HRUSCHKA JR., Estevam R. Fundamento da Teoria dos Grafos para Computação. 3th ed. LTC, 2017.

GROSS, Jonathan L.; YELLEN, Jay. Graph Theory and Its Applications. 2nd ed. Boca Raton, Fla.: Chapman \& Hall/CRC, 2006. NETTO, Paulo Oswaldo Boaventura. Grafos - Teorias, Modelos, Algoritmos. 5a ed. São Paulo: Blucher, 2012. BOLLOBÁS, Béla. Extremal Graph Theory. Mineola, N.Y.: Dover Publications, 2004. TRUDEAU, Richard J. Introduction to Graph Theory. Courier Corporation, 2013. SEDGEWICK, Robert. Algorithms in C. Part 5: Graph Algorithms. 3rd ed. Addison-Wesley/Longman, 1998.