Repositório Digital

A- A A+

Sobre o vetor de Fiedler e as componentes de Perron de um grafo

.

Sobre o vetor de Fiedler e as componentes de Perron de um grafo

Mostrar registro completo

Estatísticas

Título Sobre o vetor de Fiedler e as componentes de Perron de um grafo
Autor Rocha, Israel de Souza
Orientador Trevisan, Vilmar
Data 2012
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Matemática. Programa de Pós-Graduação em Matemática Aplicada.
Assunto Álgebra
Conectividade
Resumo Dado um grafo, sua representação através da matriz Laplaciana fornece o espectro Laplaciano do grafo. Neste trabalho, estudamos o segundo menor autovalor Laplaciano, chamado de conectividade algébrica. Chamamos qualquer autovetor associado a esse autovalor de vetor de Fiedler. Apresentamos a teoria que descreve a estrutura de um grafo através do vetor de Fiedler e as componentes de Perron de um grafo. Veremos que estudando as componentes de Perron obtemos resultados com aplicação direta no estudo da conectividade algébrica. Além disso, utilizamos estas ferramentas para obter uma ordem total pela conectividade algébrica em uma família de árvores chamadas de caterpillars [26] (um caterpillar é uma árvore na qual a remoção de todos vértices pendentes a torna um caminho).
Abstract Given a graph, its laplacian matrix representation gives the laplacian spectrum of the graph. In this work, we study the second smallest laplacian eigenvalue, called algebraic connectivity. We call any eigenvector associated with this eigenvalue a Fiedler vector. We present the theory which describes the graph structure by means of the Fiedler vector and the Perron components of a graph. We shall see that studying the Perron components we obtain results with direct application in the study of the algebraic connectivity. Moreover, we use these tools to obtain a total order by algebraic connectivity in a family of trees called caterpillars [26] (a caterpillar is a tree in which the removal of all pendant vertices make it a path).
Tipo Dissertação
URI http://hdl.handle.net/10183/49605
Arquivos Descrição Formato
000837895.pdf (715.0Kb) 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.