Встраивание матроида
В комбинаторике — вложение матроида это система множеств ( F , E ), где F — совокупность допустимых множеств , которая удовлетворяет следующим свойствам.
- Свойство доступности: каждое непустое допустимое множество X содержит элемент x такой, что X \ { x } допустимо.
- Свойство расширяемости: для каждого допустимого подмножества ( т X базиса . е. максимального допустимого множества) B некоторый элемент в B , но не в X, принадлежит расширению ext( X ) X , где ext( X ) — это набор всех элементов. e не принадлежит X такое, что X ∪ { e } допустимо.
- Свойство замыкания-конгруэнтности: для каждого надмножества A допустимого множества X, не пересекающегося с ext( X ), A ∪ { e } содержится в некотором допустимом множестве либо для всех e , либо ни для одного e в ext( X ).
- Совокупность всех подмножеств допустимых множеств образует матроид .
Встраивание матроидов было введено Хелманом, Моретом и Шапиро (1993) для описания задач, которые можно оптимизировать с помощью жадного алгоритма .
Ссылки
[ редактировать ]- Хелман, Пол; Море, Бернар М.Э .; Шапиро, Генри Д. (1993), «Точная характеристика жадных структур», SIAM Journal on Discrete Mathematics , 6 (2): 274–283, CiteSeerX 10.1.1.37.1825 , doi : 10.1137/0406021 , MR 1215233