|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 04 Oct 2002 15:59:54
To : All
Subject : отрезать вершины
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый All! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Есть задачка:
Граф, в котором надо удалить как можно меньшее количество вершин так, чтобы
оставшиеся вершины никак не были связаны (фактически получается, что никаких
ребер не должно остаться).
простейший пример: о-о-о -> о о
^удалили одну вершину
оставшиеся не соединены
*Адвенсед-версия: вершины имеют вес; задача - удалить вершины так, чтобы
суммарный вес оставшихся был максимален.
Часто встречающаяся в разных вариациях задачка, однако не сводится к чему-либо
более удобоваримому. Похожа на задачу о назначениях, но явно не то...
Good bye, mister All _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Ешь ананасы, рябчиков жуй - сегодня ведь твой день рожденья, буржуй!
--- np: ОСП-Студия - Космонавт
* Origin: воспитаннику упавшей Винды... (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
