|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 11 Oct 2002 14:19:07
To : Egor Tsygvintsev
Subject : отрезать вершины
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
