|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Egor Tsygvintsev 2:452/77.57 06 Oct 2002 22:13:17
To : Alexander Shmidt
Subject : отрезать вершины
--------------------------------------------------------------------------------
Пятница Октябрь 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
отрезать вершины 
