Decomposição arbórea e localização de autovalores em grafos
Visualizar/abrir
Data
2023Autor
Orientador
Nível acadêmico
Mestrado
Tipo
Resumo
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. ...
Instituição
Universidade Federal do Rio Grande do Sul. Instituto de Matemática e Estatística. Programa de Pós-Graduação em Matemática Aplicada.
Coleções
-
Ciências Exatas e da Terra (5097)Matemática Aplicada (283)
Este item está licenciado na Creative Commons License
![](/themes/Mirage2Novo//images/lume/cc.png)