Изменения
Нет описания правки
<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
}}
Итак, теперь мы можем описать сам алгоритм. Изначально инициализируем <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>станет максимальным.
==Псевдокод==
'''int[][]''' unionBase('''int''' <tex>s[n]</tex>, '''int''' <tex>\mathtt{base}[n]</tex>):
'''int[][]''' <tex>\mathtt{res}(n)</tex> <font color="darkgreen">// На каждом шаге алгоритма заполняем очередным элементом </font>
'''bool''' <tex>\mathtt{reached}</tex> = '''false'''
'''while''' <tex>!\mathtt{reached}</tex>
<tex>\mathtt{reached}</tex> = '''true'''
'''int''' <tex>f[n]</tex>
'''Graph''' <tex>d[n]</tex>
'''List''' <tex>p</tex> = find_shortest_path(<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>
