200
правок
Изменения
м
{{Определение
|definition=
Для каждого <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>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>, который будет суперпозицией ребер из этих графов.
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.
