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

From

Alexander Shmidt (2:464/34.74)

To

Egor Tsygvintsev

Date

2002-10-11T14:19:07Z

Area

RU.ALGORITHMS

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

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

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

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


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

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

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

"А теперь докажи, что он - равнобедренный" :)

Good bye, mister Tsygvintsev                    _
                                               /_|  _  _    _/
                                     Smith,   (  | (/ (- /) /   Smith...
                                                  _/
... Отчего, отчего, отчего Winamp поет? Оттого, что кто-то любит программиста!
--- стоппед: Kitaro - Silk Road
 * Origin: Телепузик спать ложится - программист за комп садится. (2:464/34.74)