Orientador: Alice Kimie Miwa Libardi / Banca: Thiago de Melo / Banca: Flávia Souza Machado da Silva / Resumo: O objetivo principal deste trabalho é obter um resultado sobre separação de superficies por grafos. A Homologia Relativa é a principal ferramenta usada, obtendo uma versão particular da Dualidade de Lefschetz. Para a elaboração desta dissertação foram estudados: grafos, homologia simplicial, homologia relativa e grafos em superficies. O estudo foi baseado em grande parte no livro Graphs, Surfaces and Homology de P. J. Giblin / Abstract: The main goal of this work is to get a result on separation of surfaces by graphs. The Relative Homology is the principal tool used and we get a particular version of Lefschetz duality. For the preparation of this dissertation we studied: graphs, simplicial homology, relative homology and graphs on surfaces. The study was based on the book Graphs, Surfaces and Homology of P. J. Giblin / Mestre

Made available in DSpace on 2014-11-29T01:02:12Z (GMT). No. of bitstreams: 1 000463003-Texto+Completo-0.pdf: 2663394 bytes, checksum: 0158a49caa9b116197cb1f3a76c44980 (MD5) Previous issue date: 2014 / Resting State functional Magnetic Resonance Imaging (rs-fMRI) provides information about the functional connectivity of brain areas. However, prior to calculating the functional connectivity of the brain, there is a choice of several preprocessing steps that need to be selected. A critical source of variation between studies arises from distinct preprocessing approaches prior to the functional connectivity analysis. Therefore, a study to examine the reliability of different methods for pre-processing data from rs-fMRI is necessary. In this study, seven preprocessing strategies were tested and the reliability was evaluated between them in Graph Theoretical (GT). The sample used in this study is from a public database and consists of control subjects. Measures of GT were calculated using different strategies, after applying a method of subdividing the brain into 190 regions of interest. The following measures were calculated: global efficiency, characteristic path length, clustering coefficient and local efficiency. The results indicate that there is a significant difference in measurements of GT depending on the preprocessing strategy selected. It was also found that noise estimation parameters are correlated with GT measures. Moreover, it is observed that the level of thresholding chosen in the connectivity matrix can affect the measurements of GT, therefore further studies regarding this topic are needed. It was concluded, based on the sample used in this work that the method of scrubbing by outliers could increase the reliability of measurements of GT and reduce dependence on the movement of the patient's head. / A Ressonância Magnética Funcional no estado de repouso (rs-fMRI, do inglês resting state functional Magnetic Resonance) permite obter informações a respeito das áreas de conectividade funcional do cérebro. Porém, a visualização dessa conectividade só é possível após aplicar uma série de etapas de processamento de imagens antes que se possa avaliar a conectividade cerebral. Considerando a limitação na quantificação dos dados de rs-fMRI, e sabendo que uma fonte de variação crítica para a comparação entre os estudos é o fato de cada um deles remover, incluir ou mudar parâmetros nos passos de pré-processamento de rs-fMRI, é necessário um estudo para analisar a confiabilidade de diferentes metodologias de préprocessamento de dados de rs-fMRI. Para tanto, a Teoria dos Grafos (TG) foi utilizada como parâmetro final para avaliar a conectividade. Neste presente trabalho, foram testadas sete estratégias de pré-processamento e foi avaliada a confiabilidade entre elas quando são feitas medidas de TG. A amostra utilizada neste trabalho é de uma base de dados pública e é composta por indivíduos controle. As medidas de TG foram calculadas nas diferentes estratégias, após aplicar um método de parcelamento do cérebro em 190 regiões. Foram calculadas as seguintes medidas: eficiência global, comprimento do caminho característico, coeficiente de agrupamento e eficiência local. Os resultados indicaram que existe uma diferença significativa nas medidas de teoria dos grafos quando o pré-processamento é feito de diferentes maneiras. Foi encontrado também que parâmetros de estimativa de ruído são correlacionados com as medidas de TG. Além disso, observa-se que o nível de limiarização escolhido na matriz de conectividade pode afetar significativamente as medidas de TG, sendo necessário um estudo mais aprofundado a respeito deste tema. Concluiu-se, baseado na amostra utilizada neste trabalho, que o método de scrubbing por outliers pode aumentar a confiabilidade das medidas de TG e reduzir a sua dependência com o movimento da cabeça do paciente.

