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.

Traditionally, local shape descriptors or color and texture based descriptors are used to describe the content of images. Although, these solutions achieving good results, they are not able to distinguish scenes that contain objects with the same colors, but with a different spatial organization or do not supports partial matching. In this work we focus on a particular case of the partial matching that is to find individual objects in images that contain various objects. Since the color is one of the most visually distinguishable properties, we propose a new descriptor based only on color able to find pictures of objects that are contained in other images. Although our descriptor has shown better results when compared to related works, this new color descriptor is not able to discriminate objects topologically different but having the same colors. To overcome this problem, we also propose a new approach to the partial matching of images that combine color and topological features on a single descriptor. This new descriptor, first performs a simplification process of the original image, which identifies the color regions that make up the image. Then, we represent the spatial information among the color regions using a topological graph, where vertices represent the color regions and the edges represent the spatial connections between them. To calculate the descriptor from this graph representation, we use the spectral theory of graphs, avoiding the need to make a direct comparison between graphs. To support the partial matching, we propose a decomposition of the main graph into several subgraphs, and also calculate descriptors for these subgraphs. / Tradicionalmente, descritores de forma, ou descritores baseados em cor e textura, são utilizados para descrever o conteúdo visual das imagens. Embora essas abordagens apresentem bons resultados, elas não são capazes de diferenciar adequadamente imagens que contêm objetos com as mesmas cores, mas com organização espacial diferente ou não suportam a pesquisa parcial de imagens. Neste trabalho focamos em um caso particular da pesquisa parcial de imagens, que é encontrar objetos em imagens que contenham vários objetos, não deixando de lado a pesquisa total (encontrar imagens similares à original). Dado que a cor é uma das propriedades visuais mais discriminativas, propomos um novo descritor baseado somente em cor capaz de encontrar imagens de objetos que estão contidos em outras imagens. Embora tenha apresentado melhores resultados quando comparado a trabalhos correlatos, esse novo descritor de cor não é capaz de discriminar objetos topologicamente diferentes mas que possuam as mesmas cores. Com o intuito de resolver esse problema, também propomos uma nova abordagem para a recuperação parcial de imagens que combina características topológicas e de cor em um único descritor. Esse novo descritor primeiramente realiza um processo de simplificação da imagem original, onde são identificadas as regiões de cor que compõem a imagem. Após esse processo de simplificação, a organização espacial das regiões de cor previamente identificadas é representada por meio de um grafo topológico, onde os vértices representam as regiões de cor e as arestas representam as conexões entre essas regiões. O descritor topológico é então calculado a partir do grafo de topologia utilizando a teoria espectral de grafos, evitando a necessidade de se realizar uma comparação direta entre grafos. Para suportar a pesquisa parcial de imagens, é realizada uma decomposição do grafo principal em diversos subgrafos. / Mestre em Ciência da Computação