200
правок
Изменения
Нет описания правки
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов. Пусть для каждого <tex>i:</tex> <tex>F_i</tex> {{---}} множество элементов <tex>s \notin I_i</tex> с <tex>I_i \cup {s} \in \mathcal{I}_i</tex>. Определим <tex>I = I_1 \cup \ldots \cup I_k</tex> которые могут быть добавлены в <tex>I_i</tex> таким образом, что <tex>I_i + x</tex> независимое множество в <tex>M_i</tex> . Или формально:
<tex>F_i = \{ x s \in S \setminus I_i : I_i + x s \in \mathcal{I}_i \}</tex> . <tex>F = \bigcup\limits_{k=1}^{n}</tex> <tex>F_i</tex>
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом [[Граф замен|графе замен]] <tex>D_{M_i}(I_i)</tex> ([[Алгоритм построения базы в объединении матроидов#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>.
