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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оформление и вики-разметка не для нас >_<)
Строка 3: Строка 3:
 
Радо-Эдмондса
 
Радо-Эдмондса
 
|statement=
 
|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 A</tex>, <tex>\omega (x)</tex> - минимальна.
+
На носителе матроида <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 A</tex>, <tex>\omega (x)</tex> {{---}} минимальна.
<br> Тогда <tex>A \cup x</tex> - множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
+
<br> Тогда <tex>A \cup x</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
 
|proof=
 
|proof=
Рассмотрим <tex>B \in I</tex> - множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.  
+
Рассмотрим <tex>B \in I</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.  
  
 
Из определения матроида: <tex>\exists y \in B\setminus A : A \cup y \in I</tex>.
 
Из определения матроида: <tex>\exists y \in B\setminus A : A \cup y \in I</tex>.

Версия 05:45, 29 июня 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]