Изменения

Перейти к: навигация, поиск

Теорема Радо-Эдмондса (жадный алгоритм)

58 байт добавлено, 06:26, 17 мая 2011
Нет описания правки
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)</tex>
<br><tex>\omega (A \cup 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>. Теорема доказана.
}}
Анонимный участник

Навигация