Decomposição arbórea e localização de autovalores em grafos
View/ Open
Date
2023Author
Advisor
Academic level
Master
Type
Abstract in Portuguese (Brasil)
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 ...
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. ...
Abstract
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 ...
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. ...
Institution
Universidade Federal do Rio Grande do Sul. Instituto de Matemática e Estatística. Programa de Pós-Graduação em Matemática Aplicada.
Collections
-
Exact and Earth Sciences (5097)Applied Mathematics (283)
This item is licensed under a Creative Commons License
![](/themes/Mirage2Novo//images/lume/cc.png)