Изменения
Нет описания правки
Определим ещё несколько матроидов, которые нам понадобятся:
<tex>M_{\oplus} = M_1 \oplus M_2 = \langle (X \times \{1\}) \cup (X \times \{2\}), I = \{A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle</tex>,.
Из предыдущей темы ([[Объединение матроидов, доказательство того, что объединение является матроидом]];) мы знаем, что
для <tex>P_1((x, y)) = x</tex> - <tex>P_1(M_{\oplus}) = M</tex>, поэтому матроид <tex>M_{P_1} = \langle I_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex>.
Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов.
Множество <tex>U</tex> - независимо, если <tex>r(U) = |U|</tex>.
А можно заметить, что в матроиде <tex>M</tex> - <tex>r(U) = max_\max\limits_{A \in M_{\oplus}, A \in I_{P_1}, P_1(A) \subset U} |U|</tex>.
Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. Мы это уже умеем делать - [[Алгоритм построения базы в пересечении матроидов]].
