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

From

Egor Tsygvintsev (2:452/77.57)

To

Alexander Shmidt

Date

2002-10-06T22:13:17Z

Area

RU.ALGORITHMS

Добрый день, Alexander

 Пятница Октябрь 04 2002 15:59, Alexander Shmidt писал All:

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

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

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


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

на тему адванседа - не знаю, надо думать, а основной делается так:

  e:true;
  while e do
    begin
      e:=false;
      ищем вершину, из которого выходит только одно ребро и удаляем ту вершину, к которой это ребро ведет; если нашли то e:=true;
    end;


                    Всего доброго,
                    Egor Tsygvintsev.
--- ... Линия отреза ...
 * Origin:  Крепче за шоферку держись, баран!  (2:452/77.57)