O objetivo principal deste trabalho é tratar as implicações geométricas e topológicas da planaridade, destacando a influência desse conceito em problemas geométricos fundamentais. Tais problemas são derivados da fórmula de Euler e suas diversas aplicações. Também problemas topológicos, como o problema de coloração de mapas, são estudados na dissertação. A teoria de grafos tem extensiva utilização em matemática aplicada, pois demonstra ser uma poderosa ferramenta para a modelagem de diversas situações reais em física, química, biologia, engenharia elétrica e pesquisa operacional. Tanto em problemas práticos como em problemas teóricos tem-se o fato que a maioria das aplicações admitem métodos de resolução mais eficientes se o grafo associado for planar. A determinação da planaridade de um grafo é importante em diversas aplicações na indústria, engenharia e outras. Um aspecto neste estudo é que a planaridade é uma propriedade preservada mediante o isomorfismo de grafos. Também apresenta-se duas caracterizações da planaridade, uma devido a Kuratowski e outra devido a Wagner. São dois resultados clássicos da teoria de grafos, que identificam condições necessárias e suficientes para um dado grafo ser planar, e cujas técnicas de demonstração são ainda importantes em combinatória. / The main goal of this work is to treat the geometrical and topological implications of planarity, highlighting the infl.uence of t his concept over fundamental problems. Such problems are derived from the Euler's formula and its applications. Topological problems, such as map colouring, are also dealt with in this thesis. Graph theory has extensive use in applied mathematics, because it shows to be a powerful tool for modelling real situations in physics, chemistry, biology, electrical engineering and operational research. In theory, as well as in practical problems, it is the fact most applications admit more efficient solution methods if the associated graph is planar. The determination of the planarity of a graph is important in various applications in industry, engineering and others. An aspect of this survey is that planarity is an invariant property preserved throu~h graph isomorphisms. It is also presented two characterizations of planarity. One is due to Kuratowski and the other is due to Wagner. These are two classical results of graph theory, that identify necessary and sufficient conditions for a graph to be planar, whose t echniques are still important in combinatorics.

Orientador: João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da ComputaçãO / Made available in DSpace on 2018-07-21T05:57:00Z (GMT). No. of bitstreams: 1 Cruz_CarlosFernandoBella_M.pdf: 2090300 bytes, checksum: c7ddb8099b731928143e26f66c270afc (MD5) Previous issue date: 1996 / Resumo: Abordamos os principais algoritmos para o problema de emparelhamento máximo em grafos genéricos e desenvolvemos uma implementação paralela eficiente na prática, baseada no algoritmo seqüencial de Edmonds. Por prática entendemos uma implementação eficiente num multiprocessador de memória com partilhada. A implementação consiste em permitir que cada processador procure caminhos aumentantes no grafo de forma assíncrona e independente dos demais. Embora a busca ocorra de forma paralela, o aumento do emparelhamento é feito por somente 1 processador por vez, o que garante a corretude do algoritmo sem incorrrer em atraso significativo no tempo de execução. O desenvolvimento da implementação teve como antecedente uma experiência negativa de paralelização baseada no algoritmo de Micali e Vazirani. / Abstract: In this work we present the most important matching algorithms for general graphs and develop an efficient parallel implementation in practice based on Edmonds'matching algorithm. By practice we mean an efficient implementation on a shared memory multiprocessor. The implementation allows each processor to find augmenting paths assinchronously and independently of each other. Each matching augmentation is done by only one processor, and this makes the algorithm correct without causing significant delay in the execution time, in practice. The development of this implementation was made after a nega tive experience of paralelization based on the sequential algorithm of Micali and Vazirani. / Mestrado / Mestre em Ciência da Computação

Orientador: Jose Carlos de Souza Kuhl / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-21T06:32:26Z (GMT). No. of bitstreams: 1 Mandolesi_AndreLuisGodinho_M.pdf: 916932 bytes, checksum: 4084536e3bb119fcc98ed699188e3f8e (MD5) Previous issue date: 1996 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática

