Изменения

{{ОпределениеЗадача

Объединение матроидов Даны [[Определение матроида|матроиды]] <tex>M</tex> M_1 = <tex>\langle (S,J \rangle</tex> = <tex>\cup _mathcal{k=1I}^_1), \ldots ,(S, \mathcal{nI}_k)</tex> . Необходимо найти максимальное по мощности [[Определение матроида#def_matroid|независимое множество]] в объединении <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S,J_i M_1\rangleldots M_k</tex>.

Для каждого '''Объединение матроидов''' (англ. ''matroid union'') <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_M = (S,\mathcal{M_iI}(I_i)</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой - вершины из <tex>S_i = \setminus I_i</tex>. Построим ориентированные ребра из <tex>y bigcup\in I_ilimits_{k=1}^{n}</tex> в <tex>x \in S_i \setminus I_iM_i</tex>, при условии, что где <tex>I_i - y + x M_i = (S,\in J_imathcal{I}_i)</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</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>F = F_1 \cup \ldots \cup F_k</tex> и <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</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> — снова независимо.Все наши кандидаты находятся в <tex>S \setminus I</tex> . Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</tex>, которым путь закончился, можно будет добавить в <tex>I</tex>.То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути. '''Псевдокод''' <tex>J</tex> = <tex>\emptyset</tex> '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>n - 1</tex> построить [[Граф замен|граф замен]] <tex>D_{M_i}(I_i)</tex> '''if''' <tex>I_i + s \in \mathcal{I}_i</tex> <tex>J \leftarrow I_i + s</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 + x \cup s \in J_i \mathcal{I} \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам графа <tex>D</tex>.

<tex>\Leftarrow</tex>  Пусть существует путь из <tex>F</tex> в <tex>s</tex> и <tex>P</tex> - — самый короткий такой путь. Запишем его вершины как {<tex>s_0, s_1, ... \ldots s_p</tex>}. <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1...\ldots k</tex> определим множество вершин <tex>S_j =</tex> {<tex>s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)</tex>}, где <tex>i</tex> пробегает от <tex>0</tex> до <tex>p - 1</tex>.

<tex>\Rightarrow</tex>  Пусть нет пути из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>. Тогда пусть существует множество <tex>T</tex>, состоящее из вершин <tex>D</tex>, из которого мы можем достичь <tex>s</tex> : <tex>T = \{x, \exists x \leadsto s\}</tex> по допущению <tex>F\cap T = \varnothing</tex>. Утверждается, что для всех <tex>i : |I_i \cap T| = r_i(T)</tex>(что означает, что <tex>I_i \cap T</tex> - — максимальное подмножество <tex>T</tex>, независимое в <tex>M_i</tex>).  Предположим, что это не так. <tex>|I_i \cap T| = r_i(I_i\cap T) <= \leqslant r_i(T)</tex>, это возможно только если <tex>|I_i \cap T| < r_i(T)</tex>. Значит существует такой <tex>x \in T \cap (S \setminus I_i)</tex>, для которого <tex>(I_i \cap T) + x \in J_i</tex>. Но <tex>x \notin F</tex> (по предположению вначале доказательства), значит <tex>I_i + x \notin J_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой что <tex>I_i + x - y \in J_i</tex>. Получается, что <tex>(y, x)</tex> - — ребро в <tex>D_{M_i}(I_i)</tex> и оно содержит этот <tex>y \in T</tex>, что противоречит тому как был выбран <tex>y \in I_i \setminus T</tex>. Следовательно для всех <tex>i</tex> нам известно : <tex>|I_i \cap T| = r_i(T \cap S_i)</tex>.У нас есть <tex>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex>. Из определния функции [[Определение матроида#def_rank_of_matroid|ранга ]] объединения матроидов имеем :  <tex>r_M(I + s) <= \leqslant (|(I + s)\setminus T| + \sum _\limits_{k=1}^{n}r_i(T))</tex> <tex>r_M(I + s) <= \leqslant |(I + s)\setminus T| + \sum _\limits_{k=1}^{n} |I_i \cap T| = |I\setminus T| + \sum _\limits_{k=1}^{n} |I_i \cap T| = |I| < |I + s|</tex> и значит <tex>(I + s) \notin J</tex> - — противоречие.

== Алгоритм См. также==* [[Пересечение матроидов, определение, примеры]]* [[Алгоритм построения базы в пересечении матроидов]]

Нам известно, что объединение матроидов - матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.== Примечания ==Здесь мы обозначили текущее множество как <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>.То есть шаг жадного алгоритма заключается в создании нового <tex>D<references/tex> и поиске такого пути.

[http[Категория://math.mit.edu/~goemans/18438/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13Алгоритмы и структуры данных]][[Категория:Матроиды]][[Категория:Объединение матроидов]]