Изменения

Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент <tex>ArgOf(X[i])</tex>. Заметим, что если его можно добавить с сохранением независимости множества <tex>B</tex>, то это элемент минимального веса не из <tex>B</tex>, который можно добавить (при условии сохранения независимости <tex>B</tex> при добавлении). В самом деле, пусть <tex>ArgOf(X[j])</tex> — элемент минимального веса, который можно добавить к <tex>B</tex> с сохранением его независимости, тогда <tex>j<i</tex>. Но тогда он уже был бы добавлен на <tex>j</tex>-ом шаге алгоритма.

Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.

}}