Изменения

А можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \in I, A \in I_{P_1}, P_1(A) \subset U} |A|</tex>.

Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. Мы это уже умеем делать - [[Алгоритм построения базы в пересечении матроидов]].

== Литература ==

* Chandra Chekuri {{---}} [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf '''Combinatorial Optimization''']

* https://en.wikipedia.org/wiki/Matroid