Алгоритм построения базы в пересечении матроидов
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Задача: |
Даны матроиды пересечении и . | и . Необходимо найти максимальное по мощности независимое множество в
Алгоритм решения
Пусть множество
Определим граф замен , где
.
Пусть
, , — кратчайший путь из в в графе . может и не существовать.Лемма: | ||||||||||
Если в графе нет пути из в , то — искомое максимальное по мощности независимое множество в пересечении и . | ||||||||||
Доказательство: | ||||||||||
Отметим, что если или пустые, то — база в одном из исходных матроидов или и, следовательно, искомое максимальное по мощности независимое множество в пересечении и . Таким образом, предположим, что и непусты. Пусть — множество вершин, из которых достижимы вершины из . Отсутствие пути из в означает, что , и (т.е. в не входит ни одной дуги). Тогда:
| ||||||||||
Лемма: |
Доказательство: |
Пусть лемме о единственном паросочетании в подграфе замен, . К тому же, , иначе — не кратчайший путь из в . Это означает, что , то есть . Так как (т.е. . Симметрично . Тогда и дуги из в составляют единственное полное паросочетание в . То есть, согласно и, следовательно, . |
Псевдокод
граф замен кратчайший путь из в if = else isMaximal = true= isMaximal = false while not isMaximal построить
Подсказки
- Воспользуйтесь одним массивом для проверки множества на независимость по цветам,
- для проверки ацикличности графа при добавлении ребра можно использовать СНМ или обходом в глубину,
- для нахождения кратчайшего пути можно использовать обход в ширину, первоначально добавив фиктивную вершину, соединив её с вершинами из множества .
Теорема Эдмондса-Лоулера
Теорема (Эдмондса-Лоулера): |
Пусть , — матроиды. Тогда Где . и — ранговые функции в первом и втором матроиде соответственно. |
Доказательство: |
Докажем неравенство Выберем произвольные , , тогда
и — независимые в обоих матроидах (как подмножества независимового ), значит
Но и , значит
В силу произвольности и получаем
Обозначим Построим , . Если , добавим их пересечение в . граф замен . Добавим вершину , не влияющую на независимость в первом матроиде — из неё будут вести рёбра во все вершины множества . Пусть — кратчайший путь из в , — путь с добавленным в начало ребром из . По лемме о единственном паросочетании и лемме о единственном паросочетании, индуцированном кратчайшем путём . Теперь добавим вершину , не влияющую на независимость во втором матроиде — в неё будут вести рёбра из всех вершин множества . Тогда (путь с добавленным ребром в ) — кратчайший путь из в . Аналогично, . Отсюда следует, что , причём .Будем таким образом увеличивать , пока существует путь . Рассмотрим момент, когда такого пути не нашлось. Введём обозначение: .Докажем, что от противного. Пусть , тогда существует , такое, что . Если , то и из есть путь в . Значит, . Отсюда следует, что существует , такое что . Но тогда ребро имеется в графе, то есть из существует путь в , что противоречит условию .Следовательно, Построен пример равенства, значит, теорема доказана. . Аналогично, . Отсюда , то есть при найденных и достигается равенство. |
См. также
Источники информации
- Chandra Chekuri — Combinatorial Optimization