O objetivo principal deste trabalho é apresentar uma. descrição detalhada sobre as diversas abordagens do Problema do Caixeiro Viajante, a complexidade na sua resolução e as aplicações nas diversas áreas do conhecimento. O Problema do Caixeiro Viajante é um dos mais conhecidos e estudados problemas da Teoria dos Grafos e sua importância é tanta teórica quanto prática. O resultado teórico mais importante que apresentamos neste trabalho é a prova de que o PCV é -P-Completo, usando (e provando) o Teorema de Cook, como ponto de partida e a Máquina de Turing como o modelo computacional para as provas da complexidade dos problemas envolvidos. O PCV é equivalente ao problema de encontrar um circuito Hamiltoniano de peso mínimo em um grafo ponderado. Uma das questões principais envolvidas neste problema, e na verdade uma das principais indagações da Ciência da Comput ação, é saber se existe um algoritmo eficiente de tempo polinomial para calcular tal circuito, ou se tal algoritmo não existe, caracterizando-o, assim, como um problema impossível de ser resolvido. Quando não se pode encontrar uma solução eficiente para um dado problema e também não pode ser demonstrado que tal solução existe, deve-se usar técnicas que permitam construir um algoritmo que forneça soluções aproximadas. Neste trabalho, apresentamos um algoritmo de tempo polinomial que nos fornece soluções aproximadas para o PCV. / The main objective of this work is to present a detailed description on the various approaches to the Traveling Salesperson Problem (TSP), the complexity of its solution and its applications to the various knowledge area.s. The Traveling Salesperson Problem is one of the most known and studied problems in graph theory and its importance is theoretical as well as practical. The theory result more important who we will introduce in this work is the proof of the TSP is NP-complete, using (and proving) of Cook's Theorem like point of departure and the Turing Machine like the model computational for the tests of complexity of problems involved. The TSP is equivalent to the problem of finding a Hamiltonian circuit of minimal weight in a weighted graph. One of the main questions involved in this problem, and actually one of the main questions of the whole Computing Science, is to know if there exists an polynomial-time efficient algorithm to compute such a circuit, or if such an algorithm can not exist, then characterizing it as an impossible problem. When one can not find an efficient solution for a given problem and also can not show that such a solution exists, we must use techniques that aid us to construct an algorithm providing approximate solutions. In this work, we will present a polynomial-time algorithm that gives approximate solutions for the solution of the Traveling Salesperson Problem.

O objetivo principal deste trabalho é apresentar uma. descrição detalhada sobre as diversas abordagens do Problema do Caixeiro Viajante, a complexidade na sua resolução e as aplicações nas diversas áreas do conhecimento. O Problema do Caixeiro Viajante é um dos mais conhecidos e estudados problemas da Teoria dos Grafos e sua importância é tanta teórica quanto prática. O resultado teórico mais importante que apresentamos neste trabalho é a prova de que o PCV é -P-Completo, usando (e provando) o Teorema de Cook, como ponto de partida e a Máquina de Turing como o modelo computacional para as provas da complexidade dos problemas envolvidos. O PCV é equivalente ao problema de encontrar um circuito Hamiltoniano de peso mínimo em um grafo ponderado. Uma das questões principais envolvidas neste problema, e na verdade uma das principais indagações da Ciência da Comput ação, é saber se existe um algoritmo eficiente de tempo polinomial para calcular tal circuito, ou se tal algoritmo não existe, caracterizando-o, assim, como um problema impossível de ser resolvido. Quando não se pode encontrar uma solução eficiente para um dado problema e também não pode ser demonstrado que tal solução existe, deve-se usar técnicas que permitam construir um algoritmo que forneça soluções aproximadas. Neste trabalho, apresentamos um algoritmo de tempo polinomial que nos fornece soluções aproximadas para o PCV. / The main objective of this work is to present a detailed description on the various approaches to the Traveling Salesperson Problem (TSP), the complexity of its solution and its applications to the various knowledge area.s. The Traveling Salesperson Problem is one of the most known and studied problems in graph theory and its importance is theoretical as well as practical. The theory result more important who we will introduce in this work is the proof of the TSP is NP-complete, using (and proving) of Cook's Theorem like point of departure and the Turing Machine like the model computational for the tests of complexity of problems involved. The TSP is equivalent to the problem of finding a Hamiltonian circuit of minimal weight in a weighted graph. One of the main questions involved in this problem, and actually one of the main questions of the whole Computing Science, is to know if there exists an polynomial-time efficient algorithm to compute such a circuit, or if such an algorithm can not exist, then characterizing it as an impossible problem. When one can not find an efficient solution for a given problem and also can not show that such a solution exists, we must use techniques that aid us to construct an algorithm providing approximate solutions. In this work, we will present a polynomial-time algorithm that gives approximate solutions for the solution of the Traveling Salesperson Problem.

