Нахождение базиса матроида

Материал из Algocode wiki
Перейти к: навигация, поиск

Требуется решить задачу:
Для данного матроида $\langle X,I\rangle$ найти его какой бы то ни было базис.

Пусть размер множества $X$ равен $n$, а размер его базиса $r$, тогда получаем следующие варианты алгоритмов (время дано в вызовах оракула):


АлгоритмВремяПамять
Тупой алгоритм$O(n*r)$$O(r)$
Алгоритм Радо-Эдмондса$O(n)$$O(r)$


Тупой алгоритм

Рассмотрим пустое множество, заметим, что если мы можем добавить в него некоторый элемент $a$ так, чтобы оно оставалось независимым, то ,по свойству базиса, всё ещё будет существовать базис данного матроида, который содержит текущее множество. Будем повторять такие добавления, пока можем. Заметим, что если мы не можем в наше множество добавить ни единого элемента так, чтобы оно перестало быть независимым, то мы нашли базис. Поскольку при каждом добавлении мы просматриваем все элементы в поисках того, который мы добавим, то всего будет совершено $O(n*r)$ вызовов оракула.

Алгоритм Радо-Эдмондса

Утверждение:
Если на каком-то шаге мы не добавили элемент в множество, то мы его больше никогда добавить не сможем

Доказательство:
Пусть мы имеем множество $A$ и элемент $a$ такие, что $A\cup a \notin I \Rightarrow \forall B: A\subset B; B\cup a\notin I$, а добавлением элементов в $A$ мы можем получить лишь множества, содержащие $A \Rightarrow$ мы больше никогда этот элемент $a$ не добавим, а значит и рассматривать его более не требуется

Каждый элемент множества $X$ мы рассмотрим не более одного раза и всего будет сделано $O(n)$ запросов к оракулу.


Автор конспекта: Карп

По всем вопросам пишите в telegram @KS20031501