Incrustaciones de matroides

En combinatoria , una incrustación de matroide es un sistema de conjuntos ( F , E ), donde F es una colección de conjuntos factibles , que satisface las siguientes propiedades. 

1. Propiedad de accesibilidad: Todo conjunto factible no vacío X contiene un elemento x tal que X \ { x } es factible.    
2. Propiedad de extensibilidad: Para cada subconjunto factible X de una base (es decir, conjunto factible máximo) B , algún elemento en B pero no en X pertenece a la extensión ext( X ) de X , donde ext( X ) es el conjunto de todos los elementos e que no están en X tales que X ∪ { e } es factible.    
3. Propiedad de cierre-congruencia: Para cada superconjunto A de un conjunto factible X disjunto de ext( X ), A ∪ { e } está contenido en algún conjunto factible para todos los e o ningún e en ext( X ).      
4. La colección de todos los subconjuntos de conjuntos factibles forma un matroide .

Las incrustaciones de matroides fueron introducidas por Helman, Moret y Shapiro (1993) para caracterizar problemas que pueden ser optimizados por un algoritmo voraz .

• Helman, Paul; Moret, Bernard ME ; Shapiro, Henry D. (1993), "Una caracterización exacta de estructuras voraces", SIAM Journal on Discrete Mathematics , 6 (2): 274– 283, CiteSeerX 10.1.1.37.1825 , doi : 10.1137/0406021 , MR 1215233