Изменения
Нет описания правки
<tex>F_i</tex> = { <tex>x \in S \setminus I_i</tex> : <tex>I_i + x \in J_i </tex>}. <tex>F</tex> = <tex>\cup _{k=1}^{n}</tex> <tex>F_i</tex>
}}
== Алгоритм ==
Нам известно, что объединение матроидов - матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.
Здесь мы обозначили текущее множество как <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> и поиске такого пути.
{{Теорема
и значит <tex>(I + s) \notin J</tex> - противоречие.
}}
