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

From

Alexander Chislov ()

To

Alexander Shmidt

Date

2002-10-07T18:36:14Z

Area

RU.ALGORITHMS

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

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

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

-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.ru (2:5020/400)