В неориентированном графе клика является полным подграфом данного графа. Полный подграф означает, что все вершины этого подграфа связаны со всеми остальными вершинами этого подграфа.
Задача Макса-Клика является вычислительной задачей нахождения максимальной клики графа. Макс клика используется во многих реальных задачах.
Давайте рассмотрим приложение для социальных сетей, где вершины представляют профиль людей, а ребра — взаимное знакомство в графе. На этом графике клика представляет собой подмножество людей, которые все знают друг друга.
Чтобы найти максимальную клику, можно систематически проверять все подмножества, но этот вид поиска методом «грубой силы» слишком трудоемкий для сетей, содержащих более нескольких десятков вершин.
Алгоритм: Макс-Клик (G, n, k) S: = Φ для I = 1 до K сделать t: = выбор (1… n) если t Є S, то возврат неудачи S: = S ∪ t для всех пар (i, j) таких, что i Є S и j Є S и i ≠ j делают если (i, j) не является ребром графа, то возврат неудачи вернуть успех
Анализ
Задача Макса-Клика является недетерминированным алгоритмом. В этом алгоритме сначала мы пытаемся определить набор из k различных вершин, а затем мы пытаемся проверить, образуют ли эти вершины полный граф.
Для решения этой проблемы не существует детерминированного алгоритма за полиномиальное время. Эта проблема NP-Complete.
пример
Посмотрите на следующий график. Здесь подграф, содержащий вершины 2, 3, 4 и 6, образует полный граф. Следовательно, этот подграф является кликой . Так как это максимально полный подграф представленного графа, это 4-клика .