ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anthone Tikhonov                     2:5020/400     09 Oct 2002  16:24:52
 To : Alexander Shmidt
 Subject : отрезать вершины
 -------------------------------------------------------------------------------- 
 

  AS> Граф, в котором надо удалить как можно меньшее количество вершин так,
  AS> чтобы оставшиеся вершины никак не были связаны (фактически получается,
  AS> что никаких ребер не должно остаться).
  AS> простейший пример:   о-о-о  ->  о   о
  AS> *Адвенсед-версия: вершины имеют вес; задача - удалить вершины так, чтобы
  AS> суммарный вес оставшихся был максимален.
 
 Как ее бы стал решать я - для любого ребра нужно удалить один из 2х 
   его концов. Hужно найти минимальное подмножество вершин, покрывающее
   все ребра. Классическая задача о наименьшем покрытии. Вот здесь 
   есть книга, в которой она описана. 
   http://www.caravan.ru/~alexch/books/christofides/ Кристофидес "Теория
 графов"
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

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

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