Описание тега clique-problem
В информатике проблема клики относится к любой из проблем, связанных с поиском определенных полных подграфов ("клик") в графе, т. Е. Наборов элементов, в которых каждая пара элементов связана.
Например, проблема максимальной клики возникает в следующих реальных условиях. Рассмотрим социальную сеть, в которой вершины графа представляют людей, а ребра графа представляют собой общих знакомых. Чтобы найти самую большую подгруппу людей, которые все знают друг друга, можно систематически проверять все подмножества - процесс, который требует слишком много времени, чтобы быть практичным для социальных сетей, включающих более нескольких десятков человек. Хотя этот поиск методом перебора можно улучшить с помощью более эффективных алгоритмов, все эти алгоритмы требуют экспоненциального времени для решения проблемы. Следовательно, большая часть теории проблемы клики посвящена определению особых типов графов, допускающих более эффективные алгоритмы, или установлению вычислительной сложности общей проблемы в различных моделях вычислений.[1] Наряду с приложениями в социальных сетях проблема клики также имеет множество приложений в биоинформатике и вычислительной химии.
Проблемы клики включают:
- нахождение максимальной клики (клика с наибольшим числом вершин),
- нахождение клики максимального веса во взвешенном графе,
- перечисление всех максимальных клик (клик, которые не могут быть увеличены)
- решение проблемы принятия решения о проверке наличия в графе клики, превышающей заданный размер.
Все эти проблемы сложны: проблема решения клики является NP-полной (одна из 21 NP-полных проблем Карпа), проблема поиска максимальной клики является одновременно трудноразрешимой с фиксированным параметром и трудной для аппроксимации, а перечисление всех максимальных клик может потребовать экспоненциальное время, поскольку существуют графы с экспоненциально большим числом максимальных клик. Тем не менее, есть алгоритмы для этих проблем, которые работают в экспоненциальном времени или которые обрабатывают определенные более специализированные входные графы за полиномиальное время.