Теорема Радо-Эдмондса (жадный алгоритм)

Теорема (Радо-Эдмондса):

Пусть на носителе матроида [math]M = \lt X, I\gt [/math] задана весовая функция [math]\omega: X \to \mathbb R[/math]. Пусть [math]A \in I[/math] - множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k[/math]. Возьмем [math]x: A \cup x \in I[/math], [math]x \notin I[/math], [math]\omega (x)[/math] - минимальна. Тогда [math]A \cup x[/math] - множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math].