Mostrar el registro sencillo del ítem

dc.contributor.advisorHoppen, Carlospt_BR
dc.contributor.authorVarella, Guilherme Tadewaldpt_BR
dc.date.accessioned2023-02-18T03:28:12Zpt_BR
dc.date.issued2020pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/254875pt_BR
dc.description.abstractO problema de particionamento consiste, basicamente, em agrupar dados semelhantes e separar aqueles que não se assemelham e pode ser modelado matematicamente a partir de grafos. Recentemente, foram publicados diversos resultados teóricos sobre o tema e alguns deles fornecem algoritmos que utilizam o espectro de uma matriz associada a um grafo para gerar uma partição que auxilia a demonstrar estes resultados. Tais resultados trazem argumentos teóricos que podem ser evidências de que este algoritmo teria um bom desempenho como método para encontrar a melhor partição do problema de particionamento. Neste trabalho, procuramos entender o funcionamento de alguns destes algoritmos. Especificamente, nosso objetivo é compreender os algoritmos obtidos pela demonstração da cota superior para condutâncias de ordem 2, apresentada por Chung [8], e ordem k > 2, demonstrada por Trevisan [33]. Com relação a este último, apesar da demonstração não exigir que alguns passos do algoritmo sejam implementados de uma única maneira, vamos especificá-los com base na análise dos exemplos em que o aplicamos. Nestes exemplos, observamos que os algoritmos definidos obtiveram um bom desempenho. Também estudamos o resultado apresentado por Wang et. al [35] sobre particionamento de árvores em duas classes e propomos uma possível estratégia para provar a versão estendida deste resultado para k > 2 classes. Parte desta estratégia envolve uma versão do resultado [35] estendido para grafos com peso nos vértices, cuja prova é uma contribuição original deste trabalho.pt_BR
dc.description.abstractThe clustering problem basically consists of grouping similar data and separating those that are not similarm, and it can be using graphs. Recently, several theorical results have been published on this subject, and some of them provide approximation algorithms that use the spectrum of a matrix associated with a graph to generate a partition to prove these results. In this work, we try to understand how some of these algorithms work. Specifically, our objective is to understand the algorithms obtained for proving an upper bound for partitions into two classes, presented by Chung [8], and into k-classes, presented by Trevisan [33]. Regarding the latter, since the proof does not specify how some steps of the algorithm must be implemented, we will define them based on the analysis of the examples in which we apply it. We observed that the algorithm performed well on this examples. We also studied the result presented by Wang et al. [35] about splitting trees into two classes and we propose a possible strategy to prove an extended version of this result for k > 2 classes. Part of this strategy involves an extension of a result in [35] extended to graphs with weights on vertices, whose proof is an original contribution of this work.en
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectGrafospt_BR
dc.subjectParticionamentopt_BR
dc.subjectTeoria espectral de grafospt_BR
dc.subjectAlgoritmospt_BR
dc.titleFundamentos matemáticos de estratégias espectrais para particionamento de grafospt_BR
dc.typeDissertaçãopt_BR
dc.identifier.nrb001162666pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Matemática e Estatísticapt_BR
dc.degree.programPrograma de Pós-Graduação em Matemática Aplicadapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2020pt_BR
dc.degree.levelmestradopt_BR


Ficheros en el ítem

Thumbnail
   

Este ítem está licenciado en la Creative Commons License

Mostrar el registro sencillo del ítem