DAA - Макс Клик

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

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

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

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

 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 

Анализ

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

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

пример

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

Макс Клик