DAA - Макс. Клик

В неориентированном графе cliqueявляется полным подграфом данного графа. Полный подграф означает, что все вершины этого подграфа соединены со всеми остальными вершинами этого подграфа.

Задача Max-Clique - это вычислительная задача нахождения максимальной клики графа. Max clique используется во многих реальных задачах.

Давайте рассмотрим приложение социальной сети, где вершины представляют профиль людей, а ребра представляют собой общее знакомство в графе. На этом графике клика представляет собой подмножество людей, которые все знают друг друга.

Чтобы найти максимальную клику, можно систематически проверять все подмножества, но этот вид перебора отнимает слишком много времени для сетей, содержащих более нескольких десятков вершин.

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

Анализ

Задача Max-Clique - это недетерминированный алгоритм. В этом алгоритме сначала мы пытаемся определить наборk различных вершин, а затем мы пытаемся проверить, образуют ли эти вершины полный граф.

Не существует детерминированного алгоритма с полиномиальным временем для решения этой проблемы. Эта проблема является NP-полной.

пример

Взгляните на следующий график. Здесь подграф, содержащий вершины 2, 3, 4 и 6, образует полный граф. Следовательно, этот подграф являетсяclique. Поскольку это максимально полный подграф предоставленного графика, это4-Clique.