Skip navigation
Use este identificador para citar ou linkar para este item: https://repositorio.ufpe.br/handle/123456789/7529
Título: Cobertura e empacotamento por circuitos através de um elemento em matróides
Autor(es): Paulo Castalonga, João
Palavras-chave: Empacotamento; Cobertura; Conectividade; Matróides
Data do documento: 2007
Editor: Universidade Federal de Pernambuco
Citação: 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.
Resumo: 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
Aparece na(s) coleção(ções):Dissertações de Mestrado - Matemática

Arquivos deste item:
Arquivo Descrição TamanhoFormato 
arquivo8703_1.pdf655,01 kBAdobe PDFVer/Abrir


Este arquivo é protegido por direitos autorais



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.