Описание тега clique
Определение
Клика в неориентированном графе G = (V, E) представляет собой подмножество множества вершин C ⊆ V, такие, что для любых двух вершин в С, существует ребро, соединяющее два. Это эквивалентно тому, что подграф, индуцированный C, является полным (в некоторых случаях термин клика может также относиться к подграфу).
Максимальная клика является кликой, которая не может быть расширена за счет включения еще одну соседнюю вершину, то есть, верхушку, который не существует исключительно в пределах множества вершин большего чувств.
Максимальная клика является кликой наибольшего возможного размера в заданном графике. Кликовое число ω(G) графа G - это количество вершин в максимальной клике в G. Число пересечений графа G - это наименьшее количество клик, которые вместе покрывают все ребра графа G.
Противоположность клике - это независимое множество в том смысле, что каждая клика соответствует независимому множеству в графе дополнения. Проблема покрытия клик касается поиска как можно меньшего количества клик, включающих каждую вершину графа. Родственное понятие - биклика, полный двудольный подграф. Двудольная размерность графа - это минимальное количество бикликов, необходимых для покрытия всех ребер графа.
Проблема клики
В информатике проблема клики - это вычислительная проблема нахождения максимальной клики или всех клик в заданном графе. Это NP-полная, одна из 21 NP-полных проблем Карпа (Karp 1972). Кроме того, это трудноразрешимый метод с фиксированными параметрами, который трудно подобрать приблизительно. Тем не менее, было разработано множество алгоритмов для вычисления клик, работающих либо с экспоненциальным временем (например, алгоритм Брона – Кербоша), либо специализированных для семейств графов, таких как планарные графы или совершенные графы, для которых проблема может быть решена за полиномиальное время.