Клик в теории графов: определение и свойства

Введение

Подмножество смежных вершин неориентированного графа

В математической области теории графов, клика (['/k//l//iː//k/ или '/k//l//ɪ//k/]) — это подмножество вершин неориентированного графа, такое что любые две различные вершины в клике смежны. Иными словами, клика графа является полным индуцированным подграфом этого графа. Клики — одна из базовых концепций теории графов и используются во многих других математических задачах и построениях на графах. Клики также изучались в информатике: задача определения, существует ли в графе клика заданного размера (задача о клике) является NP-полной, но, несмотря на эту сложность, было изучено множество алгоритмов для поиска клик. Хотя изучение полных подграфов восходит, по крайней мере, к переформулировке теории Рамзи в терминах теории графов, термин «клика» был введен , который использовал полные подграфы в социальных сетях для моделирования клик людей, то есть групп людей, все члены которых знакомы друг с другом. Клики имеют множество других применений в науке, особенно в биоинформатике.

Определения

Клика, C, в ненаправленном графе 1=G = (V, E) — это подмножество вершин, C ⊆ V, такое, что любые две различные вершины смежны. Это эквивалентно условию, что индуцированный подграф графа G, индуцированный C, является полным графом. В некоторых случаях термин "клика" может также относиться непосредственно к самому подграфу. Максимальная клика — это клика, которую нельзя расширить, добавив еще одну смежную вершину, то есть клика, которая не является частью набора вершин большей клики. Некоторые авторы определяют клики таким образом, что требуют их максимальности, и используют другую терминологию для полных подграфов, которые не являются максимальными. Максимальная клика графа G — это клика, для которой не существует клики с большим числом вершин. Кроме того, число клики ω(G) графа G — это число вершин в максимальной клике графа G. Число пересечений графа G — это наименьшее число клик, которые вместе покрывают все ребра графа G. Число покрытия кликами графа G — это наименьшее число клик графа G, объединение которых покрывает множество вершин V графа. Максимальная кликовая трансверсаль графа — это подмножество вершин, обладающее свойством, что каждая максимальная клика графа содержит хотя бы одну вершину из этого подмножества. Противоположностью клики является независимое множество, в том смысле, что каждой клике соответствует независимое множество в комплементарном графе. Задача покрытия кликами заключается в нахождении минимального числа клик, включающих все вершины графа. Связанным понятием является биклика — полный двудольный подграф. Двудольное измерение графа — это минимальное число бикликов, необходимое для покрытия всех ребер графа.

Информатика

В информатике задача о клике — это вычислительная задача поиска максимальной клики или всех клик в заданном графе. Она является NP-полной, одной из 21 NP-полных задач Карпа. Также она является вычислительно сложной для фиксированных параметров и трудно поддается аппроксимации. Тем не менее, было разработано множество алгоритмов для вычисления клик, работающих либо за экспоненциальное время (например, алгоритм Брон-Кербоша), либо специализированных для семейств графов, таких как планарные графы или совершенные графы, для которых задача может быть решена за полиномиальное время.

Приложения

Слово "клика", в его графотеоретическом использовании, возникло из работы , который использовал полные подграфы для моделирования клик (групп людей, которые все знакомы друг с другом) в социальных сетях. То же определение было использовано в статье, использующей менее технические термины. Обе работы посвящены выявлению клик в социальных сетях с использованием матриц. Для дальнейших усилий по графотеоретическому моделированию социальных клик см., например, , , и .
Многие различные задачи биоинформатики были смоделированы с использованием клик. Например, моделируют задачу кластеризации данных об экспрессии генов как поиск минимального количества изменений, необходимых для преобразования графа, описывающего данные, в граф, образованный как непересекающееся объединение клик; обсуждают аналогичную задачу бикластеризации для данных об экспрессии, в которой кластеры должны быть кликами. использует клики для моделирования экологических ниш в пищевых сетях. описывают задачу вывода эволюционных деревьев как задачу поиска максимальных клик в графе, вершины которого представляют характеристики видов, где две вершины соединены ребром, если существует идеальная филогенетическая схема, объединяющая эти два признака. моделируют предсказание структуры белка как задачу поиска клик в графе, вершины которого представляют положения субъединиц белка. И, осуществляя поиск клик в сети взаимодействия белков, обнаружили кластеры белков, которые тесно взаимодействуют друг с другом и имеют мало взаимодействий с белками вне кластера. Анализ силовых графов — это метод упрощения сложных биологических сетей путем поиска клик и связанных структур в этих сетях. В электротехнике использует клики для анализа коммуникационных сетей, а — для проектирования эффективных схем для вычисления частично заданных булевых функций. Клика также используется в автоматическом генерировании тестовых наборов: большая клика в графе несовместимости возможных неисправностей предоставляет нижнюю границу размера тестового набора. описывают применение клик в поиске иерархического разделения электронной схемы на более мелкие подмодули. В химии используют клики для описания химических веществ в химической базе данных, которые имеют высокую степень сходства с целевой структурой. используют клики для моделирования положений, в которых два химических вещества будут связываться друг с другом.