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

From

Egor Tsygvintsev (2:452/77.57)

To

Alexander Chislov

Date

2002-10-09T00:33:05Z

Area

RU.ALGORITHMS

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

 Понедельник Октябрь 07 2002 18:36, Alexander Chislov писал Alexander Shmidt:

 AC> From: Alexander Chislov <arch-vile@rnd.runnet.ru>

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

 AC> Как я понял, граф у тебя неориентированный и вместе с удалением
 AC> вершины удаляются и все инцидентные ей рёбра. Мне пришёл в голову
 AC> жадный алгоритм: на каждом шаге находим вершину, степень которой
 AC> максимальна и удаляем её; заканчиваем работу, как только число рёбер
 AC> станет равным нулю. Имеют вершины вес или не имеют, для данного
 AC> алгоритма, по-моему, даже не важно, т.е. в любом случае получится то,
 AC> что требуется. Теперь только осталось как-нибудь доказать, что он
 AC> является оптимальным... Если не секрет, а где возникла эта задача,
 AC> т.е. к чему ты её применяешь?

проверь на таком тесте:
1 - 2 3 4
2 - 1 5 6
3 - 1 7 8
4 - 1 9 10

твой жадный снесет 4 вершины, хотя достаточно трех!!!

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