Алгоритм построения базы в объединении матроидов — различия между версиями
Vsklamm (обсуждение | вклад) (→Алгоритм) |
м (rollbackEdits.php mass rollback) |
(не показана 1 промежуточная версия 1 участника) | |
(нет различий)
|
Текущая версия на 19:30, 4 сентября 2022
Задача: |
Даны матроиды . Необходимо найти максимальное по мощности независимое множество в объединении . |
Определение: |
Объединение матроидов (англ. matroid union) | , где
Алгоритм
Эта задача сводится к пересечению матроидов, однако есть другой способ её решить. Пусть , для с , если . Определим граф замен: для каждого построим двудольный ориентированный граф так, что в левой доле находятся вершины из , а в правой — вершины из . Построим ориентированные ребра из в , при условии, что .
Объединим все
в один граф , который будет суперпозицией ребер из этих графов. Пусть для каждого — множество элементов с . Определим , и .Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом графе замен следующая теорема отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как . Тогда нужно найти такой элемент , что — снова независимо. Все наши кандидаты находятся в . Если мы найдем путь из в , то элемент , которым путь закончился, можно будет добавить в . То есть шаг жадного алгоритма заключается в создании нового и поиске такого пути.
(Псевдокод
граф замен if= for to построить
Время работы
Это подразумевает, что максимальное независимое множество в [1] разработал алгоритм, которым за можно найти максимальное независимое множество в , где максимальный размер множества в , размер подмножества и время, необходимое, чтобы определить принадлежит ли множество для каждого . Более детальное объяснение алгоритма (но не время работы) можно найти у C. Greene и T.L. Magnanti[2].
мы можем найти за полиномиальное время (жадно наращивать независимое множество в ). Cunningham
Теорема: |
Для любого имеем существует ориентированный путь из в по ребрам графа . |
Доказательство: |
Пусть существует путь из в и — самый короткий такой путь. Запишем его вершины как { }. , так что не умаляя общности можно сказать, что . Для каждого определим множество вершин { }, где пробегает от до . Положим, что , для всех положим . Ясно, что . Для того, чтобы показать независимость в объединении матроидов нужно показать, что для всех . Заметим, что так как мы выбирали путь таким, что он будет наименьшим, для каждого существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать . Так как паросочетание единственно, . Аналогично , значит . Следовательно независимо в объединении матроидов.
Пусть нет пути из в по ребрам . Тогда пусть существует множество , состоящее из вершин , из которого мы можем достичь : по допущению . Утверждается, что для всех (что означает, что — максимальное подмножество , независимое в ).Предположим, что это не так. ранга объединения матроидов имеем : , это возможно только если . Значит существует такой , для которого . Но (по предположению вначале доказательства), значит . Из этого следует, что содержит единственный цикл. Значит существует , такой что . Получается, что — ребро в и оно содержит этот , что противоречит тому как был выбран . Следовательно для всех нам известно : . У нас есть и . Из определния функции
и значит — противоречие. |
См. также
Примечания
Источники информации
Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13
Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, — Springer, 2004, — стр.732