Изменения

Даны [[Определение матроида|матроиды]] <tex>M_1 = (S, \mathcal{I}_1), \ldots ,(S, \mathcal{I}_k)</tex>. Пусть <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>. Необходимо найти максимальное по мощности [[Определение матроида#def_matroid|независимое множество]] в объединении <tex>M_1\dots ldots M_k</tex>.

'''Объединение матроидов''' (англ. ''matroid union'') <tex>M = \langle (S,\mathcal{I} \rangle ) = \bigcup\limits_{k=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i = \langle (S,\mathcal{I}_i \rangle)</tex>

Эта задача [[Объединение матроидов, проверка множества на независимость#Проверка множества на независимость| сводится к пересечению матроидов]], однако есть другой способ её решить. Пусть <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 \in \mathcal{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_i s \setminus 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 + xF = F_1 \cup \ldots \cup F_k</tex> независимое множество в и <tex>M_i\mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex> . Или формально:

<tex>F_i = \{ x \in S \setminus I_i : I_i + x \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 + \cup s</tex> — снова независимо.

=== '''Псевдокод ==='''

'''if''' <tex>I_i + x s \in \mathcal{I}_i</tex> <tex>J \leftarrow I_i + xs</tex> '''Время работы''' Это подразумевает, что максимальное независимое множество в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex> мы можем найти за полиномиальное время (жадно наращивать независимое множество в <tex>M = M_1 \cup \ldots \cup M_k</tex>). Cunningham<ref>Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, стр.732</ref> разработал алгоритм, которым за <tex>O((n^{(3/2)} + k)mQ + n^{(1/2)}km)</tex> можно найти максимальное независимое множество в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex>, где <tex>n</tex> максимальный размер множества в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex>, <tex>m</tex> размер подмножества и <tex>Q</tex> время, необходимое, чтобы определить принадлежит ли множество <tex> \mathcal{I}_j</tex> для каждого <tex>j</tex>. Более детальное объяснение алгоритма (но не время работы) можно найти у C. Greene и T.L. Magnanti<ref>C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics, p.530-539</ref>.

Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + \cup s \in J \mathcal{I} \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам графа <tex>D</tex>.