Teoria Espectral dos Grafos: um Híbrido entre a Álgebra Linear e a Matemática Discreta e Combinatória com Origens na Química Quântica
DOI:
https://doi.org/10.5540/tema.2005.06.01.0001Resumo
A partir de um breve histórico da Teoria Espectral dos Grafos, TEG, este artigo apresenta os conceitos básicos da teoria e mostra como é possível, com o uso de simples resultados da álgebra Linear, determinar propriedades de um grafo através da correspondência entre a estrutura do grafo e o espectro de sua matriz de adjacência ou de sua matriz laplaciana. Além disso, indica alguns relacionamentos de TEG com outros ramos da Matemática, das Engenharias e da Ciência da Computação, apresenta uma série de problemas em aberto e aponta os possíveis desenvolvimentos da área.Referências
[1] N.M.M. Abreu e C.S. Oliveira, “Álgebra Linear em Teoria dos Grafos”, minicurso, Primeira Semana da Matemática de São Mateus, ERMAC/SBMAC, UFES, 2004.
S. Belhaiza, N.M.M. Abreu, P. Hansen e C.S. Oliveira, Variable Neighborhood Search for Extremal Graphs 11. Bounds on Algebraic Connectivity, apresentado em Computer and Discovery, Montreal, Canadá, submetido à série DIMACS, 2004.
K. Bali´nska, D. Cvetkovi´c, Z. Radosavljevi´c, S. Simi´c e D. Stevanovi´c, A survey on integral graphs, Publ. Elektrotehn. Fak. Ser. Mat., Univ. Belgrad , 13 (2002), 42-65.
N. Biggs, “Algebraic Graph Theory”, 2a. ed., Cambridge, Inglaterra, 1993.
L. Brankovic e D. Cvetkovi´c, The eigenspace of the eigenvalue -2 in generalized line graphs and a problem in security of statistical data bases, Publ. Elektrotehn. Fak. Ser. Mat., Univ. Belgrad, 14, (2003).
P.O. Boaventura Netto, “Grafos: Teoria, Modelos, Algoritmos”, 2a. ed., Editora Bl¨ucher, São Paulo, 2001.
D. Cvetkovi´c, M. Cangalovic e V. Kovacevic-Vujcic, Combinatorial optimization and highly informative graph invariants, to appear.
D. Cvetkovi´c, M. Doob, I. Gutman e A. Torgaˇsev, “Recent Results in the Theory of Graph Spectra”, North-Holland, 1988.
D. Cvetkovi´c, M. Doob e H. Sachs, “Spectra of Graphs: Theory and application”, Academic Press, New York, 1979.
D. Cvetkovi´c, M. Doob e H. Sachs, “Spectra of Graphs”, 3a. ed., Academic Press, New York, 1995.
D. Cvetkovi´c, P. Hansen e V. Kovacevic-Vujcic, On some interconnections between combinatorial optimization and extremal graph theory, to appear.
D. Cvetkovic, P. Rowlinson e S. Simic, “Eigenspaces of Graphs”, in: Encyclopedia of Mathematics and its Applications, Cambridge, vol. 66, 1997.
D. Cvetkovi´c, P. Rowlinson e S. Simic, “Spectral Generalizations of line graphs: On graphs with least eigenvalues-2”, Cambridge University Press, 2004.
D. Cvetkovi´c e D. Stevanovic, Spectral moments of fullerene graphs, MATCH
Commun. Math. Comput. Chem., 50 (2004), 62-72.
D. Cvetkovi´c, The Theory of Graph Spectra: Origins and Development, palestra apresentada em Algraic Graph Theory Jorney, ERMAC-Rio, SBMAC, (2004).
E.R. Dam e W.H. Haemers, Which graphs are determined by their spectrum, Linear Algebra and its Applications, 373 (2003) 241-272.
R. Diestel, “Graph Theory”, Springer-Verlag, 1997.
F.R. Gantmacher, “The Theory of Matrices”, Chelsea Publishing Company, New York, 1997.
A. Graovac, I. Gutman e N. Trinajsti´c, Graph theory and molecular orbitals, Theoret. Chim. Acta, 26 (1972), 67-78.
C. Godsil e G. Royle, “Algebraic Graph Theory”, Graduate texts in Mathematics, GTM 207, Springer, 2001.
F. Harary, “Graph Theory”, Addison-Wesley, 1969.
K. Hoffman e R. Kunze, “Linear Algebra”, Prentice-Hall Inc., 1961.
L. Lima, N.M.M. Abreu, P.E. Moraes e C. Sertã, Some properties of graphs in (a,b)-linear classes, submetido à Congressus Numerantium, 2004.
R. Merris, Laplacian Matrices of Graphs: A Survey, Linear Algebra and its Applications, 197/198 (1994), 143-176.
P.E. Moraes, N.M.M. Abreu e S. Jurkiewicz, The fifth and sixth coeficients of charactersitic polynomial of a graph, Eletronic Notes in Discrete Mathematics, 11, (2002).
G. Michaels e K.H. Rosen, “Applications of Discrete Mathematics”, Mc Graw- Hill, 1992.
C.S. Oliveira, N.M.M. Abreu e S. Jurkiewicz, The characteristic polynomial of the Laplacian graphs in (a,b)-linear classes, Linear Algebra and its Applications, 356 (2002), 113-121.
J.L. Szwarcfiter, “Grafos e Algoritmos Computacionais”, Ed. Campus, 1984.
N. Trinajsti´c, “Chimical Graph Theory”, I and II, CRC Press, Boca Raton, Flórida, 1983.
D.B. West, “Introduction to Graph Theory”, Prentice-Hall, 1996.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Direitos Autorais
Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.
Propriedade Intelectual e Termos de uso
O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.
O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.
