ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Egor Tsygvintsev                     2:452/77.57    09 Oct 2002  00:33:05
 To : Alexander Chislov
 Subject : отрезать вершины
 -------------------------------------------------------------------------------- 
 

 
  Понедельник Октябрь 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)
 
 

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

Тема:    Автор:    Дата:    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