ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vitaly Osipov                        2:5080/180.38  28 Nov 2001  19:20:47
 To : Stanislav Shwartsman
 Subject : Клика в графе?
 -------------------------------------------------------------------------------- 
 

 
 *27 ноября 2001 года* /*(а было тогда 21:12)*/
 _/Stanislav Shwartsman/_ /*в своем письме к*/ _/Vitaly Osipov/_ /*писал:*/
 
  VO>> Задан обыкновенный граф, найти в нем клику - максимальный полный
  VO>> подграф. Мне кроме перебора ничего в голову не идет :( Может есть
  VO>> что похитрее?
 
  SS>  Это одна из классических NP-полных задач. То есть решения за
  SS>  полиномиальное время еще никто в мире не нашел и все известные
  SS>  решения этой задачи работают за время const*<полный перебор>.
 
 Спасибо, тогда может кто подскажет как лучшим образом организовать перебор?
 Я хотел поступить так:
 Пусть граф задан матрицей смежности nxn
 
 1. Во время считывания графа посчитать степень каждой вершины, и тем самым
 сделать предположение о возможном количестве вершин в клике.
 
 2. Перебор сочетаний n вершин по k , начав его с предполагаемого в п.1
 возможного количества вершин, затем уменьшаем k. Т.е. если мы получили в п. 1,
 что клика может состоять не более чем из k  вершин, то рассматриваем все
 подграфы из k вершин. Для каждого такого подграфа получим матрицу смежности kxk.
 Проверяя полученную матрицу на единичность, выясним является ли полученный
 подграф кликой. Перебрав все подграфы с k вершинами, и не найдя клики, начинаем 
 перебор подграфов с k-1 вершинами и так далее...
 
 Сложность алгоритма
 
 k
 __
 \   i   i^2
 /  C   _____
 __  n    2
 i=1
 
       i
 где  С  - кол-во подграфов с i вершинами
       n
 
 i^2
 ___  проверка подграфа на "кликовость" :) (матрицы ixi на единичность)
  2
 
 P.S. Hадеюсь нигде не ошибся :)
 
 /*Всего наилучшего*/ _/Stanislav/_ /*!*/               _28 ноября 2001 года_
 
 --- URAL STATE UNIVERSITY  МАТ-МЕХ
  * Origin: *** LIVE=(EVIL)^(-1) *** (2:5080/180.38)
 
 

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

Тема:    Автор:    Дата:    Клика в графе?   Vitaly Osipov   27 Nov 2001 13:00:50   Клика в графе?   Stanislav Shwartsman   27 Nov 2001 22:12:34   Клика в графе?   Vitaly Osipov   28 Nov 2001 19:20:47