ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Chislov                    2:5020/400     07 Oct 2002  18:36:14
 To : Alexander Shmidt
 Subject : Re: отрезать вершины
 -------------------------------------------------------------------------------- 
 

 AS> Есть задачка:
 AS> Граф, в котором надо удалить как можно меньшее
 AS> количество вершин так, чтобы
 AS> оставшиеся вершины никак не были связаны
 AS> (фактически получается, что никаких
 AS> ребер не должно остаться).
 
 Как я понял, граф у тебя неориентированный и вместе с удалением вершины 
 удаляются и все инцидентные ей рёбра. Мне пришёл в голову жадный 
 алгоритм: на каждом шаге находим вершину, степень которой максимальна и 
 удаляем её; заканчиваем работу, как только число рёбер станет равным 
 нулю. Имеют вершины вес или не имеют, для данного алгоритма, по-моему, 
 даже не важно, т.е. в любом случае получится то, что требуется.
 Теперь только осталось как-нибудь доказать, что он является 
 оптимальным...
 Если не секрет, а где возникла эта задача, т.е. к чему ты её применяешь?
 
 -- 
 Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.ru (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: отрезать вершины   Alexander Chislov   07 Oct 2002 18:36:14   отрезать вершины   Egor Tsygvintsev   09 Oct 2002 00:33:05   отрезать вершины   Alexander Shmidt   11 Oct 2002 14:10:54