MAC5771 - 1o semestre de 2025
Objetivos
Estudar resultados estruturais e algorítmicos fundamentais
da teoria dos grafos.
A teoria dos grafos é uma disciplina fundamental da área de
matemática discreta e algorítmica.
Conhecer as técnicas e resultados desta disciplina é
essencial para aqueles que desejam fazer pesquisa na área de
combinatória, algoritmos e otimização combinatória.
Conteúdo
Conexidade; estrutura de grafos 2-conexos e 3-conexos.
Teorema de Menger.
Emparelhamento máximo; Teorema de Tutte; algoritmo de
Edmonds.
Coloração de vértices. Lista coloração. Grafos perfeitos.
Problemas extremos; teorema de Turán e o teorema de Erdös e
Stone.
Teoria de Ramsey.
Grafos planares; teorema de Kuratowski. Dualidade planar.
Espaços dos ciclos e dos cociclos. Outras caracterizações de
planaridade.
Fluxos e dualidade fluxos-colorações.
Menores. O minor theorem para árvores. Decomposição arbórea.
Forma de Avaliação
Média de provas e exercícios.
Bibliografia
J. A. Bondy e U. S. R. Murty, Graph Theory,
Springer, 2008.
R. Diestel, Graph Theory, Springer, 1996 (1a.
ed.), 2000 (2a. ed.), 2005 (3a.ed.).