Изменения
Нет описания правки
{{Определение
|definition=
Объединение матроидов <tex>M </tex> = <tex>\langle S,J \rangle</tex> = <tex>\cup _{k=1}^{n}</tex> <tex>M_i</tex>
}}
Для каждого <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_{M_i}(I_i)</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой - вершины из <tex>S_i \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S_i \setminus I_i</tex>, при условии, что <tex>I_i - y + x \in J_i</tex>.
}}
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, котороый будет суперпозицией ребер из этих графов.
{{Определение
|definition=
<tex>F_i</tex> = { <tex>x \in S_i \setminus I_i</tex> : <tex>I_i + x \in J_i </tex>}.
}}
{{Теорема
|statement=
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + x \in J_i \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
|proof=
}}
== Алгоритм ==
В жадном алгоритме трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.
Здесь мы обозначили текущее множество как <tex>I</tex>.
Тогда нужно найти такой элемент <tex>s \in S \setminus I</tex>, что <tex>I + s</tex> - снова независимо.
Все наши кандидаты находятся в <tex>S \setminus I</tex>. Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</tex>, которым путь закончился, можно будет добавить в <tex>I</tex>.
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути.
