Decomposição arbórea e localização de autovalores em grafos

Abstract

A busca por autovalores de matrizes associadas a grafos é um passo fundamental da Teoria Espectral de Grafos. Neste trabalho, abordamos um Algoritmo de Localização de Autovalores em grafos que utiliza como parte da entrada uma decomposição arbórea. Exemplificamos e detalhamos seu funcionamento para grafos em geral e demonstramos seu desempenho para duas classes específicas. A primeira classe é a das árvores, onde realizamos uma comparação com um algoritmo desenvolvido especificamente para esse propósito. Por fim, utilizamos o algoritmo para a classe de grafos cactos como uma de suas aplicações.

The search for eigenvalues of matrices associated with graphs has become one of the important lines of research in the Spectral Graph Theory. In this work, we address an Eigenvalue Localization Algorithm in graphs that uses tree decomposition as part of its input. We exemplify and detail its operation for a general graph and demonstrate its performance for two specific classes. The first class is that of trees, where we make a comparison with an algorithm developed for this purpose. Finally, we use the algorithm for the class of Cactus graphs as one of its applications.