Made available in DSpace on 2014-06-12T18:29:19Z (GMT). No. of bitstreams: 2 arquivo4282_1.pdf: 1806381 bytes, checksum: d8e5341810eebc7820e9231598a88d15 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Fundação de Amparo a Pesquisa do Estado da Bahia / A caracterização de matróides através de sua circunferência iniciou-se com a publicação dos artigos Matroids Having Small Circumference, Combinatorics, Probability and Compumting (2001) 10, 349-360 e Connected matroids with a small circumference, Discrete Mathematics 259 (2002) 147-161 de Braulio Maia Junior e Manoel Lemos, onde eles construíram todas as matróides com circunferência menor ou igual a 5. Recentemente, em The 3-connected binary matroids with circumference 6 or 7, European Jounal of Combinatorics ( a ser publicado), Raul Cordovil,Maia Junior e Lemos construíram todas as matróides binárias 3-conexas de circunferência 6 e 7, contudo eles trabalharam apenas com matróides de posto pelo menos 8. Nesta tese construímos todas as matróides binárias de circunferência 6 e posto pequeno, isto é, as matróides de posto 5, 6 e 7. Com base no resultado de Bixby(1972), Cunningham(1973) e Seymour(1980), que diz: Uma matróide 2-conexa M não é 3-conexa se e somente se M = M1⊕2M2, onde M1 e M2 são matróides conexas, cada uma isomorfa a um menor próprio de M, concluímos que para estudar as matróides de posto pequeno é suficiente conhecer as matróides binárias com e-circunferência 3, 4 e 5. Como Maia Junior já havia construído as matróides 3-conexas com e-circunferência 3 e 4, bastava-nos construir as matróides binárias com e-circunferência 4 e 5. Iniciamos descrevendo todas as matróides 3-conexas binárias de circunferência 6 e posto 7 e posteriormente descrevemos todas as matróides binárias 3-conexas com circunferência 6 e posto 6. Assim foi possível conhecer todas as matróides 3-conexas com e-circunferência 5. Conseguimos também construir as matróides binárias não 3-conexas com e-circunferência 4 e 5. Estes resultados nos fornecem uma completa descrição de todas as matróides binárias não 3-conexas de circunferência 6 e posto pequeno

