Neste trabalho estudamos o espectro de grafos, que é o conjunto de autovalores da sua matriz de adjacência. Apresentamos uma teoria baseada na função geradora do número de passeios de um grafo para obter o polinômio característico de algumas classes de grafos. Também desenvolvemos um novo método para o cálculo do polinômio característico de árvores que utiliza um algoritmo geométrico -- também por nós apresentado-- para o determinante de matrizes da forma A+a.I, onde A é a matriz de adjacências e a. é um número real arbitrário. O custo computacional desse algoritmo é O(n2 ), que é menor do que os algoritmos previamente conhecidos. Finalmente apresentamos alguns resultados que visam determinar a estrutura de um grafo a partir de suas propriedades espectrais. / In this dissertation, we study the spectra of graphs, which is the set o f the eigenvalues ofits adjacency matrix. We present a theory, based on the generating function o f the number o f walks, in order to obtain the characteristic polynomial o f certa in classes of graphs. We also develop a new method to compute the characteristic polynomial of a tree's adjacency matrix that hinges on a geometric algorithm --- also introduced in this work ---to obtain the determinant of matrices A+a l, where Ais the adjacency matrix and a an arbitrary real number. The computational cost of this algorithm is O(n2 ) , which is lower than any previously known algorithm. Finally, we present results that try to determine the structure o f a graph from its spectral properties.
| Identifer | oai:union.ndltd.org:IBICT/oai:lume.ufrgs.br:10183/127020 |
| Date | January 1999 |
| Creators | Machado, Catia Maria dos Santos |
| Contributors | Trevisan, Vilmar |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, instname:Universidade Federal do Rio Grande do Sul, instacron:UFRGS |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds