Изменения
→Алгоритм
== Алгоритм ==
Пусть у нас есть множество <tex>I\in\mathcal{I}</tex>, где <tex>\mathcal{I}</tex> — искомое множествобаза матроида, и разбиение <tex>I</tex> на <tex>\bigcup\limits_{i=1}^{n}I_i</tex>, такое, что <tex>I_i\in \mathcal{I}_i</tex>. Также нам дан какой-то Рассмотрим элемент <tex>s\not \in I</tex>. Нужно определить, правда ли, что <tex>I+s\in \mathcal{I}</tex>. Если научиться это делать, то тогда можно решить задачу [[Теорема_Радо-Эдмондса_(жадный_алгоритм)|жадным алгоритмом]], добавляя в текущее множество по одному элементу <tex>s</tex> на каждом шаге.
Определим объединение матроидов как <tex>M</tex> = <tex>\langle S,\mathcal{I} \rangle</tex> = <tex>\bigcup\limits_{i=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_i,\mathcal{I}_i \rangle</tex>.
Для каждого <tex>i</tex> от <tex>1</tex> до <tex>n</tex> возьмем <tex>M_i</tex> и построим [[Основные_определения_теории_графов#.D0.94.D0.B2.D1.83.D0.B4.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84|двудольный ориентированный граф]] <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in \mathcal{I}_i</tex>. Вершины графа — элементы из <tex>S</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 \mathcal{I}_i</tex>.
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет наложением ребер из этих графов, то есть, будет содержать все рёбра всех графов <tex> D_{M_i}(I_i)</tex>.
Для каждого <tex>i</tex> определим множество <tex>F_i</tex> как множество вершин <tex>S_i\setminus I_i</tex> таких, что множество <tex>I_i+x</tex> также независимое. Формально: <tex>F_i = \{ x \in S_i \setminus I_i \mid I_i + x \in \mathcal{I}_i \}</tex>. Определим <tex>F</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>F_i</tex>
{{Теорема
}}
Итак, теперь мы можем описать сам алгоритм. Изначально инициализируем <tex>I</tex> как пустое множествосемейство пустых множеств. На каждом шаге будем строить граф <tex>D</tex> из текущего <tex>I</tex> и <tex>S\setminus I</tex> и добавлять в <tex>I</tex> кандидата-вершину <tex>s</tex>, удовлетворяющую условию теоремы. При добавлении вершины нужно не забыть поменять местами вершины на пути <tex>F \leadsto s</tex>, так как ребра из <tex>I_i</tex> должны вести в <tex>S\setminus I_i</tex> (т.е. должен сохраняться инвариант). Когда вершины-кандидаты закончатся, по доказанной выше теореме получившееся множество <tex>I</tex> станет максимальным.
==Псевдокод==
