ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    11 Oct 2002  14:16:53
 To : Anthone Tikhonov
 Subject : отрезать вершины
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  Anthone!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
  Эй, уважаемые Anthone Tikhonov и Alexander Shmidt! Что за "отрезать вершины", а
 где же яйца?!
 
  AS>> Граф, в котором надо удалить как можно меньшее количество вершин
  AS>> так, чтобы оставшиеся вершины никак не были связаны (фактически
  AS>> получается, что никаких ребер не должно остаться). простейший
  AS>> пример:   о-о-о  ->  о   о *Адвенсед-версия: вершины имеют вес;
  AS>> задача - удалить вершины так, чтобы суммарный вес оставшихся был
  AS>> максимален.
 
  AT> Как ее бы стал решать я - для любого ребра нужно удалить один из 2х
  AT>   его концов. Hужно найти минимальное подмножество вершин, покрывающее
  AT>   все ребра. Классическая задача о наименьшем покрытии. Вот здесь
  AT>   есть книга, в которой она описана.
 
 Огромное спасибо. И ведь знал же, что все задачки приводятся к известным типам, 
 а тут попалась парочка вот таких, и че-то крутил я их, и не получалось. :)
 
 А, кстати, вот насчет второй постановки забыл: задача о наименьшем покрытии
 может учитывать взвешенность?
 
 Good bye, mister Tikhonov                       _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                   _/
 ... Пiнгвiн - то не win. Щоб стояв у кожнiй хатi!
 --- паузед: Ундервуд - Гагарин
  * Origin: Полк красноармейцев не может идти вечно... (2:464/34.74)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    отрезать вершины   Anthone Tikhonov   09 Oct 2002 16:24:52   отрезать вершины   Alexander Shmidt   11 Oct 2002 14:16:53