200
правок
Изменения
Нет описания правки
|definition=
'''Объединение матроидов''' <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S,J_i \rangle</tex>
}}
Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in J_i</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in J_i</tex>.
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов.Пусть для каждого <tex>i:</tex> <tex>F_i</tex> - множество вершин из <tex>S_i \setminus I_i</tex>, которые могут быть добавлены в <tex>I_i</tex> таким образом, что <tex>I_i + x</tex> независимое множество в <tex>M_i</tex>. Или формально: <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>.
{{Теорема
|id=th_1
|statement=
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + s \in J \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