Submitted by Victor Hugo Albuquerque Rizzo (victor.rizzo@ufpe.br) on 2015-04-14T14:55:20Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Jônata Ferreira de Melo.pdf: 4496803 bytes, checksum: 608a870941a111c2fef5e1ad33e18180 (MD5) / Made available in DSpace on 2015-04-14T14:55:20Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Jônata Ferreira de Melo.pdf: 4496803 bytes, checksum: 608a870941a111c2fef5e1ad33e18180 (MD5) Previous issue date: 2013 / Este trabalho propõe a utilização da teoria dos grafos e simulação computacional para analisar redes hidráulicas industriais, isto com o intuito principal de reduzir o tempo desprendido na simulação dos cenários propostos. Esta metodologia é baseada principalmente em sete etapas: converter a rede hidráulica em um grafo correspondente, sistematizar o cálculo das perdas de carga para cada trecho; automatizar a análise do grafo no MATLAB®; analisar o resultado do ponto hidraulicamente mais desfavorável; elaborar de acordo com o ponto hidraulicamente mais desfavorável, novos cenários alterando parâmetros como diâmetro das tubulações; dimensionar bomba para os cenários viáveis e analisar o custo de cada cenário proposto. Com este método de análise as simulações dos diversos cenários puderam ser realizadas em poucos minutos. A agilidade na elaboração e decisão envolvidas na etapa de projeto é essencial para que a etapa de construção e montagem providencie os recursos com mais antecedência o que dá uma folga maior para absorver os imprevistos da construção e montagem.

Orientador: Patrícia Helena Araújo da Silva Nogueira / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T08:03:36Z (GMT). No. of bitstreams: 1 Staib_FredericoFontes_M.pdf: 14016255 bytes, checksum: 4ec6112a82029b5e16c1c450779bf803 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho, estudamos a teoria das bases de Gröbner e sua aplicação ao problema da k-coloração de grafos, estabelecendo assim uma interessante conexão entre a álgebra abstrata e a matemática discreta. Fazemos também uma abordagem de caráter lúdico, traduzindo o passatempo chamado Sudoku em um problema de 9-coloração e utilizando a teoria apresentada para resolvê-lo através das bases de Gröbner / Abstract: In the present work, we study the Gröbner basis theory and its application on the graph k-coloring problem, establishing an interesting relation between abstract algebra and discrete mathematics. We make a ludic approach, translating the puzzle called Sudoku to a 9-coloring problem and using the given theory to solve it by the Gröbner basis / Mestrado / Algebra / Mestre em Matemática

