Изменения

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

Объединение матроидов Даны матроиды <tex>M</tex> M_1 = \langle S_1, \mathcal{I}_1 \rangle \dots M_n = <tex>\langle SS_n,J \mathcal{I}_n \rangle</tex> = . Необходимо найти максимальное по мощности независимое множество в [[Объединение_матроидов,_проверка_множества_на_независимость|объединении]] <tex>\bigcup\limits_{i=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_i,J_i \rangle</tex>.

{{Определение|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_I\in\mathcal{M_iI}</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>DI_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> на каждом шаге.

{{Определение|definition=Определим объединение матроидов как <tex>F_i = \{ x \in S_i \setminus I_i : I_i + x \in J_i \}M</tex>. = <tex>F\langle S,\mathcal{I} \rangle</tex> = <tex>\bigcup\limits_{ki=1}^{n}</tex> <tex>F_iM_i</tex>}, где <tex>M_i</tex> = <tex>\langle S_i,\mathcal{I}_i \rangle</tex>.

Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.Здесь мы обозначим текущее множество как Объединим все <tex>ID_{M_i}(I_i)</tex>.Тогда нужно найти такой элемент в один граф <tex>s \in S \setminus ID</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>DD_{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>.

union('''int''' <tex>S[n]</tex>, '''int''' <tex>J[n]</tex>): '''int''' <tex>I[n]</tex> '''bool''' reached = '''false''' '''while''' '''not''' reached: reached = '''true''' '''int''' Определим <tex>F[n]</tex> '''Graph''' <tex>D[n]</tex> '''for''' i = 1 '''to''' n <tex>D[i]</tex> = build_bipartite_graph<tex>(I[i] ,S[i] \setminus I[i])</tex> <font color="darkgreen">// Строим двудольный граф D[i] </font> <tex>F[i]</tex> =<tex> bigcup\limits_{ x \in S \setminus I[i] : I[i] + x \in J[i] \}</tex> '''for''' <tex>s \in S</teX>: '''int[]''' <tex>P</tex> k= find_shortest_path(<tex>F</tex>, <tex>s</tex>) '''if''' find_shortest_path(<tex>F</tex>, <tex>s</tex>) <tex>\neq \varnothing </tex>: reached = '''false''' '''int''' <tex>pos</tex> = get_f(<tex>P[1]}^{n}</tex>) <font color="darkgreen">// Находим <tex>F_i</tex>, которому принадлежит стартовая вершина в пути</font> '''int''' <tex>V[n]</tex> '''for''' j = 1 '''to''' <tex>P.len - 1</tex>: '''int''' <tex>vertex\_num</tex> = get_D_by_edge<tex>(P[j],P[j+1])</tex> <font color="darkgreen">// Находим номер множества, соответствующего ребру <tex>(p[j],p[j+1])</tex></font> <tex>V[vertex\_num].add(j)</tex> <tex>V[vertex\_num].add(j + 1)</tex> '''for''' j = 1 '''to''' n: <tex> I[j]</tex> = <tex> I[j] \oplus V[j]</tex> <tex>I[pos]</tex> = <tex>I[pos] \cup P[1] </tex> '''break'''

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

:Пусть существует путь из <tex>F</tex> в <tex>s</tex> и <tex>P</tex> — самый короткий такой путь. Запишем его вершины как <tex>\{s_0, s_1, \dots s_p\}</tex>. Вершина <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1...\dots n</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>I'_1 = (I_1 \oplus S_1) \cup \{s_0\}</tex>, для всех <tex>j > 1</tex> положим опеределим <tex>I'_j = (I_j \oplus S_j)</tex>. Ясно, что <tex>\cup _j I'_j = I + s</tex>(. Для того, чтобы показать независимость <tex>I + s</tex> в объединении матроидов нужно показать, что <tex>I'_j \in J_j\mathcal{I}_j</tex> для всех <tex>j</tex>. Заметим, что так как мы выбирали путь <tex>P</tex> таким, что он будет наименьшим, для каждого <tex>j > 1</tex> существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать <tex>I'_j = I_j \oplus S_j</tex>. Так как паросочетание единственно, <tex>I'_j \in J_j\mathcal{I}_j</tex>. Аналогично <tex>s_0 \in F_1</tex>, значит <tex>I'_1 \in J_1\mathcal{I}_1</tex>(см. [[Лемма_о_единственном_паросочетании_в_графе_замен#.D0.9B.D0.B5.D0.BC.D0.BC.D0.B0_.D0.BE_.D0.B5.D0.B4.D0.B8.D0.BD.D1.81.D1.82.D0.B2.D0.B5.D0.BD.D0.BD.D0.BE.D0.BC_.D0.BF.D0.B0.D1.80.D0.BE.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D0.B8_.D0.B2_.D0.B3.D1.80.D0.B0.D1.84.D0.B5_.D0.B7.D0.B0.D0.BC.D0.B5.D0.BD|лемму]]). Следовательно , <tex>I + s</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) \le 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\mathcal{I}_i</tex>. Но <tex>x \notin F</tex> (по предположению вначале в начале доказательства), значит <tex>I_i + x \notin J_i\mathcal{I}_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой , что <tex>I_i + x - y \in J_i\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) \le leqslant (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))</tex>

:<tex>r_M(I + s) \le 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\mathcal{I}</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>s</tex> — принимаемое множество носитилей матроидов*<tex>\mathtt{base}</tex> — принимаемое множество баз матроидов*<tex>\mathtt{res}</tex> — возвращаемая база в объединении матроидов. <tex>res_1, res_2 \dots res_n</tex> содержат элементы, содержащиеся в полученной базе.  '''int[][]''' unionBase('''int[n]''' <tex>s</tex>, '''int[n]''' <tex>\mathtt{base}</tex>): '''int[n][]''' <tex>\mathtt{res}</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> = findShortestPath(<tex>f</tex>, <tex>\mathtt{elem}</tex>) '''if''' <tex>p\neq \varnothing </tex> <tex>\mathtt{reached}</tex> = ''false'' <font color="darkgreen">// Нашли очередную вершину, цикл можно продолжить </font> '''int''' <tex>\mathtt{pos}</tex> = getF(<tex>p[1]</tex>) <font color="darkgreen">// Находим <tex>f_i</tex>, которому принадлежит стартовая вершина в пути</font> '''int''' <tex>v[n]</tex> <font color="darkgreen">// i-й элемент <tex>v</tex> хранит множество вершин, соответствующее i-му входному матроиду </font> '''for''' <tex> j</tex> = 1 '''to''' <tex>p.len - 1</tex> '''int''' <tex>\mathtt{vertex}</tex> = getDbyEdge<tex>(p[j],p[j+1])</tex> <font color="darkgreen">// Находим номер графа, соответствующего ребру <tex>(p[j],p[j+1])</tex></font> <tex>v[\mathtt{vertex}].add(j)</tex> <font color="darkgreen">// Добавляем в соответствующее вершинам множество концы ребра</font> <tex>v[\mathtt{vertex}].add(j + 1)</tex> '''for''' <tex>j</tex> = 1 '''to''' <tex>n</tex> <tex> \mathtt{res}[j]</tex> = <tex> \mathtt{res}[j] \oplus v[j]</tex> <font color="darkgreen"> // Удаляем и добавляем ребра на пути к конечной вершине </font> <tex>\mathtt{res}[\mathtt{pos}]</tex> = <tex>res[\mathtt{pos}] \cup p[1] </tex> '''break''' '''return''' <tex>\mathtt{res}</tex> == См. также ==*[[Объединение_матроидов,_проверка_множества_на_независимость| Объединение матроидов, проверка множества на независимость]]*[[Объединение_матроидов,_доказательство_того,_что_объединение_является_матроидом| Объединение матроидов, доказательство того, что объединение является матроидом]]* [[Пересечение матроидов, определение, примеры]] == Асимптотика ==На каждом шаге алгоритма происходит построение графа 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>. == Источники информации ==

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