Teoria Algébrica dos Grafos › 46991

Domínio das técnicas e instrumentos algébricos utilizados no estudo dos grafos, designadamente os valores e vectores próprios associados às matrizes representativas de grafos, a partir dos quais se podem tirar conclusões sobre a estrutura combinatória dos grafos e sobre os seus parâmetros invariantes (como são o caso do número de clique, número de independência, número cromático, etc). Domínio de algumas técnicas de identificação de grafos isomorfos, da extensão ao contexto combinatório dos grafos de espaços vectoriais (espaços das arestas ou dos arcos) e da interpretação combinatória, neste contexto, do lema de Farkas muito utilizado em optimização linear. Domínio dos esquemas associativos e da sua relação com os grafos fortemente regulares.

No final deste curso. os estudantes devem ter adquirido os fundamentos e as técnicas da teoria espectral dos grafos, dos problemas associados à identificação de isomorfismos entre grafos, dos espaços vetoriais associados a grafos e respectiva interpretação combinatória e dos esquemas associativos e dua relação com os grafos fortemente regulares.

Técnicas e resultados da teoria espectral dos grafos, com especial incidência nas relações entre os valores próprios das matrizes de adjacência e laplaciana e certos parâmetros combinatórios dos grafos (número de clique, número cromático, etc). Existência de isomorfimos entre grafos. Espaços vectoriais associados a digrafos e suas propriedades (lema de Farkas e relações entre circuitos e cocircuitos). Grafos fortemente regulares e esquemas associativos.

A avaliação consiste na realização de um exame final escrito.

Conhecimentos básicos de combinatória e teoria dos grafos e conhecimentos gerais de  álgebra linear.

Orientação tutorial baseada na discussão dos capítulos estudados pelos alunos e esclarecimento das dúvidas que se levantaram durante o estudo.

1. R. A. Bailey, Association Schemes: Designed Experiments, Algebra and Combinatorics, Cambridge University Press, Cambridge, 2004.
2. N. L. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1963.
3. D. M. Cardoso, J. Szymanski e M. Rostami,  Matemática a Discreta: combinatória, teoria dos grafos e algortimos,  Escolar Editora, Lisboa, 2009.
4. D. Cvetkovic, P. Rowlinson and S. Simic, An introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010.
5. C. Godsil, G. Royle, Algebraic Graph Theory, Springer, New York, 2001.
6. Lint, R. M. Wilson, A course in Combinatorics, Cambridge University Press, Cambridge, 2001.