Orientador: Jacques Wainer / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-05T07:24:55Z (GMT). No. of bitstreams: 1 Elias_GuilhermeSteinberger_M.pdf: 3432904 bytes, checksum: 9dba0032d1f963b571f539e39035e9d9 (MD5) Previous issue date: 2005 / Resumo: Esta é uma pesquisa, na área de Tecnologias de Informação, sobre como as inovações são disseminadas em sociedade. Tomando o trabalho de Everett Rogers (1962) sobre "difusão de inovações" como referência, o estudo situa-se na interface desta área com os campos da Sociologia e do Marketing, permitindo avaliar como as mudanças ou os novos conceitos são recebidos ou rejeitados em agrupamentos de diferentes naturezas. A representação de como as inovações penetram nestas populações tem sido feita através de simulações baseadas em grafos, onde cada vértice representa um membro da população. Nos estudos de Rogers e outros pesquisadores, prevalece uma forma aleatória de interconexão destes membros, aqui chamada de "mundo aleatório". Entretanto, mais recentemente, Watts (1999) descobriu que, sob certas condições, membros de grupos interconectam-se de forma que todos possuam apenas uns poucos intermediários entre si, em contextos onde haja vizinhanças com muitos membros já interconectados. Ainda hoje se estuda as causas para este fenômeno, chamado de "mundo pequeno". O objetivo deste trabalho é verificar como se comporta a curva de "difusão de inovações" em contextos com tais características e identificar as diferenças em relação ao modelo onde as interconexões eram aleatórias. Os primeiros resultados mostraram que, na maioria dos casos aqui analisados, a velocidade de aceitação de inovações (performance) é inferior em contextos de "mundo pequeno", se comparada aos de "mundo aleatório". Ao redesenharmos, entretanto, modelos de "mundo pequeno" com as mesmas definições de Watts e extraindo a aleatoriedade, encontramos uma performance superior, ainda que bem mais sensível do que as versões de Rogers e Watts em relação às características da população. Concluímos que a adoção de alguns modelos de "mundo pequeno" (desde que bem parametrizados) pode ser mais produtiva e permitir preservar características do mundo real, ou seja, obter efeito mais "natural". Testamos diferentes parâmetros, encontrando como mais produtivos: o grau de independência das novas conexões em relação às anteriores ( parâmetro a), a probabilidade aleatória de conexão entre dois membros quaisquer (parâmetro p), a quantidade média de conexões por membro (parâmetro km), a seleção de membros inovadores como líderes locais (além de possuírem conexão com outros grupos, detêm alto índice de conexões com seu próprio grupo). O modelo para simulação aqui utilizado, com pequeno ajuste, foi o de "multiagentes" idealizado por Maienhofer e Finholt (2000) / Abstract: This is a research in the area of Information Technology about how are the innovations disseminated in society. Taking the work of Everett Rogers (1962) about "diffusion of innovations" as reference, the study takes p1ace in the interface of this area with the fields of Sociology and Marketing, allowing evaluating how do the changes or new concepts are received or rejected in groups of different natures. The representation of how do the innovations penetrate in these populations has been done by simulations based on graphs, where each vertex represents one member of the population. In the studies of Rogers and other researchers, prevails a random shape of interconnection of these members, here known as "random world". But recent1y, Watts (1999) discovered that, under certain conditions, members of groups interconnect in such a way where all of them have on1y a few intermediates between each other, in contexts where there are neighborhoods with many members already connected. Still today, it's studied the causes for this phenomenon, known as "small world". The objective of this work is to verify how is the behavior of the curve of "diffusion of innovations" in contexts with these characteristics and identify the differences regarding the model where the interconnections were random. The first results showed that, in the majority of the cases here analyzed, the velocity of acceptance of innovations (performance) is lower in contexts of "small world", if compared to those from "random world". But, after redesigning models of "small world" based on the same definitions of Watts and extracting the randomness, we found a superior performance, even though it' s more sensible than versions of Rogers and Watts regarding the characteristics of the population. We concluded that the adoption of some models of "small world" (if with good parameters), can be more productive and allow the preservation of characteristics of real world, that means, to obtain a more "natural" effect We tested different parameters, finding advantages in the following: the degree of independence of new connections regarding the previous connections (parameter a), the random probability of connection between any two members (parameter p), the medium quantity of connections per member (parameter km), the selection of innovators members as local leaders (they have connection with other groups and high index of connections with their own group). The model used here for simulation, with little adjust, was the "multi-agents" idealized by Maienhofer and Finholt (2000) / Mestrado / Engenharia de Software / Mestre Profissional em Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-14T23:05:02Z (GMT). No. of bitstreams: 1 Silva_CandidaNunesda_D.pdf: 1443438 bytes, checksum: c37eb2de501a4f5b10d9c8681c3a0971 (MD5) Previous issue date: 2009 / Resumo: Esta tese trata de fluxos inteiros e colorações em grafos, problemas intimamente relacionados. Concentramos nossa atenção nas Conjeturas de Tutte sobre 5-, 4- e 3-fluxos, as quais foram propostas entre as décadas de 50 e 70 e permanecem abertas até hoje. Apresentamos três abordagens para o ataque das conjeturas, com ênfase na Conjetura dos 3-Fluxos. Na primeira abordagem propomos o estudo dos grafos fluxo-críticos, aqueles que não admitem um k-fluxo, mas que passam a admitir quando sujeitos a uma simples operação de redução. O interesse no estudo dessa classe de grafos vem da observação de que todo contra-exemplo mínimo para qualquer uma das conjeturas de Tutte é fluxo-crítico. Na segunda abordagem estudamos a conexidade cíclica do contra-exemplo mínimo para uma conjetura equivalente à Conjetura dos 3-Fluxos. Na terceira abordagem buscamos uma nova demonstração do Teorema de Grötzsch, o qual é o dual planar da Conjetura dos 3-Fluxos, que não utilize a Fórmula de Euler como a demonstração original. / Abstract: The theme of this thesis is nowhere-zero flows and colourings of graphs, two subjects that are closely related. We focus mainly on the three Conjectures of Tutte concerning 5-, 4- and 3-nowhere-zero flows. These conjectures were proposed, respectively, in the 50's, 60's and 70's; all of them remain open so far. In this thesis we present three different approaches for the study of Tutte's Conjectures, with emphasis on the 3-Flow Conjecture. In the first approach, we introduce the concept of flow-critical graph. A graph is flowcritical if it does not admit a nowhere-zero k-flow but, when a simple reduction operation is applied, the resulting graph does admit a nowhere-zero k-flow. The motivation for the study of such graphs is due to the observation that any minimum counterexample for any of Tutte's conjectures lies in this particular class. In the second approach, we study the cyclic-connectivity of a minimum counterexample for an equivalent version of the 3-Flow Conjecture. In the third approach, we give a new proof for Gr¨otzsch's Theorem that differs from the original in the fact that it does not depend on Euler's Formula. / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

