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

Made available in DSpace on 2014-06-12T18:28:24Z (GMT). No. of bitstreams: 2 arquivo4258_1.pdf: 1001952 bytes, checksum: e6142e24fe39949000cf8b23eda47a6d (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Muitas situações no dia-dia podem ser descritas por meio de um diagrama que consiste de um conjunto de pontos e linhas que unem certos pares desses pontos. Por exemplo, podemos pensar nos pontos como terminais rodoviários e nas linhas como sendo as estradas. Uma abstração matemática para esse tipo de situação aparece no conceito de grafos. Em 1992, Mayr e Plaxton provaram uma conjectura, proposta por Kano, envolvendo árvores geradoras de grafos com peso. Em 2006, Lemos em seu trabalho intitulado Weight Distribution of the Bases of a Matroid, estende este resultado para matróides. Lemos também prova que as quatro conjecturas devidas a Kano valem para matróides fornecendo uma partição das bases da matróide pela distribuição dos pesos de seus elementos em vez do seu peso. Este trabalho de dissertação tem como objetivo desenvolver os resultados obtidos por Lemos bem como sua conjectura

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: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

Made available in DSpace on 2014-06-12T18:31:43Z (GMT). No. of bitstreams: 2 arquivo8519_1.pdf: 1184960 bytes, checksum: bacaee589325d0137cd7cd316fb23a67 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2003 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O trabalho aqui apresentado consiste no estudo e plicação da teoria relacionada com conjuntos co-geradores de uma matróide, desenvolvida por Alfred Lehman e Jack Edmonds, num jogo chamado Bridge-it. Para tanto, exibimos um algoritmo que encontra, dada uma matróide, um subconjunto maximal de seus elementos, A0, o qual pode ser particionado em k subconjuntos independentes co-geradores, disjuntos, e geradores de A0. Este conjunto A0 está fortemente relacionado com as estratégias dos jogadores