Return to search

Generalizações da Teoria de Fiedler para a Conectividade Algébrica

Esta tese generaliza resultados sobre a conectividade algébrica e seus autovetores associados. Generalizamos resultados que foram descobertos por Fiedler et. al. na investigação da conectividade algébrica de grafos com um ponto de articulação para grafos sem pontos de articulação. Exibimos uma fórmula explícita para a conectividade algébrica absoluta sobre uma classe de árvores específica. Além disso, exibimos expressões para os autovetores que geram o autoespaço associado a conectividade algébrica absoluta. Também apresentamos um novo algoritmo combinatório que computa a conectividade algébrica absoluta para qualquer árvore em tempo O(n3). Desenvolvemos uma teoria como a de Fiedler para a matriz Laplaciana perturbada, levando a resultados que são do mesmo tipo dos obtidos para a conectividade algébrica de um grafo. / This thesis generalizes results on the algebraic connectivity and its eigenvectors. We generalize results that were found by Fiedler et. al. investigating the algebraic connectivity of graphs with articulation points to graphs without articulation points. We exhibit an explicit formula for the absolute algebraic connecitivity over a speci c class of trees. Besides, we exhibit expressions for the eigenvectors that generates the eigenspace associated with the absolut algebraic connectivity. Also, we present a new combinatorial algorithm that computes the absolute algebraic connectivity in time O(n3). We develop a theory like Fiedler's to the perturbed Laplacian matrix, leadig to results that are of the same kind obtained for the algebraic connectivity of a graph.

Identiferoai:union.ndltd.org:IBICT/oai:lume.ufrgs.br:10183/122181
Date January 2015
CreatorsRocha, Israel de Souza
ContributorsTrevisan, Vilmar
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFRGS, instname:Universidade Federal do Rio Grande do Sul, instacron:UFRGS
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0186 seconds