Submitted by Lúcia Brandão (lucia.elaine@live.com) on 2015-12-14T18:11:19Z No. of bitstreams: 1 Dissertação - Audemir Lima de Souza.pdf: 2998133 bytes, checksum: 80d0fe342d01a9b0c319d28a64167d5d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-01-20T18:20:45Z (GMT) No. of bitstreams: 1 Dissertação - Audemir Lima de Souza.pdf: 2998133 bytes, checksum: 80d0fe342d01a9b0c319d28a64167d5d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-01-20T18:22:03Z (GMT) No. of bitstreams: 1 Dissertação - Audemir Lima de Souza.pdf: 2998133 bytes, checksum: 80d0fe342d01a9b0c319d28a64167d5d (MD5) / Made available in DSpace on 2016-01-20T18:22:03Z (GMT). No. of bitstreams: 1 Dissertação - Audemir Lima de Souza.pdf: 2998133 bytes, checksum: 80d0fe342d01a9b0c319d28a64167d5d (MD5) Previous issue date: 2013-08-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work we make a simple approach to the concepts of graphs and make them better known, because although it has a wide variety of applications, is a little known subject in basic secondary education. In the intimate to disclose modeling using graph theory, concepts and definitions will be shown, models and classic examples applied by early scholars of this theory with the intention to motivate the logical reasoning of our students to assist them in the resolution of other problems. It will be shown as such information can be represented in the computer and how to decide which representation by choice. Also present algorithms that can bring in automated or computerized results because certain problems will solve only with the help of the machine. We believe that this form of modeling-problems can contribute to the improvement of teaching and learning and serve as a motivating factor for students and teachers seeking to improve their knowledge of graph theory and its applications. / Neste trabalho procuramos fazer uma abordagem simples sobre os conceitos de grafos e torná-los mais conhecidos, pois embora tenha uma grande variedade de aplicações, é um assunto pouco conhecido no Ensino Médio básico. No intimo de divulgar modelagem usando a teoria dos grafos, serão mostrados conceitos e definições, modelos e exemplos clássicos aplicados pelos primeiros estudiosos dessa teoria, com a intenção de motivar o raciocínio lógico de nossos alunos para auxiliá-los nas resoluções de outros problemas. Será mostrado como tais informações podem ser representadas no computador e como decidir por qual representação optar. Também apresentaremos algoritmos que podem nos trazer resultados automáticos ou informatizados, pois determinados problemas só resolveremos com o auxílio da máquina. Acreditamos que esta forma de modelas problemas pode contribuir para a melhoria do ensino-aprendizagem e servir como elemento motivador para alunos e professores que buscam melhorar seus conhecimentos sobre a teoria dos grafos e suas aplicações.

