Аннотация:
Наследственные структуры — объекты, наделённые свойствами наследственности — широко распространены в дискретной математике. К ним относятся, в первую очередь, наследственные системы и их частный случай — матроиды, а также порядковые идеалы решёток и их частные случаи — L-матроиды. Они объединяют в себе черты многих известных комбинаторных объектов и являются адекватными моделями множеств допустимых решений большого числа дискретных оптимизационных задач. Целью работы является исследование структуры и комбинаторных свойств наследственных систем, изучение решёток замкнутых множеств наследственных систем, рассмотрение эквивалентных определений наследственных систем в терминах замыкания и в терминах циклов, а также приближённое решение жадным алгоритмом задач оптимизации модулярных и супермодулярных функций на наследственных структурах в конечных булевых и геометрических решётках.
|
