ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    11 Oct 2002  14:10:54
 To : Alexander Chislov
 Subject : отрезать вершины
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  Alexander!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
  Эй, уважаемые Alexander Chislov и Alexander Shmidt! Что за "Re: отрезать
 вершины", а где же яйца?!
 
  AS>> Есть задачка:
  AS>> Граф, в котором надо удалить как можно меньшее
  AS>> количество вершин так, чтобы
  AS>> оставшиеся вершины никак не были связаны
  AS>> (фактически получается, что никаких
  AS>> ребер не должно остаться).
 
  AC> Как я понял, граф у тебя неориентированный и вместе с удалением
  AC> вершины удаляются и все инцидентные ей рёбра.
 
 Именно так.
 
  AC> Мне пришёл в голову
  AC> жадный алгоритм: на каждом шаге находим вершину, степень которой
  AC> максимальна и удаляем её; заканчиваем работу, как только число рёбер
  AC> станет равным нулю. Имеют вершины вес или не имеют, для данного
  AC> алгоритма, по-моему, даже не важно, т.е. в любом случае получится то,
  AC> что требуется.
  AC> Теперь только осталось как-нибудь доказать, что он
  AC> является оптимальным...
 
 Практика показывает, что проще всего показать, что он неоптимален :)
 
 И потом - что делать, если несколько вершин имеют равную степень?
 
  AC> Если не секрет, а где возникла эта задача, т.е. к чему ты её
  AC> применяешь?
 
 Просматривал задачки с олимпиад, этот тип оказался единственным, который я ни к 
 чему не смог привести.
 
 Good bye, mister Chislov                        _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                   _/
 ... Отчего, отчего, отчего Winamp поет? Оттого, что кто-то любит программиста!
 --- стоппед: Kitaro - Silk Road
  * Origin: FidoNet - друг молодежи: по Fido не видно рожи.
  (2:464/34.74)
 
 

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

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