Материал из Викиконспекты
| Теорема (Радо-Эдмондса): |
На носителе матроида [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]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим [math]B \in I[/math] - множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math].
Очевидно, что [math]\exists y \in B\setminus A : A \cup y \in I[/math].
Тогда верны два неравенства:
[math]\omega (A \cup y) = \omega (A) + \omega (y) \ge \omega (B)[/math]
[math]\omega (B \setminus y) = \omega (B) - \omega (y) \ge \omega (A)[/math]
Сложим эти два неравенства и получим
[math]\omega (A) + \omega (B) \ge \omega (A) + \omega (B) [/math], что свидетельствует о том, что все знаки в неравенствах можно заменить на равенства.
Следовательно
[math]\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)[/math]
Таким образом получаем, что если объединить множество [math]A[/math] с [math]x[/math] - минимальным из таких, что [math]A \cup x \in I[/math], то получим множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math].
Теорема доказана. |
| [math]\triangleleft[/math] |
