MAC5771 -- MAC0452 - 1^o semestre de 2024

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.

Listas de Exercícios     1^a lista     solução     2^a lista

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.).

B. Bollobás, Modern Graph Theory, Springer, 1998.