200
правок
Изменения
Нет описания правки
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом графе замен <tex>D_{M_i}(I_i)</tex> ([[Алгоритм построения базы в объединении матроидов#th_1|следующая теорема]] отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как <tex>I</tex>.
Тогда нужно найти такой элемент <tex>s \in S \setminus I</tex>, что <tex>I + \cup s</tex> — снова независимо.
Все наши кандидаты находятся в <tex>S \setminus I</tex> . Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</tex>, которым путь закончился, можно будет добавить в <tex>I</tex>.
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути.
