Изменения

Пусть на носителе матроида <tex>M = <\langle X, I>\rangle</tex> задана весовая функция <tex>\omega: X \to \mathbb R</tex>. Для любого <tex>A \subset X</tex> выполнено: <tex>\omega(A) = \sum\limits _{x \in A} \omega(x)</tex>. Тогда база минимального веса матроида <tex>M</tex> ищется жадно.

'''whilefor''' <tex>i \leftarrow 0</tex> '''to''' (<tex>\exists x mid X \notin B: mid</tex> '''do''' '''if''' <tex>B \cup x ArgOf(X[i]) \in I</tex>): <tex>y B \leftarrow B \cup ArgOf(X[i])</tex>Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент <tex>ArgOf(\min\limits _{x \notin X[i])</tex>. Заметим, что если его можно добавить с сохранением независимости множества <tex>B: </tex>, то это элемент минимального веса не из <tex>B \cup x \in I} \omega</tex>, который можно добавить (xпри условии сохранения независимости <tex>B</tex> при добавлении). В самом деле, пусть <tex>ArgOf(X[j])</tex> — элемент минимального веса, который можно добавить к <tex>B \leftarrow B \cup y</tex>с сохранением его независимости, тогда <tex>j<i</tex>. Но тогда он уже был бы добавлен на <tex>j</tex>-ом шаге алгоритма.Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.