Ementas das Disciplinas

Teoria dos Grafos

Código: MCTA027-15

T-P-I: 3-1-4

Carga Horária: 48 horas

Recomendações: Processamento da Informação, Matemática Discreta, Algoritmos e Estruturas de Dados I

Ementa: Conceitos básicos de grafos dirigidos e não dirigidos. Passeios, caminhos, circuitos. Grafos bipartidos e multi-partidos. Subgrafos. Isomorfismo. Conexidade. Florestas e árvores. Exemplos de problemas de interesse: coloração de vértices; clique máximo; caixeiro viajante; problemas de fluxo. Estruturas de dados para a representação de grafos. Percursos em grafos: em largura, em profundidade. Ordenação topológica. Árvores geradoras mínimas. Algoritmo de Kruskal. Caminhos mínimos em grafos: algoritmo de Dijkstra, algoritmo de Floyd-Warshall. Emparelhamentos: Teorema de Hall.

Bibliografia Básica

  1. CHARTRAND, G.; LESNIAK, L.; ZHANG, P. Graphs & Digraphs. 5th ed. Boca Raton: Chapman and Hall/CRC, 2010.

  2. CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: Teoria e Prática. Rio de Janeiro: Campus, 2002. 

  3. SEDGEWICK, R. Algorithms in C, Part 5: Graph Algorithms. 3rd ed. Boston: Addison-Wesley Professional, 2001.

Bibliografia Complementar

  1. ANDERSON, I. A first course in discrete mathematics. London: Springer-Verlag, 2001. (Springer undergraduate mathematics series)

  2. BOAVENTURA NETTO, P. O. Grafos: Teoria, Modelos, Algoritmos. São Paulo: Edgard Blücher, 2003.

  3. BOLLOBÁS, B. Modern Graph Theory. Corrected Edition. New York: Springer-Verlag, 1998.

  4. BONDY, A.; MURTY, U. S. R. Graph theory. London: Springer-Verlag London, 2008.

  5. GROSS, J. L.; YELLEN, J. Graph theory and its applications. 2nd ed. Boca Raton: Chapman & Hall/CRC, 2006 (Discrete mathematics and its applications)

Share

Cursos de Licenciatura e Bacharelado em Matemática da UFABC são os Melhores do Brasil

 Cursos de graduação da UFABC estão entre os melhores do Brasil segundo levantamento do MEC. Os últimos  resultados do IGC (Índice Geral de Cursos) colocaram a UFABC em segundo lugar entre as melhores universidades do país.

Os cursos de Bacharelado em Matemática  e Licenciatura em Matemática foram avaliados como os melhores do Brasil em suas respectivas categorias.

Leia Mais

Matemático foi escolhida a melhor profissão de 2014

Matemático aparece como a melhor profissão em 2014,  segundo ranking divulgado pela Careercast.com. A lista completa tem 200 profissões e leva em conta o quanto o emprego afeta a parte física do trabalhador, além de ambiente de trabalho, renda, nível de estresse e perspectivas de contratação.

Leia Mais