Изменения

'''Объединение матроидов''' <tex>M</tex> = <tex>\langle S,J \mathcal{I} \rangle</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S,J_i \mathcal{I}_i \rangle</tex>

Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in J_i\mathcal{I}_i</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in J_i\mathcal{I}_i</tex>.

<tex>F_i = \{ x \in S \setminus I_i : I_i + x \in J_i \mathcal{I}_i \}</tex>. <tex>F</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>F_i</tex>

Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. Иначе говоря, на каждом шаге мы выбираем элемент не из текущего множества, который оставит построить [[Граф замен|граф замен]] <tex>D_{M_i}(I_i)</tex>текущее множество независимым ([[Алгоритм построения базы в объединении матроидов#th_1|следующая теорема]] отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как <tex>I</tex>.

isMaximal = ''false'for' ''<tex>i \leftarrow 0</tex> 'while''to' '''not''' isMaximal<tex>n - 1</tex> построить [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2M_i}(JI_i)</tex> <tex>X_1 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_1 \}</tex> <tex>X_2 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_2 \}</tex> <tex>P</tex> <tex>\leftarrow</tex> кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex> '''if''' <tex>P I_i + x \ne in \emptysetmathcal{I}_i</tex> <tex>J</tex> = <tex>J \bigtriangleup V(P)leftarrow I_i + x</tex> '''else''' isMaximal = ''true''