Изменения
Новая страница: «{{Теорема |about= Радо-Эдмондса |statement= Пусть на носителе матроида <tex>M = <X, I></tex> задана весовая ф…»
{{Теорема
|about=
Радо-Эдмондса
|statement=
Пусть на носителе матроида <tex>M = <X, I></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=
}}
|about=
Радо-Эдмондса
|statement=
Пусть на носителе матроида <tex>M = <X, I></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=
}}