Orientadores: Pedro Jussieu de Rezende, Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T03:33:56Z (GMT). No. of bitstreams: 1 Silva_AndreCarvalho_M.pdf: 846347 bytes, checksum: ec1253f464900a70a0ef3bb68f9af1fa (MD5) Previous issue date: 2013 / Resumo: Grafos de visibilidade entre vértices de polígonos são estruturas que resumem as informações de visibilidade de tais vértices. Existem três relevantes problemas relativos a grafos de visibilidade: caracterização, reconhecimento e reconstrução. O problema da caracterização consiste em encontrar um conjunto de condições necessárias e suficientes para a classe de grafos de visibilidade. A procura de uma forma algorítmica para se reconhecer quando um grafo é de visibilidade define o problema de reconhecimento. O problema de reconstrução trata da questão de se reconstruir um polígono a partir de um grafo de visibilidade de tal forma que este seja isomorfo ao grafo de visibilidade do polígono. Neste trabalho, abordamos estes problemas para uma subclasse destes grafos: grafos de visibilidade de leques convexos. Dois resultados principais são apresentados nesse trabalho. O primeiro deles é um conjunto de três condições necessárias que um grafo de visibilidade de um leque convexo deve satisfazer. Adicionalmente, mostramos que estas condições são necessárias e suficientes para grafos de visibilidade de pseudo-leques convexos. Um resultado colateral deste processo é a equivalência entre grafos de visibilidade entre vértices, e grafos de visibilidade vértice-aresta, para leques convexos em posição geral. O segundo resultado consiste em que podemos reduzir o problema de reconstrução de polígonos unimonótonos para o mesmo problema para leques convexos / Abstract: The (vertex) visibility graph of a polygon is a graph that gathers all the visibility information among the vertices of the polygon. Three relevant problems related to visibility graphs are: characterization, recognition and reconstruction. Characterization calls for a set of necessary and sufficient conditions that every visibility graph must satisfy. Recognition deals with the problem of determining whether a given graph is the visibility graph of some polygon. Reconstruction asks for the generation of a polygon whose visibility graph is isomorphic to a given visibility graph. In this work, we study these problems on a restricted class of polygons, namely, convex fans: polygons that contain a convex vertex in its kernel. This work is comprised of two main results. The first one presents three necessary conditions that visibility graphs of convex fans must satisfy. We also show that those conditions are necessary and sufficient for visibility graphs of convex pseudo-fans. As a byproduct, we show that we can construct the vertex-edge visibility graph of a convex fan in general position from its vertex visibility graph. In the second major result, we show that we can reduce the reconstruction problem of unimonotone polygons to the same problem for convex fans / Mestrado / Ciência da Computação / Mestre em Ciência da Computação