ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      21 Jul 2003  14:00:00
 To : All
 Subject : расщепить граф
 -------------------------------------------------------------------------------- 
 

 ЫЫЫЫ OS/2        Hi, All !
 
 Пусть дан взвешенный неориентированный граф G=(V,E) и биективное отображение
 (инволюция) i на его вершинах такое, что
 1) i(i(v))=v для любой вершины v из V;
 2) i(v)<>v для любой вершины v из V;
 3) для любого ребра (u,v) из E, (i(u),i(v)) является ребром такого же веса.
 
 Hеобходимо расщепить этот граф на два подграфа G'=(V',E') и G''=(V'',E'') так
 что:
 1) V = V' U V''; причем i переводит множество V' в V'' и, наоборот, V'' в V'.
 Другими словами, из каждой пары вершин {v,i(v)} одна попадает в G', а другая в
 G''.
 2) суммарный вес ребер, соединяющих V' и V'', минимален.
 
 Интересует эффективный (можно приближенный) алгоритм для решения этой задачи.
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.8
  * Origin:  (2:5015/60)
 
 

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