Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.ufpe.br/handle/123456789/7529
Title: Cobertura e empacotamento por circuitos através de um elemento em matróides
Authors: Paulo Castalonga, João
Keywords: Empacotamento;Cobertura;Conectividade;Matróides
Issue Date: 2007
Publisher: Universidade Federal de Pernambuco
Citation: Paulo Castalonga, João; José Machado Soares Lemos, Manoel. Cobertura e empacotamento por circuitos através de um elemento em matróides. 2007. Dissertação (Mestrado). Programa de Pós-Graduação em Matemática, Universidade Federal de Pernambuco, Recife, 2007.
Abstract: Seja M uma matróide conexa e e um elemento de M tal que M/e seja conexa. Seja CeM o conjunto dos elementos de M que contém e, veM o tamanho de uma maior subfamília Ce na qual cada dois membros se encontram somente em e e 0eM o tamanho de uma maior subfamília de CeM que cobre M. Lemos e Oxley demonstraram que veM + 0eM < r*M + 2, e, em particular, veM + 0eM < r*M + 1 se M não possui um menor F7 usando e. O objetivo deste trabalho é apresentar a prova para tal teorema, bem como a teoria necessária para seu entendimento e algumas de suas consequências. Em paricular, o trabalho inclui alguns resultados importantes em conectividade em matróides(especialmente em 3-connectividade), e, como consequência do teorema principal, um teorema de Seymour, o qual diz que, em uma matróide conexa M, a soma do tamanho de uma maior família de circuitos disjuntos com o tamanho de uma menor família cobrindo M é, no máximo, r*M + 1
URI: https://repositorio.ufpe.br/handle/123456789/7529
Appears in Collections:Dissertações de Mestrado - Matemática

Files in This Item:
File Description SizeFormat 
arquivo8703_1.pdf655.01 kBAdobe PDFView/Open


This item is protected by original copyright



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.