Made available in DSpace on 2014-06-12T18:27:29Z (GMT). No. of bitstreams: 2 arquivo1002_1.pdf: 528686 bytes, checksum: 535bcf01de6958ff7151de8b39e5c67f (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Universidade Federal Rural de Pernambuco / Nesta dissertação provaremos uma conjectura proposta por Leo : uma matróoide M minimalmente 3-conexa suficientemente grande tem pelo menos 5|E(M)|+30 9 dos seus elementos pertencentes a alguma tráade. Também é fornecida uma cota para o número de elementos pertencentes a tríades em matróides 3-conexas com poucos elementos removíveis. Ambas as cotas são atingidas e são construidas famílias infnitas de matróides que atingem tais cotas. É feita ainda uma nova demonstraçao de resultados obtidos por Lemos e Leo sobre tríades que intersectam circuitos com no máximo um elemento removível em matróides 3-conexas

Submitted by ANA FLAVIA MARIANO DE SOUSA null (flavinha455@hotmail.com) on 2016-10-17T20:55:50Z No. of bitstreams: 1 Dissertação final imprimir.pdf: 3125220 bytes, checksum: 761d821c6466a0e1358b2a44c7b1c9f2 (MD5) / Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2016-10-20T19:22:54Z (GMT) No. of bitstreams: 1 sousa_afm_me_rcla.pdf: 3125220 bytes, checksum: 761d821c6466a0e1358b2a44c7b1c9f2 (MD5) / Made available in DSpace on 2016-10-20T19:22:54Z (GMT). No. of bitstreams: 1 sousa_afm_me_rcla.pdf: 3125220 bytes, checksum: 761d821c6466a0e1358b2a44c7b1c9f2 (MD5) Previous issue date: 2016-10-10 / Nesse trabalho, consideramos o conceito de variedades topológicas. Porém, nos especializamos nas variedades conexas de dimensão 2, as chamadas superfícies. Nosso objetivo é o estudo da classificação topológica das superfícies compactas. Para isto, enunciamos e demonstramos o Teorema de classificação das superfícies compactas. Desta maneira, mostramos que toda superfície compacta orientável é homeomorfa à esfera ou a uma soma conexa de toros, e que toda superfície compacta não orientável é homeomorfa a uma soma conexa de planos projetivos. / In this work, we consider the concept of a topological manifold. However, we focus on the connected 2-dimensional manifolds, the so-called surfaces. Our goal is the study of the topological classification of the compact surfaces. In this direction, we state and prove the classification Theorem of compact surfaces. That is, we show that every orientable compact surface is homeomorphic to the sphere or to a connected sum of torus, and every non-orientable compact surface is homeomorphic to a connected sum of projective planes.

Submitted by Etelvina Domingos (etelvina.domingos@ufpe.br) on 2015-03-06T17:52:49Z No. of bitstreams: 2 tese_digital_iveslima.pdf: 1006004 bytes, checksum: ac61098b56ddbddb7ebe29a13f4edc2d (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-06T17:52:49Z (GMT). No. of bitstreams: 2 tese_digital_iveslima.pdf: 1006004 bytes, checksum: ac61098b56ddbddb7ebe29a13f4edc2d (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012 / CAPES / Seja M uma matroide 3-conexa menor-minimal possuindo a matroide N como menor. Em 2003, Lemos e Oxley obtiveram uma estimativa para diferença |E(M) − E(N)| e mostraram que o resultado obtido é o melhor possível, quando o menor N é conexo. Nesta tese, mostramos que esta estimativa pode ser melhorada quando o menor N é uma matroide circular, desde que M não possua um menor isomorfo ao prisma.

Made available in DSpace on 2014-06-12T18:31:13Z (GMT). No. of bitstreams: 2 arquivo8545_1.pdf: 1387918 bytes, checksum: f45c75e1c26e36767432de4b52d087a9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2005 / Circuitos e cocircuitos não-separadores são muito importantes para a compreensão das matróides gráficas. Por exemplo, Tutte [27] caracterizou os grafos 3-conexos planares usando o conceito de circuitos não-separadores. Bixby e Cunningham [2] generalizaram esse resultado para a classe das matróides binárias. Kelmans [11] e independentemente Seymour (veja [16]) provaram que cada matróide binária, conexa, simples e co-simples tem pelo menos um cocircuito não-separador. McNulty e Wu [15] provaram que essas matróides têm no mínimo quatro cocircuitos não-separadores, sendo este resultado o melhor possível. Lemos [14] calculou, para matróides binárias 3-conexas, a dimensão do subespaço do espaço dos cociclos gerado pelos cocircuitos não-separadores que evitam um elemento da matróide. Nesta tese, á fornecido um limite inferior para a dimensão de um tal subespaço gerado pelos cocircuitos não-separadores que evitam um conjunto com no mínimo dois elementos da matróide. Inicialmente, será feita uma abordagem geral da teoria das matróides utilizada para provar os principais resultados encontrados nesta tese, apresentados em seguida. No segundo capítulo, o problema de encontrar cocircuitos não-separadores de uma matróide binária, conexa, simples e co-simples será reduzido ao problema de encontrar cocircuitos não-separadores evitando, no máximo, dois elementos em matróides binárias 3-conexas. No terceiro capítulo, serão caracterizadas as matróides binárias 3-conexas sem cocircuitos não-separadores que evitam um 2-subconjunto do conjunto de elementos da matróide. Este resultado é essencial para o cálculo da dimensão do subespaço do espaço dos cociclos gerado pelos cocircuitos não-separadores que evitam um 2-subconjunto do conjunto de elementos de uma matróide binária 3-conexa. Será feito ainda o cálculo da dimensão de um tal subespaço quando o subconjunto de elementos evitado por esses cocircuitos é um triângulo da matróide. Além disso, será determinada a dimensão do mesmo subespaço para cocircuitos não-separadores que evitam uma coleção qualquer dos elementos de uma matróide binária 3-conexa, desde que a restrição da matróide a esse conjunto não tenha colaço

Estudamos inicialmente resultados de classificação de difeomorfismos de produtos de esferas de mesma dimensão. Tratado isto, estudamos os mergulhos suaves de produtos de três esferas, sendo a primeira de dimensão um e as demais de dimensão maior ou igual a um, com a dimensão da última maior ou igual a da segunda, em uma esfera em codimensão um, e buscamos a total caracterização do fecho das duas componentes conexas do complementar de tais mergulhos. Tratamos com enfoque especial os mergulhos do produto de três esferas de dimensão um na esfera de dimensão quatro, e, finalmente, estudamos problemas de classificação de mergulhos PL localmente não-enodados de somas conexas de toros em codimensão um. / We study initially results of classification of difeomorfisms of Cartesian products of spheres of same dimension. Treated this, we study the smooth embeddings of cartesian products of three spheres, being the first one of dimension one and excessively of bigger or equal dimension to one, with the dimension of the last equal greater or of second, in a sphere in codimension one, and search the total characterization of the latch of the two connected components of complementing of such embeddings. We deal with special approach the embeddings of the product to three spheres to dimension one in the sphere dimension four, and, finally, we study problems of classification of PL locally unknotted embeddings of connected sums of torus on codimension one.

Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximação / In this dissertation we study algorithmic aspects of the following problem, known as the balanced connected partition. Given a connected graph G with weights defined on its vertices, and an integer q >= 2, find a partition of the vertices of G into q classes such that each class induces a connected graph, and furthermore, when we consider the sum of the weights of the vertices in each class, the smallest sum is as large as possible. In other words, the q classes must have weights that are as balanced as possible. This problem is known to be NP-hard. We mention some computational complexity and algorithmic results that are known for this problem. We present some heuristics that we designed, all of them based on the use of the polynomial algorithm for trees, due to Perl and Schach, which we show in detail. We implemented four heuristics and a 3/4-approximation algorithm that is known for q=2. We run tests on many random instances, of graphs with different weights and densities. The computational results indicate that the performance of these heuristics --- all of polynomial time complexity --- are very satisfactory. For q=2, we observed that the most expensive heuristic produced solutions with values which are systematically better or equal to those produced by the approximation algorithm.

Estudamos inicialmente resultados de classificação de difeomorfismos de produtos de esferas de mesma dimensão. Tratado isto, estudamos os mergulhos suaves de produtos de três esferas, sendo a primeira de dimensão um e as demais de dimensão maior ou igual a um, com a dimensão da última maior ou igual a da segunda, em uma esfera em codimensão um, e buscamos a total caracterização do fecho das duas componentes conexas do complementar de tais mergulhos. Tratamos com enfoque especial os mergulhos do produto de três esferas de dimensão um na esfera de dimensão quatro, e, finalmente, estudamos problemas de classificação de mergulhos PL localmente não-enodados de somas conexas de toros em codimensão um. / We study initially results of classification of difeomorfisms of Cartesian products of spheres of same dimension. Treated this, we study the smooth embeddings of cartesian products of three spheres, being the first one of dimension one and excessively of bigger or equal dimension to one, with the dimension of the last equal greater or of second, in a sphere in codimension one, and search the total characterization of the latch of the two connected components of complementing of such embeddings. We deal with special approach the embeddings of the product to three spheres to dimension one in the sphere dimension four, and, finally, we study problems of classification of PL locally unknotted embeddings of connected sums of torus on codimension one.

Um resultado clássico em Geometria Diferencial, conhecido como teorema de Hadamard, e demonstrado pelo mesmo ([Ha]), estabelece que uma superfície conexa compacta no espaço Euclidiano cujas curvaturas principais são todas positivas é o bordo de um corpo convexo. Em part icular, a superfície é difeomorfa a uma esfera. Neste trabalho apresentamos extensões parciais deste teorema para imersões de codimensão arbitrária e para outros espaços ambientes que o E uclidiano conforme feito em [R]. / A classical result in differential geometry, known as Hadamard's theorem and proved by himself ([Ha]). establishes that a compact connected surface in the Euclidean space whose principal curvatures are everywhere positive is the boundary of a convex body. In particular, the surface is diffeomorphic to a sphere. In this work we present IJartial extensions of this theorem to immersions of arbitrary codimension and to other spaces than the Euclidean one, as clone in [R].

Um resultado clássico em Geometria Diferencial, conhecido como teorema de Hadamard, e demonstrado pelo mesmo ([Ha]), estabelece que uma superfície conexa compacta no espaço Euclidiano cujas curvaturas principais são todas positivas é o bordo de um corpo convexo. Em part icular, a superfície é difeomorfa a uma esfera. Neste trabalho apresentamos extensões parciais deste teorema para imersões de codimensão arbitrária e para outros espaços ambientes que o E uclidiano conforme feito em [R]. / A classical result in differential geometry, known as Hadamard's theorem and proved by himself ([Ha]). establishes that a compact connected surface in the Euclidean space whose principal curvatures are everywhere positive is the boundary of a convex body. In particular, the surface is diffeomorphic to a sphere. In this work we present IJartial extensions of this theorem to immersions of arbitrary codimension and to other spaces than the Euclidean one, as clone in [R].