Изменения
Нет описания правки
Радо-Эдмондса
|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 I</tex>, <tex>\omega (x)</tex> - минимальна.
<br> Тогда <tex>A \cup x</tex> - множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
|proof=
<br>Очевидно, что <tex>\exists y \in B\setminus A : A \cup y \in I</tex>.
<br>Тогда верны два неравенства:
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) \ge \omega (B) \Rightarrow \omega (A) \ge \omega (B) - \omega (y)</tex>
<br><tex>\omega (B \setminus y) = \omega (B) - \omega (y) \ge \omega (A)</tex>
<br>Заметим, что величина <tex>\omega (A)</tex> с двух сторон ограничивает величину <tex>\omega (B) - \omega (y)</tex>. Значит, эти величины равны:
<br><tex>\omega (A) = \omega (B) - \omega (y) \Rightarrow \omega (A) + \omega (y) = \omega (B)</tex>
<br>Следовательно
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)</tex>
