A semiregular tree is a tree where all non-pendant vertices have the same degree. Among all semiregular trees with fixed order and degree, a graph with minimal (adjacency / Laplacian) spectral radius is a caterpillar. Counter examples show that the result cannot be generalized to the class of trees with a given (non-constant) degree sequence. / Series: Research Report Series / Department of Statistics and Mathematics

The Discrete Nodal Domain Theorem states that an eigenfunction of the k-th largest eigenvalue of a generalized graph Laplacian has at most k (weak) nodal domains. We show that the number of strong nodal domains cannot exceed the size of a maximal induced bipartite subgraph and that this bound is sharp for generalized graph Laplacians. Similarly, the number of weak nodal domains is bounded by the size of a maximal bipartite minor. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

We investigate the structure of trees that have minimal algebraic connectivity among all trees with a given degree sequence. We show that such trees are caterpillars and that the vertex degrees are non-decreasing on every path on non-pendant vertices starting at the characteristic set of the Fiedler vector. (author´s abstract) / Series: Research Report Series / Department of Statistics and Mathematics

Orientador: Alice Kimie Miwa Libardi / Banca: Thiago de Melo / Banca: Washington Mio / Resumo: O objetivo desta dissertação é apresentar uma versão detalhada do artigo: "A Tutorial on Spectral Clustering" de U. von Luxburg sobre agrupamentos através de grafos Laplacianos, suas propriedades e mostrar alguns resultados da teoria de agrupamentos. Além disso, serão apresentados três algoritmos de agrupamentos e ilustraremos um deles com uma aplicação no cultivo da soja em diferentes condições de cultivo / Abstract: The main goal of this dissertation is to present a detailed version of the paper: " A Tutorial on Spectral Clustering" of U. von Luxburg on clusters, through Laplacian graphs, their properties and to show some results of the cluster theory. In addition, it will be presented three clustering algorithms and we will illustrate one of them with an application in the soybean cultivation, under different conditions / Mestre

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas. / In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

Este trabalho apresenta um estudo sobre segmentação de volumes médicos e uma solução para se obter malhas poligonais de pacientes específicos para uso em simulações de cirurgia. Malhas de pacientes específicos são importantes para planejamento de intervenções cirúrgicas e permitem uma melhor visualização de condições patológicas em um paciente, coisa não obtível em malhas geradas artisticamente. Nós analisamos quais são os fatores complicantes para se obter estas malhas de um paciente específico usando apenas imagens médicas obtidas em exames padrões. Para isso, nós revisamos diversos métodos existentes para segmentação de volumes médicos. Isso nos levou a definir os problemas com as técnicas existentes, e a desenvolver um método que não sofra destes problemas, utilizando pouca interação humana e não tendo dependências de mais dados que não o exame do paciente. Nosso alvo para obter malhas especificas foram órgãos de tecido mole, que são um caso especialmente complicado da área, graças a várias questões relacionadas às imagens médicas e à anatomia humana. Atacamos esse problema aplicando modificações geométricas em malhas especiais, que deformam até atingir a forma dos órgãos que se deseja segmentar. Os resultados mostram que nossa técnica conseguiu obter malhas específicas de pacientes a partir de volumes médicos com qualidade superior a de outros algoritmos de mesma classe. Graças a simplicidade do método desenvolvido, nossos resultados são facilmente implementáveis e reproduzidos. / This work presents a study about medical-volume segmentation and a solution to generate patient-specific meshes to use in patient-specific surgery simulations. Patientspecific meshes are useful assets for surgery planning and to allow better visualization of certain pathological conditions of a given patient, which are not obtainable by artistically designed meshes. We analyzed what are the complications to obtain a patient-specific mesh using only standard medical imagery exams. For that, we reviewed several medical volume segmentation techniques. It led us to define the problems within the existing techniques and to develop a method that does not suffer from these problems, with the least possible user interaction or relying on any other data other then the patient exam. Our target for obtaining specific meshes were soft tissue organs, which are a specially complicated case due to various issues related to the medical images and human anatomy. This is accomplished by geometrical operations over special meshes that deform until achieving the shape of the desired organ. Results show that our technique was able to obtain patient-specific meshes from medical images with superior quality than algorithms of the same class. Thanks to the simplicity of the developed approach, its also easy to implement and to reproduce our obtained results.

Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

