200
правок
Изменения
м
Нет описания правки
<tex>F_i = \{ x \in S \setminus I_i : I_i + x \in J_i \}</tex>. <tex>F</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>F_i</tex>
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. Иначе говоря, на каждом шаге мы выбираем элемент не из текущего множества, который оставит текущее множество независимым ([[Алгоритм построения базы в объединении матроидов#id=th_1|следующая теорема]] отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как <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>.
