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.

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.

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.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-01-26T09:20:52Z No. of bitstreams: 2 Dissertação - Jânio Alves dos Santos Júnior - 2016.pdf: 3798217 bytes, checksum: c2acd93260ead52c126f4b37d994825f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-30T10:25:56Z (GMT) No. of bitstreams: 2 Dissertação - Jânio Alves dos Santos Júnior - 2016.pdf: 3798217 bytes, checksum: c2acd93260ead52c126f4b37d994825f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-01-30T10:25:56Z (GMT). No. of bitstreams: 2 Dissertação - Jânio Alves dos Santos Júnior - 2016.pdf: 3798217 bytes, checksum: c2acd93260ead52c126f4b37d994825f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-12-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work aims to study some topics of graph theory in order to solve some problems. In order to complement, we approached a light study of matrices, eigenvalues and eigenvectors. The first problem is known as Königsberg Bridge Problem, where this was considered the problem that gave rise to the study on graphs. The House Problem is a joke, which shows us several propositions about planar and bipartite graphs. Some models we can relate graphs, such as we can observe in the problem of cannibals and in the game of chess. Finally, we will work with applications in the adjacency matrix as in the Problem of the Condominium of Farms and in the Number of Possible Paths in a graph, where we will work with geometric figures, apparently resolving a counting problem using eigenvalues and graph. As a methodological support will be approached Linear Algebra. / O objetivo deste trabalho é estudar alguns tópicos da teoria de grafos com o intuito de resolver alguns problemas. Para complementar, abordamos um leve estudo de matrizes, autovalores e autovetores. O primeiro problema é conhecido como o Problema da Ponte de Königsberg, onde tal, foi considerado o problema que deu origem ao estudo sobre grafos. O Problema das Casas que é uma brincadeira, que nos mostra várias proposições sobre grafos planares e bipartidos. Alguns modelos que podemos relacionar grafos, tais como veremos no problema dos canibais e no jogo de xadrez. Por fim, trabalharemos com aplicações na matriz de adjacência como no problema do Condomínio de Chácaras e no Número de Caminhos Possíveis em um Grafo, onde trabalharemos com figuras geométricas, resolvendo aparentemente um problema de contagem, utilizando autovalores e grafos. Como suporte metodológico será abordado Álgebra Linear.