Жадный алгоритм поиска базы минимального веса

Теорема (жадный алгоритм поиска базы минимального веса):

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

Доказательство:

[math]\triangleright[/math]

Псевдокод алгоритма: [math]sort(X)[/math] // сортируем элементы по возрастанию веса [math]B \leftarrow \emptyset[/math] for [math]i \leftarrow 0[/math] to [math]|X|-1[/math] do if [math]B \cup X[i] \in I[/math] [math]B \leftarrow B \cup X[i][/math] Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент [math]X[i][/math]. Заметим, что если его можно добавить с сохранением независимости множества [math]B[/math], то это элемент минимального веса не из [math]B[/math], который можно добавить (при условии сохранения независимости [math]B[/math] при добавлении). В самом деле, пусть [math]X[j][/math] — элемент минимального веса не из [math]B[/math], который можно добавить к [math]B[/math] с сохранением его независимости, тогда [math]j\lt i[/math]. Но тогда он уже был бы добавлен на [math]j[/math]-ом шаге алгоритма. Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По теореме Радо-Эдмондса множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из [math]X[/math] так, чтобы после каждого добавления множество оставалось независимым. Алгоритм работает за [math]O(|X| \log(|X|))[/math]. На сортировку элементов из [math]X[/math] по возрастанию весов уходит [math]O(|X| \log(|X|))[/math] и [math]O(\mid X \mid)[/math] шагов цикла, каждый из которых работает [math]O(1)[/math] времени (если считать, что проверка множества на независимость происходит за [math]O(1)[/math]).

[math]\triangleleft[/math]