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

From

Alexander Shmidt (2:464/34.74)

To

Anthone Tikhonov

Date

2002-10-11T14:16:53Z

Area

RU.ALGORITHMS

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

 Эй, уважаемые Anthone Tikhonov и Alexander Shmidt! Что за "отрезать вершины", а где же яйца?!

 AS>> Граф, в котором надо удалить как можно меньшее количество вершин
 AS>> так, чтобы оставшиеся вершины никак не были связаны (фактически
 AS>> получается, что никаких ребер не должно остаться). простейший
 AS>> пример:   о-о-о  ->  о   о *Адвенсед-версия: вершины имеют вес;
 AS>> задача - удалить вершины так, чтобы суммарный вес оставшихся был
 AS>> максимален.

 AT> Как ее бы стал решать я - для любого ребра нужно удалить один из 2х
 AT>   его концов. Нужно найти минимальное подмножество вершин, покрывающее
 AT>   все ребра. Классическая задача о наименьшем покрытии. Вот здесь
 AT>   есть книга, в которой она описана.

Огромное спасибо. И ведь знал же, что все задачки приводятся к известным типам, а тут попалась парочка вот таких, и че-то крутил я их, и не получалось. :)

А, кстати, вот насчет второй постановки забыл: задача о наименьшем покрытии может учитывать взвешенность?

Good bye, mister Tikhonov                       _
                                               /_|  _  _    _/
                                     Smith,   (  | (/ (- /) /   Smith...
                                                  _/
... Пiнгвiн - то не win. Щоб стояв у кожнiй хатi!
--- паузед: Ундервуд - Гагарин
 * Origin: Полк красноармейцев не может идти вечно... (2:464/34.74)