322
правки
Изменения
Нет описания правки
Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов.
Множество <tex>U</tex> - независимо, если <tex>r(U) = |U|</tex>.
А можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \in M_{\oplus}I, A \in I_{P_1}, P_1(A) \subset U} |UA|</tex>.
Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. Мы это уже умеем делать - [[Алгоритм построения базы в пересечении матроидов]].
== Литература ==
Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
