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

Detalhes bibliográficos
Ano de defesa: 2015
Autor(a) principal: Rocha, Israel de Souza
Orientador(a): Trevisan, Vilmar
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/10183/122181
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.