Orientador: Marcius Fabius Henrique de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas. Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-07-26T21:25:37Z (GMT). No. of bitstreams: 1 Furtado_PythagorasGrangeiro_M.pdf: 2514612 bytes, checksum: ac05ec10fe71f6b82b8c79cd0b14cece (MD5) Previous issue date: 2000 / Resumo: Este trabalho caracterizou-se por duas atividades principais: 1) desenvolvimento de ambiente computacional para modelagem de sistemas produtivos, visando o planejamento da produção de sistemas de manufatura; 2) implementação de um algoritmo especial para aproveitamento da estrutura de fluxo em redes do problema relacionado com o sistema produtivo em questão, visando melhor desempenho deste sistema. O objetivo do trabalho foi criar uma nova ferramenta de software com uma interface amigável, constituída por uma linguagem visual/simbólica, possibilitando ao usuário não-especialista construir modelos de sistemas produtivos, segundo a abordagem de fluxo em redes. Faz parte desta ferramenta um algoritmo para obtenção da solução otimizante do problema matemático inerente ao modelo proposto pelo usuário. Este algoritmo ou solver considera características especiais da estrutura esparsa das matrizes relacionadas com o problema / Abstract: This work considers two main topics: 1) the development of modeling environrnent for production planning; 2) the implementation of special algorithm to explore the structure of the production planning problem. The objective of the first topic is the development of an environrnent composed of a man-machine user-friendly interface based on a visuallanguage that allows the users to represent production planning problems through graph models. These models are transformed into mathematical network flows models. The second topic try to take advantage of the special structure of the mathematical model, regarding to the sparse characteristic of the constraints matrices related with the problem and to implement a special algorithm (solver). Finally, a performance comparison shows some advantages and drawback ofthis approach / Mestrado / Mecanica dos Sólidos e Projeto Mecanico / Mestre em Engenharia Mecânica

Orientador : Alexandre Xavier Falcão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T19:58:39Z (GMT). No. of bitstreams: 1 Cunha_BrunoSantosda_M.pdf: 6812183 bytes, checksum: 0d97298986902b62c8b3a8b313835b23 (MD5) Previous issue date: 2001 / Resumo: Diversos problemas em processamento e análise de imagens podem ser abordados como um problema de particionamento ótimo de uma imagem baseado em pixels sementes. A transformada imagem-floresta (1FT) se propõe a resolver tais problemas de maneira unificada e eficiente, a partir do cálculo de florestas de caminhos mínimos. Podendo ser considerada uma generalização de trabalhos voltados para a segmentação de imagens baseada em bordas, a 1FT já foi utilizada para segmentação baseada em regiões, cálculo de linhas divisoras de águas e cálculo de transformadas de distância, inclusive baseadas na métrica Euclideana. Neste trabalho acrescentamos novos operadores ao contexto da 1FT, como métodos de segmentação de imagens baseada em conexidade fuzzy, geração de esqueletos multi­escala e operadores conexos. Realizamos comparações qualitativas e quantitativas com outros operadores descritos na literatura, além de apresentar exemplos de aplicações em imagens médicas e em vídeo digital. Exploramos também algumas questões de cunho teórico, como provas de corretude, análises de complexidades computacionais e garantias de qualidade do resultado de alguns métodos / Abstract: In image processing and analysis, many problems can be thought of as an optimal image partition problem based on seed pixels, where each seed defines an influence zone compo­sed by its "closest" pixels. The image foresting transform (1FT) is a unified and efficient approach to solve these problems, by reducing them into a shortest-path forest problem in a graph. It is an extension of previous works on boundary-based image segmenta­tion methods, and it has already been used to design operators for region-based image segmentation, watershed transform and Euclidean distance transformo In this work we add new image processing operators to the 1FT framework, like image segmentation based on fuzzy connectedness, multiscale skeletons and connected operators. We make qualitative and quantitative comparisons with other operators described in the literature, and present some examples in medical imaging and digital video. We also explore some theoretical aspects, such as correctness proofs, complexity analysis and quality assurances of the results of some operators / Mestrado / Mestre em Ciência da Computação

