MAC228 -- Combinatória e Teoria dos Grafos - 2o. semestre de 2006

Informações Gerais

Ementa da disciplina

Permutações, combinações, identidades binomiais, aplicações em várias áreas. Princípio da inclusão-exclusão. Fórmulas de recorrência simples. Conceitos básicos em grafos: caminhos, circuitos, árvores, colorações. Algoritmos envolvendo caminhos, circuitos e árvores. Planaridade (idéias); fórmula de Euler. O Teorema das Quatro Cores. Noções da Teoria de Ramsey.

• L. Lovász, J. Pelikán and K. Vetsztergombi, Discrete Mathematics (Elementary and Beyond) , Springer, N. York, 2003.
• J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan, 1976.
• D.I.A. Cohen, Basic Techniques of Combinatorial Theory, John Wiley, 1978.
• P. Feofiloff, Y. Kohayakawa e Y. Wakabayashi, Texto preparado para a Bienal de Matemática - out/2004
• R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, Reading 1989. (Tradução para português por V. I. Magalhães, Matemática Concreta, Livros Técnicos e Científicos, Rio de Janeiro, 1995.)
• M. Hausner, Discrete Mathematics, Saunders College Publishing, 1992.
• A. Tucker, Applied Combinatorics, John Wiley, 3rd. edition, 1995.
• R. Wilson, Introduction to Graph Theory, Academic Press, N.Y., 1972.

2a.f. das 21:10 às 22:50h; e 5a.f das 19:20h às 21h -- Sala B-4 - IME.

• Listas de exercícios e uma prova.
• Trabalhos