Изменения
Нет описания правки
Для простоты мы считаем, что носители в обоих матроидах одинаковы, если не так, то дополним их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами.
Давайте зададим функцию <tex>P_1</tex> : <tex> X \times X \rightarrow X</tex>: <tex>P_1((x, y)) = x</tex>, а для матроида множества <tex>M = \langle X \times X, I \rangleB</tex> выполняется <tex>P_1(MB) = \langle X, I' = \{A \subset X|</tex> <tex>\exists B \in I : \forall x \in A</tex> <tex>\exists y \in B : P_1(y) = x\}</tex>.
Определим ещё несколько матроидов, которые нам понадобятся:
<tex>M_{\oplus} = M_1 \oplus M_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> I = \{A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle</tex>.
<tex>M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> I_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex>. Заметим, что <tex>P_1(M_{\oplus}) = M</tex>, поэтому матроид <tex>M = M_{\oplus} \cap M_{P_1}</tex>.
Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов.
