Repositório Digital

A- A A+

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

.

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

Mostrar registro completo

Estatísticas

Título Generalizações da Teoria de Fiedler para a Conectividade Algébrica
Autor Rocha, Israel de Souza
Orientador Trevisan, Vilmar
Data 2015
Nível Doutorado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Matemática. Programa de Pós-Graduação em Matemática.
Assunto Álgebra
Conectividade
Vetores
Resumo 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.
Abstract 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.
Tipo Tese
URI http://hdl.handle.net/10183/122181
Arquivos Descrição Formato
000971196.pdf (764.2Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.