Orientador : João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-02T14:52:50Z (GMT). No. of bitstreams: 1 Conceicao_ArlindoFlavioda_M.pdf: 1967561 bytes, checksum: 27b15ad3216c72fe882e027f64fc719e (MD5) Previous issue date: 2000 / Resumo: Nesta dissertação estudamos o aspecto combinatório dos problemas de congestionamento. O principal problema estudado consiste em, dado um grafo G e um inteiro positivo k, encontrar k árvores espalhadas de G, não necessariamente disjuntas, de peso total mínimo. Neste problema o congestionamento é caracterizado por funções que penalizam o peso de uma aresta se ela é usada por mais de uma árvore. Roskind e Tarjan apresentaram um algoritmo para a versão deste problema onde as árvores devem ser disjuntas nas arestas. Nós apresentamos uma descrição detalhada do algoritmo de Roskind e Tarjan e então mostramos um algoritmo polinomial para o problema de congestionamento, o algoritmo consiste em uma redução ao problema disjunto. O nosso algoritmo é quadrático em k. Apresentamos ainda duas heurísticas de complexidade linear em k. Baseados na mesma técnica, desenvolvemos algoritmos polinomiais para problemas combinatórios de congestionamento relacionados aos problemas de encontrar um caminho mínimo e de encontrar um emparelhamento de custo mínimo / Abstract: This work studies the combinatorial aspects of congestion problems. The main problem studied is the following: Given a graph G and a positive integer k, we want to find k spanning trees on G, not necessarily disjoint, of minimum total weight, such that the weight of each edge is subject to a penalty function if it belongs to more than one tree. This penalty function models congestion situations. Roskind and Tarjan have developed an algorithm for the disjoint version of this problem. We present a detailed description of their algorithm and then show that a polynomial algorithm for the congestion problem can be obtained by reducing it to the disjoint problem. The complexity of our algorithm is quadratic in k. We also present two heuristics with complexity linear in k. Based on the same idea, we then present polynomial algorithms for combinatorial congestion problems related to shortest paths and minimum weight matchings / Mestrado / Mestre em Ciência da Computação

