Теорема Радо-Эдмондса (жадный алгоритм) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (А мы-то и не догадались!)
Строка 15: Строка 15:
 
<br>Следовательно
 
<br>Следовательно
 
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)</tex>
 
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)</tex>
<br>Таким образом получаем, что если объединить  множество <tex>A</tex> с <tex>x</tex> - минимальным из таких, что <tex>A \cup x \in I</tex>, то получим множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
+
<br>Таким образом получаем, что если объединить  множество <tex>A</tex> с <tex>x</tex> - минимальным из таких, что <tex>A \cup x \in I</tex>, то получим множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
<br>Теорема доказана.
 
 
}}
 
}}

Версия 03:00, 27 июня 2011

Теорема (Радо-Эдмондса):
На носителе матроида [math]M = \langle X, I \rangle[/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 A[/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) \Rightarrow \omega (A) \ge \omega (B) - \omega (y)[/math]
[math]\omega (B \setminus y) = \omega (B) - \omega (y) \ge \omega (A)[/math]
Заметим, что величина [math]\omega (A)[/math] с двух сторон ограничивает величину [math]\omega (B) - \omega (y)[/math]. Значит, эти величины равны:
[math]\omega (A) = \omega (B) - \omega (y) \Rightarrow \omega (A) + \omega (y) = \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]