Изменения
Нет описания правки
Радо-Эдмондса
|statement=
На носителе матроида <tex>M = \langle X, I \rangle</tex> задана весовая функция <tex>\omega: X \to \mathbb R</tex>. Пусть <tex>A \in I</tex> - множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k</tex>. Возьмем <tex>x: A \cup x \in I</tex>, <tex>x \notin IA</tex>, <tex>\omega (x)</tex> - минимальна.
<br> Тогда <tex>A \cup x</tex> - множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
|proof=