Orientador: Alexandre Xavier Falcão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-03T19:18:14Z (GMT). No. of bitstreams: 1 Bergo_FelipePauloGuazzi_M.pdf: 2903070 bytes, checksum: f8902d34fd2d17a55acd13552cd66d54 (MD5) Previous issue date: 2004 / Mestrado

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-03T20:15:11Z (GMT). No. of bitstreams: 1 Stecca_FlaviodeFreitas_M.pdf: 2291737 bytes, checksum: 854734e6990e1e125c61b7312d5f1056 (MD5) Previous issue date: 2003 / Resumo: Esta dissertação aborda o problema da coloração de arestas restrito aos grafos indiferença. O teorema de Vizing diz que qualquer grafo pode ter suas arestas coloridas com .6 (G) ou .6( G) + 1 cores. Grafos pertencentes à Classe 1 são os grafos cujo índice cromático (n úmero mínimo de cores suficientes para pintar suas arestas) X' é igual a .6 ( G) . Se X' = .6(G) + 1, o grafo pertence à Classe 2. Um grafo é dito overfull se .6(G) l_J < m, onde nem são o número de vértices e o número de arestas, respectivamente. Grafos neighborhood overfull são grafos que têm um vértice de grau máximo cuja vizinhança induz um subgrafo overfull. Grafos indiferença overfull ou neighborhood overfull pertencem à Classe 2. Apresentaremos uma breve compilação de resultados de pesquisas. Dois destes resultados mostram que grafos indiferença com grau máximo ímpar e grafos indiferença reduzidos pertencem à Classe 1, porém o problema ainda está em aberto para um grafo indiferença qualquer. Abordamos o problema criando um modelo de programação linear para coloração de arestas. Implementamos um gerador que nos permitiu gerar grafos indiferença de dife-rentes estruturas. Estes grafos tiveram suas arestas coloridas através de programação linear. Definimos um tipo especial de grafo indiferença denominado grafo indiferença semi-universal. Criamos um método que permite cobrir um grafo indiferença com grafos indiferença semi-universais. Mostramos que resolver o problema para um grafo indife-rença qualquer equivale a estender certas colorações parciais para um grafo indiferença semi-universal qualquer. Reforçamos a conjectura de que todos os grafos indiferença não neighborhood overfull são Classe 1, através de testes práticos em milhares de grafos indi-ferença / Abstract: This dissertation is on the subject of edge coloring restricted to indifference graphs. Vi-zing's theorem states that any graph can be edge-colored with .6. or .6. + 1 colors. Graphs are said to be Class 1 if their chromatic index (minimum number of colors required to produce an edge-coloring) X ' equals .6.( G). If X ' = .6.( G) + 1 the graph is said to be Class 2. A graph is overfull if .6. (G) l _ J < m, where n and m are the number of vertices and number of edges, respectively. Graphs are said to be neighborhood overfull if they have a maximum-degree vertex whose neighborhood induces an overfull subgraph. Overfull and neighborhood overfull indifference graphs are Class 2. vVe will show a brief compilation of research results. Two of these results show that indifference graphs with odd maximum degree and reduced indifference graphs are Class 1, however the problem is open for a generic interference graph. The approach used for the problem was the creation of a linear programming mo dei for edge coloring. A graph generator program that allowed creation of indifference graphs with different structures was implemented. These graphs were edge colored using linear programming. We defined a special type of graph called semi-universal indifference graph. We created a method for covering an indifference graph with semi-universal indifference graphs. We show that solving the problem for indifference graphs is equivalent to ex-tending a partial edge coloring in a semi-universal indifference graph. We reinforce the conjecture that says that all indifference graphs not neighborhood overfull are Class 1, through practical tests in thousands of indifference graphs / Mestrado / Mestre em Ciência da Computação

Made available in DSpace on 2014-06-12T18:33:40Z (GMT). No. of bitstreams: 2 arquivo934_1.pdf: 678753 bytes, checksum: af8d8f157b72162d2a4446bf7978c0c6 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Universidade Federal de Pernambuco / O Polinômio de Tutte generaliza alguns polinômios usados para contar estruturas em grafos, tais como colorações e fluxos. Não obstante, é mais naturalmente definido para matróides. Em termos mais formais, é essencialmente o único invariante polinomial com comportamento multiplicativo para soma direta de matróides ou uniões disjuntas de grafos conexos. Adicionando alguma complexidade em sua formulação, é possível capturar nele as simetrias de um grafo por um argumento de contagem de órbitas de grupos. Com outro viés, é possível codificar algebricamente uma matróide atribuindo pesos para os seus elementos ao construirmos uma variação do Polinômio de Tutte, o que resulta praticamente na função de partição do modelo de Potts

Orientador : Mario Jino / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-13T23:27:16Z (GMT). No. of bitstreams: 1 Carnassale_Mauro_M.pdf: 4907860 bytes, checksum: 9ae042cdd1fd83ffb5b10d25f8855a73 (MD5) Previous issue date: 1991 / Resumo: Grafos de programa têm sido utilizados há muito tempo e, apesar de serem um conceito tradicional, sua aplicabilidade atual é grande e crescente. Muitas ferramentas e alguns ambientes utilizam-se dessa representação da estrutura lógica do Programa para atingirem seus objetivos. O propósito deste trabalho é apresentar a arquitetura, aspectos fundamentais de implementação e principais aplicações de uma ferramenta que produz o grafo de programa a partir de programas escritos em diversas linguagens procedimentais. Os Programas são t raduzidos para uma linguagem intermediária, denominada LI, a partir da qual obtêm-se o grafo de programa e outros produtos relevantes. A ferramenta tambem aceita programas escritos diretament e em LI. Sua finalidade principal é apoiar outras ferramentas ou aplicações que se utilizam do grafo de programa / Abstract; Not informed. / Mestrado / Mestre em Engenharia Elétrica