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

From

Anthone Tikhonov ()

To

Alexander Shmidt

Date

2002-10-09T16:24:52Z

Area

RU.ALGORITHMS

From: "Anthone Tikhonov" <ia26@vtb.ru>

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

Как ее бы стал решать я - для любого ребра нужно удалить один из 2х 
  его концов. Нужно найти минимальное подмножество вершин, покрывающее
  все ребра. Классическая задача о наименьшем покрытии. Вот здесь 
  есть книга, в которой она описана. 
  http://www.caravan.ru/~alexch/books/christofides/ Кристофидес "Теория
графов"

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)