Mostrar el registro sencillo del ítem

dc.contributor.advisorTrevisan, Vilmarpt_BR
dc.contributor.authorFritscher, Eliseupt_BR
dc.date.accessioned2015-02-12T02:15:27Zpt_BR
dc.date.issued2014pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/110045pt_BR
dc.description.abstractNeste trabalho, apresentamos um algoritmo que decompõe o espectro de uma matriz associada a um grafo em uma união de espectros de matrizes de ordem menor, se o grafo possui certas simetrias. Este método unifica técnicas usadas por vários autores. Para a execução do algoritmo, são introduzidos os grafos com pesos generalizados (GWG), estruturas que representam matrizes simétricas com componentes reais arbitrárias. Como aplicação direta do algoritmo, obtemos o espectro das matrizes de adjacências, laplaciana, laplaciana sem sinal e laplaciana normalizada de grafos threshold, árvores de Bethe generalizadas e grafos multi-leque. Uma segunda aplicação do algoritmo consiste na análise de uma operação que adiciona arestas em partes simétricas de um grafo de modo que o espectro laplaciano do grafo se mantém controlado. Como consequência, é possível montar uma família, da ordem de n/2 elementos, formada por grafos unicíclicos com n vértices que não são coespectrais, mas que possuem a mesma energia laplaciana. O terceiro problema abordado consiste no ordenamento de árvores de acordo com sua energia laplaciana. Utilizando uma nova cota superior para a soma dos maiores autovalores laplacianos, encontramos o conjunto de f(n) árvores com n vértices com maior energia laplaciana, onde f(n) é aproximadamente p n.pt_BR
dc.description.abstractIs this work, we present an algorithm that partitions the spectrum of a matrix associated to a graph into a union of spectra of smaller matrices, provided that the graph has some special symmetries. This method uni es techniques used by several authors. To execute the algorithm, we introduce generalized weighted graphs (GWG), structures that represent symmetric matrices with arbitrary real components. As an application of the algorithm, we obtain the spectrum of the adjacency, Laplacian, signless Laplacian and normalized Laplacian matrices of threshold graphs, generalized Bethe trees and multi-fan graphs. A second application of the algorithm consists of the analysis of an operation that adds edges to symmetric parts of the graph in such a way that the change in the Laplacian spectrum of the graph is controlled. As a consequence, it is possible to build a family of n-vertex noncoespectral unicyclic graphs of cardinality about n/2 , all of them with the same Laplacian energy. The third problem is to order trees with respect to their Laplacian energy. Using a new upper bound on the sum of the largest Laplacian eigenvalues, we are able to nd the family of f(n) trees with n vertices with the largest Laplacian energy, where f(n) is approximately p n.en
dc.format.mimetypeapplication/pdf
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectGrafospt_BR
dc.subjectAlgorítmopt_BR
dc.titleDecomposição de espectros de grafos e aplicaçõespt_BR
dc.typeTesept_BR
dc.contributor.advisor-coHoppen, Carlospt_BR
dc.identifier.nrb000952190pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Matemáticapt_BR
dc.degree.programPrograma de Pós-Graduação em Matemáticapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2014.pt_BR
dc.degree.leveldoutoradopt_BR


Ficheros en el ítem

Thumbnail
   

Este ítem está licenciado en la Creative Commons License

Mostrar el registro sencillo del ítem