Propriedades do primeiro autovalor e da primeira autofunção do operador laplaciano em variedades riemannianas são estudadas. Para variedades em que se pode estimar o laplaciano de funções distância, estimativas explícitas para o primeiro autovalor do laplaciano em domínios duplamente conexos são obtidas. Então observamos que hipóteses sobre as curvaturas da variedade e do bordo do domínio permitem estimar o laplaciano da distância. Além disso, autofunções em domínios não compactos do espaço hiperbólico EI" são estudadas. Mostramos que donn'nios contidos em horobolas não admitem autofunções limitadas associadas ao autovalor A(HIn), mas se o fecho assintótico do domínio contém um aberto de (9ooIHIn, então ele admite uma autofunção positiva que se anula em dfí U dooQ. A existência e o perfil de autofunções de autovalor A(IHI") em EI", em IHIn\Sr(o), em horobolas, em hiperbolas e no complementar de horobolas são analisados. Para alguns desses domínios apresentamos uma expressão explícita para a autofunção que depende apenas da distância à fronteira. Finalmente, técnicas de simetrização de Schwarz são adaptadas para variedades permitindo-nos obter estimativas para normas de autofunções. Primeiro um argumento de comparação demonstra que variedades mais simétricas maximizam certas normas. Obtenios também uma estimativa diretamente da função isoperimétrica da variedade. / Some properties of the first eigenvalue A and the first eigenfunction of the Laplace operator in a Riemannian manifold are studied. Assuming a bound for the Laplacian of the distance function, exphcit estimates for the first eigenvalue of a doubly counected domain are presented. Then some assumptions on the curvatures of the manifold and its boundary are made in order to have an estimate for the Laplacian of the distance function. Furthermore eigenfunctions of non compact domains in the hyperbohc space EIn are studied. We prove that a domain contained in a horoball does not admit a bounded eigenfunction of eigenvalue A(lHIn), but if the closure of the domain contains an open set of then it admits a positive eigenfunction that vanishes on dQ U daoíl. The existence and the profile of eigenfunctions of eigenvalue A(E[n ) in H71, in H [ r i \ 5 r ( o ) , in horoballs, hiperballs and in the complement of a horoball are analysed. For some of these domains we present an explicit expression for the eigenfunction that depends only on the distance to the boundary. Finally Schwarz symmetrization techniques are adapted for manifolds implying in estimates for the norm of the eigenfunctions. First a comparison argument proves that highly symmetric manifolds maximize some norm and then an estimated obtained directly from the isoperimetric function of the manifold is presented.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Os métodos espectrais são ferramentas úteis na análise de dados, sendo capazes de fornecer informações sobre a estrutura organizacional de dados. O agrupamento de dados utilizando métodos espectrais é comumente baseado em relações de similaridade definida entre os dados. O objetivo deste trabalho é estudar a capacidade de agrupamento de métodos espectrais e seu comportamento, em casos limites. Considera-se um conjunto de pontos no plano e usa-se a similaridade entre os nós como sendo o inverso da distância Euclidiana. Analisa-se a qual distância mínima, entre dois pontos centrais, o agrupamento espectral é capaz de reagrupar os dados em dois grupos distintos. Acessoriamente, estuda-se a capacidade de reagrupamento caso a dispersão entre os dados seja aumentada. Inicialmente foram realizados experimentos considerando uma distância fixa entre dois pontos, a partir dos quais os dados são gerados e, então, reduziu-se a distância entre estes pontos até que o método se tornasse incapaz de efetuar a separação dos pontos em dois grupos distintos. Em seguida, retomada a distância inicial, os dados foram gerados a partir da adição de uma perturbação normal, com variância crescente, e observou-se até que valor de variância o método fez a separação dos dados em dois grupos distintos de forma correta. A partir de um conjunto de pontos obtidos com a execução do algoritmo de evolução diferencial, para resolver um problema multimodal, testa-se a capacidade do método em separar os indivíduos em grupos diferentes.

Neste trabalho, estudamos a existˆencia e multiplicidade de solu¸c˜oes de certos problemas p-sublineares envolvendo o operador p-laplaciano usando teoria de Morse. / The purpose of this text is to provide a didactic exposition of the paper “Solutions of p-sublinear p-Laplacian equation via Morse theory” by Yuxia Guo and Jiaquan Liu [8]. This paper addresses the existence and multiplicity of solutions for the problem where is a smooth, bounded domain of RN, p is the p-Laplacian operator and f satisfies certain conditions, in particular f is p-sublinear at 0. Morse theory is used to infer the existence of critical points of a functional associated to this problem. In Chapter 2, we introduce the necessary Morse theoretic concepts, assuming basic knowledge of singular homology theory. In Chapter 3, we introduce basic properties of the p-Laplacian operator, assuming knowledge of Sobolev spaces, including imbedding and compactness results. Finally, in Chapter 4, we follow Guo and Liu’s paper itself.