Наследственные структуры и оптимизационные задачи в булевых и геометрических решётках

• Автор: Выплов, Михаил Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Екатеринбург
• Количество страниц: 81 с. : ил.

Оглавление
Введение

1. Аналог теоремы Биркгофа-Уитни для наследственных

систем

1.1. Теорема Биркгофа-Уитни

1.2. Решётки замкнутых множеств конечных наследственных систем

1.3. Решётки замкнутых множеств бесконечных наследственных систем

2. Представление наследственных систем в терминах замыкания и в терминах циклов

2.1. Эквивалентные определения матроида

2.2. Обобщение соответствия между матроидами и операторами замыкания

2.3. Эквивалентные определения наследственной системы

3. Задачи оптимизации модулярных и супермодулярных
функций на порядковых идеалах
3.1. Задача максимизации модулярной функции на Т-матроиде
3.2. Задача максимизации модулярной функции на порядковом идеале
3.3. Задача минимизации супермодулярной функции на Т-матроиде
Заключение
Литература

Введение
Наследственные структуры — объекты, наделённые свойствами наследственности — чрезвычайно широко распространены в дискретной математике. К ним относятся, в первую очередь, наследственные системы — универсальные комбинаторные объекты, сочетающие черты систем независимости (систем подмножеств некоторого, как правило, конечного множества V, обладающих свойством наследственности) и систем множеств с аналогичным свойством наследственности "вверх”. Подмножества множества V, входящие в его систему независимости, называют независимыми, а все остальные множества — зависимыми. Свойство наследственности для независимых множеств формулируется так: любое подмножество независимого множества само независимо. Очевидно, что семейство всех зависимых множеств обладает свойством наследственности "вверх”: любое надмножество зависимого множества является зависимым.
Хорошо изучены частные случаи наследственных систем — матроиды, изначально возникшие на стыке линейной алгебры и теории графов как обобщение понятия линейной независимости в векторных пространствах. Решётка подпространств (т. е. замкнутых множеств) любого матроида является геометрической, а обыкновенные матроиды часто определяют как комбинаторные геометрии, рассматривая те и другие как операторы замыкания специального вида, заданные на подмножествах множества V.
Семейство независимых множеств любой наследственной системы или матроида молено рассматривать как порядковый идеал булевой решётки всех подмножеств конечного множества V. Тогда семейство всех за-

висимых множеств будет порядковым фильтром этой решётки. Таким образом, понятия порядкового идеала и соответствующего фильтра произвольной решётки являются обобщениями понятия наследственной системы. Пожалуй, наиболее близки по своим свойствам к наследственным системам порядковые идеалы и фильтры геометрических решёток, что можно объяснить атомарностью последних: как и в булевой решётке, каждый элемент геометрической решётки является объединением некоторого подмножества атомов. В геометрической решётке может быть введено понятие П-матроида как обобщение понятия матроида в булевой решётке.
Наследственные системы и матроиды являются адекватными моделями множеств допустимых решений большого числа дискретных оптимизационных задач. Многие из этих задач могут быть представлены как задачи максимизации модулярных функций на наследственных системах или задачи минимизации супермодулярных функций на матроидах.
С матроидами тесно связан интерес к жадному алгоритму, представляющему собой эффективный метод точного или приближённого решения ряда задач дискретной оптимизации.
Целью работы является исследование структуры и комбинаторных свойств наследственных систем, изучение решёток замкнутых множеств наследственных систем, рассмотрение эквивалентных определений наследственных систем в терминах замыкания и в терминах циклов, а также приближённое решение жадным алгоритмом дискретных оптимизационных задач на решёточных аналогах наследственных систем и матроидов (порядковых идеалах и Ь-матроидах) с модулярными и су-пермодулярными целевыми функциями.
В работе используются методы теории матроидов, теории решёток, элементы теории графов, методы дискретной оптимизации и анализа алгоритмов в худшем случае.
Приведём определения основных понятий и краткую сводку известных результатов, относящихся к теме исследования.

Имеет место следующий аналог теоремы Биркгофа-Уитни для бесконечного случая.
Теорема 1.3. 1) Решётка замкнутых множеств любой наследственной системы не содерокит бесконечных цепей.
2) И обратно, для любой непустой решётки Ь, не содержащей бесконечных цепей, существует наследственная система, решётка замкнутых множеств которой изоморфна Ь.
Доказательство. 1) Первое утверждение доказывается в точности так же, как в теореме Биркгофа-Уитни. Пусть Н — наследственная система, Ь(У)-— решётка её замкнутых множеств. Если в Ь{У) существуют бесконечные цепи, то они должны содержать счётно-бесконечную возрастающую цепь или счётно-бесконечную убывающую цепь. Пусть Аг < А2 <
...— некоторая возрастающая цепь в Ь{У). Согласно свойству конечного базиса ( А2 > ... — убывающая цепь в В (У), то выберем элементы а, Е А, А,+ и положим А = {01, <22,...}, V, = {а,, а(+1,...}. Так как Уг+1 С Аг+х, то аг Е Уг+ при всех г. Положим Вг = А {аг} и допустим, что а, € Вг. Выбирая максимально возможное ], для которого ещё аг Е V, {аг} (д < г, потому что а, Е К+1), заключаем, что аг ^ У]+ {аг} = (У0 {а,}) {аД, а отсюда, согласно аксиоме замены, а■) Е У]+1- Противоречие. Поэтому вопреки аксиоме конечного базиса не существует конечного подмножества А, имеющего то же замыкание, что и А.
2) Пусть I/ — произвольная непустая решётка, не содержащая бесконечных цепей. Докажем, что существует такой клаттер С = {У, £), удовлетворяющий аксиоме конечного базиса, что решётка его замкнутых множеств изоморфна Ь.
Построим гиперграф С с помощью алгоритма А2. В силу леммы 1.3 семейство его замкнутых множеств совпадает с семейством замкнутых