Клика (теория графов)
В математической области теории графов клика ( / ˈk l iː k / или / ˈ k l ɪ k / ) — это подмножество вершин неориентированного графа, такое, что каждые две различные вершины в клике смежны . То есть клика графа — это индуцированный подграф этого полного графа . Клики являются одним из основных понятий теории графов и используются во многих других математических задачах и конструкциях на графах. Клики изучались и в информатике : задача найти, есть ли в графе клика заданного размера ( задача о кликах ) является NP-полной , но, несмотря на такой результат по сложности, изучено множество алгоритмов поиска клик.
Хотя изучение полных подграфов восходит, по крайней мере, к теоретико-графовой переформулировке теории Рамсея Эрдёшем и Секересом (1935) , [1] термин «клика» взят из работы Люси и Перри (1949) , которые использовали полные подграфы в социальных сетях для модельные клики людей; то есть группы людей, все из которых знают друг друга. Клики имеют множество других применений в науке, особенно в биоинформатике .
Клика C в неориентированном графе G = ( V , E ) — это подмножество вершин C ⊆ V , такое, что каждые две различные вершины смежны . Это эквивалентно условию, что индуцированный подграф G, индуцированный C , является полным графом . В некоторых случаях термин «клика» может также напрямую относиться к подграфу.
Максимальная клика — это клика, которую нельзя расширить за счет включения еще одной соседней вершины, то есть клика, которая не существует исключительно внутри множества вершин большей клики. Некоторые авторы определяют клики таким образом, чтобы они были максимальными, и используют другую терминологию для полных подграфов, которые не являются максимальными.
Максимальная клика графа G — это клика, в которой не существует клики с большим количеством вершин. Более того, кликовое число ω ( G ) графа G — это количество вершин в максимальной клике вG.
Число кликового покрытия графа G — это наименьшее число клик G , объединение которых покрывает множество вершин V графа.