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

From

Alexander Shmidt (2:464/34.74)

To

Alexander Chislov

Date

2002-10-11T14:10:54Z

Area

RU.ALGORITHMS

      ><  ┼  ><  ┼  ><   Хау, бледнолицый  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)