ru.algorithms

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

 Добрый день.
 --
 "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)
 
 

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

Тема:    Автор:    Дата:    Re: отрезать вершины   Dmitry Onegov   07 Oct 2002 18:42:55   Re: отрезать вершины   Dmitry Onegov   09 Oct 2002 08:20:13