81
правка
Изменения
Нет описания правки
{{Теорема
|statement=
Для любого какого-нибудь <tex>s \in S \setminus I</tex> выполняется: <tex>I + s \in J \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
|proof=
<tex>\Leftarrow</tex>
'''int'''[][] union('''int''' <tex>S[n]</tex>, '''int''' <tex>J[n]</tex>):
'''int'''[] <tex>I[n]</tex> <font color="darkgreen">//На каждом шаге алгоритма заполняем очередным элементом </font>
'''bool''' <tex>reached </tex> = '''false'''
'''while''' '''not''' reached:
<tex>reached </tex> = '''true'''
'''int''' <tex>F[n]</tex>
'''Graph''' <tex>D[n]</tex>
'''int[]''' <tex>p</tex> = find_shortest_path(<tex>F</tex>, <tex>s</tex>)
'''if''' find_shortest_path(<tex>F</tex>, <tex>s</tex>) <tex>\neq \varnothing </tex>:
<tex>reached </tex> = '''false'''
'''int''' <tex>pos</tex> = get_f(<tex>p[1]</tex>) <font color="darkgreen">// Находим <tex>F_i</tex>, которому принадлежит стартовая вершина в пути</font>
'''int''' <tex>v[n]</tex>
'''for''' <tex> j</tex> = 1 '''to''' <tex>Pp.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>
'''break'''
'''return''' <tex>I</tex>
== См. также ==
*[[Объединение_матроидов,_проверка_множества_на_независимость| Объединение матроидов, проверка множества на независимость]]
*[[Объединение_матроидов,_доказательство_того,_что_объединение_является_матроидом| Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Пересечение матроидов, определение, примеры]]
== Источники информации ==
[http://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
[http[Категория://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13Алгоритмы и структуры данных]][[Категория:Матроиды]][[Категория:Объединение матроидов]]
