Matróides induzidas por empacotamentos em grafos com pesos

Abstract

Esta dissertação se propõe a explorar o artigo intitulado Matroids induced by packing wheited subgraphs de M. Lemos. Apresentamos, baseado no artigo de M. Loebl e S. Poljak, On Matroids induced by packing subgraphs, uma família F, de subgrafos de G que preservam a propriedade de o conjunto dos vértices cobertos por algum F-empacotamento gerarem uma matróide. Introduzimos os conceitos de família hipoemparelhável, H, e família fechada de propulsores enraizados , e mostramos que se F = H[, os conjuntos dos vértices dos F,-empacotamentos de peso máximo de uma matróide, com pequenas restrições à função peso, formam uma matróide