200
правок
Изменения
Нет описания правки
Пусть <tex>I_i \in \mathcal{I}_i</tex>, для <tex>i = 1\ldots k</tex> с <tex>I_i \cap I_j = \emptyset</tex>, если <tex>i \neq j</tex>. Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим [[Основные определения теории графов#defBiparateGraph|двудольный ориентированный граф]] <tex>D_{M_i}(I_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 \mathcal{I}_i</tex>.
Объединим все <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 + xF = F_1 \cup \ldots \cup F_k</tex> независимое множество в и <tex>M_i</tex> . Или формально: <tex>F_i \mathcal{I} = \mathcal{ s I}_1 \in S cup \setminus I_i : I_i + s ldots \in cup \mathcal{I}_i \}_k</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>.
