Изменения
Нет описания правки
== Алгоритм ==
Пусть у нас есть множество <tex>I\in\mathcal{I}</tex>, где <tex>\mathcal{I} = \{ \bigcup\limits_{i=1}^{n} I_i \mid I_i \in \mathcal{I}_i\}</tex> — искомое множество, и разбиение <tex>I</tex> на <tex>\bigcup\limits_{i=1}^{n}I_i</tex>, такое, что <tex>I_i\in \mathcal{I}_i</tex>. Также нам дан какойТо есть, <tex>I</tex> состоит из каких-то подмножеств семейства множеств <tex>\mathcal{I}_i</tex> для <tex>i</tex> от <tex>1</tex> до <tex>n</tex>. Рассмотрим элемент <tex>s\not \in I</tex>. Нужно определить, правда ли, что <tex>I+s\in \mathcal{I}</tex>. Если научиться это делать, то тогда можно решить задачу [[Теорема_Радо-Эдмондса_(жадный_алгоритм)|жадным алгоритмом]], добавляя в текущее множество по одному элементу <tex>s</tex> на каждом шаге.
Определим объединение матроидов как <tex>M</tex> = <tex>\langle S,\mathcal{I} \rangle</tex> = <tex>\bigcup\limits_{i=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_i,\mathcal{I}_i \rangle</tex>.
Для каждого <tex>i</tex> от <tex>1</tex> до <tex>n</tex> возьмем <tex>M_i</tex> и построим [[Основные_определения_теории_графов#.D0.94.D0.B2.D1.83.D0.B4.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84|двудольный ориентированный граф]] <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in \mathcal{I}_i</tex>. Вершины графа — элементы из <tex>S</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> D_{M_i}(I_i)</tex>.
Для каждого <tex>i</tex> определим множество <tex>F_i</tex> как множество вершин <tex>S_i\setminus I_i</tex> таких, что множество <tex>I_i+x</tex> также независимое. Формально: <tex>F_i = \{ x \in S_i \setminus I_i \mid I_i + x \in \mathcal{I}_i \}</tex>. Определим <tex>F</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>F_i</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\mid \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 \mathcal{I}_i</tex>. Но <tex>x \notin F</tex> (по предположению в начале доказательства), значит <tex>I_i + x \notin
\mathcal{I}_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой, что <tex>I_i + x - y \in \mathcal{I}_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)</tex>.
:У нас есть <tex>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex>. Из определния определения функции ранга объединения матроидов имеем :
:<tex>r_M(I + s) \leqslant (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))</tex>
}}
Итак, теперь мы можем описать сам алгоритм. Изначально инициализируем <tex>I</tex> как пустое множествосемейство пустых множеств. На каждом шаге будем строить граф <tex>D</tex> из текущего <tex>I</tex> и <tex>S\setminus I</tex> и добавлять в <tex>I</tex> кандидата-вершину <tex>s</tex>, удовлетворяющую условию теоремы. При добавлении вершины нужно не забыть поменять местами вершины на пути <tex>F \leadsto s</tex>, так как ребра из <tex>I_i</tex> должны вести в <tex>S\setminus I_i</tex> (т.е. должен сохраняться инвариант). Когда вершины-кандидаты закончатся, по доказанной выше теореме получившееся множество <tex>I</tex> станет максимальным.
==Псевдокод==
*<tex>\mathtt{res}</tex> — возвращаемая база в объединении матроидов. <tex>res_1, res_2 \dots res_n</tex> содержат элементы, содержащиеся в полученной базе.
'''int[][]''' unionBase('''int[n]''' <tex>s[n]</tex>, '''int[n]''' <tex>\mathtt{base}[n]</tex>): '''int[n][]''' <tex>\mathtt{res}(n)</tex> <font color="darkgreen">// На каждом шаге алгоритма заполняем очередным элементом </font> '''bool''' <tex>\mathtt{reached}</tex> = ''false'' <font color="darkgreen">// Индикатор окончания работы цикла. Если true, то не нашли подходящую вершину</font>
'''while''' <tex>!\mathtt{reached}</tex>
<tex>\mathtt{reached}</tex> = ''true''
'''int''' <tex>f[n]</tex> <font color="darkgreen">// Соответствует <tex>F</tex> </font>
'''Graph''' <tex>d[n]</tex>
'''for''' <tex>i</tex> = 1 '''to''' <tex>n</tex>
<tex>d[i]</tex> = buildBipartiteGraph<tex>(\mathtt{res[i]} ,s[i] \setminus \mathtt{res}[i])</tex> <font color="darkgreen">// Строим двудольный граф d[i] </font>
<tex>f[i]</tex> = <tex> \{ x \in s[i] \setminus \mathtt{res[i]} : \mathtt{res}[i] + x \in base[i] \}</tex>
'''for''' <tex>\mathtt{elem} \in s\setminus \mathtt{base}</tex>
'''List<int>''' <tex>p</tex> = find_shortest_pathfindShortestPath(<tex>f</tex>, <tex>\mathtt{elem}</tex>)
'''if''' <tex>p\neq \varnothing </tex>
<tex>\mathtt{reached}</tex> = ''false'' <font color="darkgreen">// Нашли очередную вершину, цикл можно продолжить </font>
*[[Объединение_матроидов,_доказательство_того,_что_объединение_является_матроидом| Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Пересечение матроидов, определение, примеры]]
== Асимптотика ==
На каждом шаге алгоритма происходит построение графа D. Для того, чтобы его построить, нам нужно для <tex>i=1\dots n</tex> для каждого <tex>v</tex> из <tex>S</tex> и <tex>u</tex> из <tex>S\setminus I_i</tex>, где <tex>S</tex> — объединение матроидов, проверить условие <tex>(I_i \setminus u) \cup v \in \mathcal{I}_i</tex>. Построение графа занимает <tex>O(\sum\limits_{i=1}^{n}\vert (S_i\setminus I_i)\vert \vert I_i\vert </tex>) времени на каждой итерации. Нахождение кратчайшего пути для всех вершин занимает <tex>O(\vert E\vert )</tex> единиц времени, где <tex>E</tex> — множество ребер графа <tex>D</tex>, если использовать [[обход_в_ширину| поиск в ширину]], что в худшем случае будет равно <tex>O(\vert S \vert ^2)</tex>. Обновление <tex>res</tex> занимает <tex>O(n|I_{max}|)</tex> времени, что равно <tex>O(\vert S \vert)</tex>. В худшем случае требуется <tex>|S|</tex> итераций, и общая асимптотика будет <tex>O(|S|^3)</tex>.
== Источники информации ==
