Изменения

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

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

38 байт убрано, 03:00, 27 июня 2011
м
А мы-то и не догадались!
<br>Следовательно
<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>Теорема доказана.
}}

Навигация