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

From

Dmitry Onegov ()

To

Alexander Shmidt

Date

2002-10-07T18:42:55Z

Area

RU.ALGORITHMS

From: "Dmitry Onegov" <Dmitry.Onegov@psu.ru>

Добрый день.
--
"Alexander Shmidt" <Alexander.Shmidt@p74.f34.n464.z2.fidonet.org> wrote in
message news:1033747771@p74.f34.n464.z2.FIDOnet.ftn...

[skipped]

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

[skipped]

imho, должно работать что-то типа (может быть и не всегда, но контр-пример в
голову не приходит):

while (<в графе есть ребра>) {
  <берем одну из вершин с максимальным кол-вом ребер>;
  <удаляем её (вместе с ребрами)>;
};

> *Адвенсед-версия: вершины имеют вес; задача - удалить вершины так, чтобы
> суммарный вес оставшихся был максимален.

:-) можно решить "в лоб" (если время выполнения не критично). можно
попытаться привести к 1-й задачке (если это вообще возможно).
что первое пришло на ум: добавим в вершину помимо массы ещё одно свойство -
bm (суммарный вес соседей).
что-то типа:
   Веса вершин: Суммарные веса соседей:
      1---2            5---4
       \ /              \ /
        3                3

<подсчитываем bm вершин>;
while (<в графе есть вершины с bm>0 >) {
  <берем одну из вершин с максимальным bm>;
  <удаляем её>;
  <пересчитываем bm вершин>;
};

останется только одна вершина с массой 3.

p.s. к сожалению нет возможности проверить правильность работы алгоритмов.

--
С уважением, Онегов Дмитрий.



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