Изменения
Нет описания правки
|proof=
}}
== Алгоритм ==
Нам известно, что объединение матроидов - матроид. При поиске базы матроида используется жадный алгоритм. В жадном алгоритме нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.
Здесь мы обозначили текущее множество как <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</tex> и поиске такого пути.
== Источник ==
[http://math.mit.edu/~goemans/18438/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
