отрезать вершины

From

Alexander Shmidt (2:464/34.74)

To

All

Date

2002-10-04T15:59:54Z

Area

RU.ALGORITHMS

      ><  ┼  ><  ┼  ><   Хау, бледнолицый  All!   ><  ┼  ><  ┼  ><
    (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)

Есть задачка:
Граф, в котором надо удалить как можно меньшее количество вершин так, чтобы оставшиеся вершины никак не были связаны (фактически получается, что никаких ребер не должно остаться).

простейший пример:   о-о-о  ->  о   о
                                  ^удалили одну вершину
                                   оставшиеся не соединены


*Адвенсед-версия: вершины имеют вес; задача - удалить вершины так, чтобы суммарный вес оставшихся был максимален.


Часто встречающаяся в разных вариациях задачка, однако не сводится к чему-либо более удобоваримому. Похожа на задачу о назначениях, но явно не то...

Good bye, mister All                            _
                                               /_|  _  _    _/
                                     Smith,   (  | (/ (- /) /   Smith...
                                                  _/
... Ешь ананасы, рябчиков жуй - сегодня ведь твой день рожденья, буржуй!
--- np: ОСП-Студия - Космонавт
 * Origin: воспитаннику упавшей Винды... (2:464/34.74)