Клика (теория графов)

В математической области теории графов клика ( / ˈ k l iː k / или / ˈ k l ɪ k / ) представляет собой подмножество вершин неориентированного графа, такое, что каждые две различные вершины в клике смежны . То есть клика графа — это индуцированный подграф этого полного графа . Клики являются одним из основных понятий теории графов и используются во многих других математических задачах и конструкциях на графах. Клики изучались и в информатике : задача найти, есть ли в графе клика заданного размера ( задача о кликах ) является NP-полной , но, несмотря на такой результат по сложности, изучено множество алгоритмов поиска клик. $G$ $G$

Хотя изучение полных подграфов восходит, по крайней мере, к теоретико-графовой переформулировке теории Рэмсея Эрдёшем и Секересом (1935), ^[1] термин «клика» взят из работы Люси и Перри (1949), которые использовали полные подграфы в социальных сетях для модельные клики людей; то есть группы людей, все из которых знают друг друга. Клики имеют множество других применений в науке, особенно в биоинформатике .

Определения

Клика C в неориентированном графе $G$ $=$ $($ $V$ $,$ $E$ ) $—$ это подмножество вершин C ⊆ $V$ $,$ такое, что каждые две различные вершины смежны $.$ Это эквивалентно условию, что индуцированный подграф G, $индуцированный$ C $,$ является полным графом . В некоторых случаях термин «клика» может также напрямую относиться к подграфу.

Максимальная клика — это клика, которую нельзя расширить за счет включения еще одной соседней вершины, то есть клика, которая не существует исключительно внутри множества вершин большей клики. Некоторые авторы определяют клики таким образом, чтобы они были максимальными, и используют другую терминологию для полных подграфов, которые не являются максимальными.

Максимальная клика графа $G$ — это клика, в которой не существует клики с большим количеством вершин. Более того, кликовое число $ω (G)$ графа $G$ — это количество вершин в максимальной клике в $G.$

Число пересечений G $—$ это наименьшее количество клик, которые вместе покрывают все ребра $G$ .

Число кликового покрытия графа $G$ — это наименьшее число клик $G$ , объединение которых покрывает множество вершин $V$ графа.

Максимальная кликовая трансверсаль графа — это подмножество вершин, свойство которого состоит в том, что каждая максимальная клика графа содержит хотя бы одну вершину в этом подмножестве. ^[2]

Противоположностью клике является независимое множество в том смысле, что каждая клика соответствует независимому множеству в графе дополнений . Задача о покрытии кликами заключается в поиске как можно меньшего количества клик, включающих каждую вершину графа.

Родственное понятие — биклика , полный двудольный подграф . Двудольная размерность графа — это минимальное количество биклик, необходимое для покрытия всех ребер графа.

Математика

Математические результаты, касающиеся клик, включают следующее.

Теорема Турана дает нижнюю оценку размера клики в плотных графах . ^[3] Если в графе достаточно много ребер, он должен содержать большую клику. Например, каждый граф с вершинами и более ребрами должен содержать трехвершинную клику. $п$ $\scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil$
Теорема Рамсея утверждает, что каждый граф или граф-дополнение к нему содержит клику по крайней мере с логарифмическим числом вершин. ^[4]
Согласно результату Муна и Мозера (1965), граф с 3 n вершинами может иметь не более 3 ⁿ максимальных клик. Графы, удовлетворяющие этой границе, представляют собой графы Муна–Мозера K _3,3,... , частный случай графов Турана , возникающих как экстремальные случаи в теореме Турана.
Гипотеза Хадвигера , до сих пор не доказанная, связывает размер наибольшей минорной клики в графе (ее число Хадвигера ) с ее хроматическим числом .
Гипотеза Эрдеша – Фабера – Ловаса связывает раскраску графа с кликами.
Гипотеза Эрдеша-Хайнала утверждает, что семейства графов, определенные с помощью характеризации запрещенных графов, имеют либо большие клики, либо большие коклики .

Несколько важных классов графов могут быть определены или охарактеризованы их кликами:

Кластерный граф — это граф, компоненты связности которого являются кликами.
Блочный граф — это граф, двусвязные компоненты которого являются кликами.
Хордальный граф — это граф, вершины которого можно упорядочить в идеальном порядке исключения, таком порядке, что соседи каждой вершины v , расположенные позже v в порядке, образуют клику.
Кограф — это граф , все индуцированные подграфы которого обладают тем свойством, что любая максимальная клика пересекает любое максимальное независимое множество в одной вершине.
Граф интервалов — это граф, максимальные клики которого можно упорядочить таким образом, чтобы для каждой вершины v клики, содержащие v , были последовательными в упорядочении.
Линейный граф — это граф, ребра которого могут быть покрыты кликами, не пересекающимися по ребрам, таким образом, что каждая вершина принадлежит ровно двум кликам покрытия.
Совершенный граф — это граф, в котором кликовое число равно хроматическому числу в каждом индуцированном подграфе .
Разбитый граф — это граф, в котором некоторая клика содержит хотя бы одну конечную точку каждого ребра.
Граф без треугольников — это граф, в котором нет клик, кроме вершин и ребер.

Кроме того, многие другие математические конструкции включают клики в графах. Среди них,

Кликовый комплекс графа G — это абстрактный симплициальный комплекс X ( G ) с симплексом для каждой клики в G.
Симплексный граф — это неориентированный граф κ( G ) с вершиной для каждой клики в графе G и ребром, соединяющим две клики, отличающиеся одной вершиной. Это пример медианного графа , который связан с медианной алгеброй на кликах графа: медиана m ( A , B , C ) трех клик A , B и C — это клика, вершины которой принадлежат как минимум две клики A , B и C. ^[5]
Сумма кликов — это метод объединения двух графов путем их объединения в общую клику.
Ширина клика — это понятие сложности графа с точки зрения минимального количества различных меток вершин, необходимых для построения графа из непересекающихся объединений, операций перемаркировки и операций, которые соединяют все пары вершин с заданными метками. Графы с кликовой шириной, равной единице, представляют собой в точности непересекающиеся объединения клик.
Число пересечений графа — это минимальное количество клик, необходимое для покрытия всех ребер графа.
Граф клик графа — это граф пересечений его максимальных клик.

Тесно связанными понятиями с полными подграфами являются подразделения полных графов и полные миноры графа . В частности, теорема Куратовского и теорема Вагнера характеризуют плоские графы запрещенными полными и полными двудольными подразделениями и минорами соответственно.

Информатика

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

Приложения

Слово «клика» в его теоретико-графовом использовании возникло из работы Люса и Перри (1949), которые использовали полные подграфы для моделирования клик (групп людей, которые все знают друг друга) в социальных сетях . То же определение использовал Фестингер (1949) в статье, в которой использовалось меньше технических терминов. Обе работы посвящены выявлению клик в социальной сети с помощью матриц. О продолжающихся попытках моделировать социальные клики с помощью теории графов см., например, Alba (1973), Peay (1974) и Doreian & Woodard (1994).

С помощью клик было смоделировано множество различных задач биоинформатики . Например, Бен-Дор, Шамир и Яхини (1999) моделируют проблему кластеризации данных об экспрессии генов как проблему поиска минимального числа изменений, необходимых для преобразования графа, описывающего данные, в граф, сформированный как непересекающееся объединение клик; Танай, Шаран и Шамир (2002) обсуждают аналогичную проблему бикластеризации для данных выражений, в которой кластеры должны быть кликами. Сугихара (1984) использует клики для моделирования экологических ниш в пищевых сетях . Дэй и Санкофф (1986) описывают проблему построения эволюционных деревьев как проблему поиска максимальных клик в графе, вершинами которого являются характеристики вида, где две вершины имеют общее ребро, если существует идеальная филогения, сочетающая эти два признака. Самудрала и Моулт (1998) моделируют прогнозирование структуры белка как проблему поиска клик в графе, вершины которого представляют положения субъединиц белка. А путем поиска клик в сети межбелковых взаимодействий Спирин и Мирный (2003) обнаружили кластеры белков, которые тесно взаимодействуют друг с другом и мало взаимодействуют с белками вне кластера. Анализ степенных графов — это метод упрощения сложных биологических сетей путем поиска клик и связанных с ними структур в этих сетях.

В электротехнике Прихар (1956) использует клики для анализа сетей связи, а Полл и Унгер (1959) используют их для разработки эффективных схем для вычисления частично заданных булевых функций. Клики также использовались при автоматической генерации тестовых шаблонов : большая клика в графе несовместимости возможных ошибок обеспечивает нижнюю границу размера тестового набора. ^[7] Конг и Смит (1993) описывают применение клик для поиска иерархического разделения электронной схемы на более мелкие подразделения.

В области химии Родс и др. (2003) используют клики для описания химических веществ в химической базе данных , которые имеют высокую степень сходства с целевой структурой. Куль, Криппен и Фризен (1983) используют клики для моделирования положений, в которых два химических вещества связываются друг с другом.

Смотрите также

Кликовая игра

Примечания

^ Более ранняя работа Куратовского (1930), характеризующая плоские графы запрещенными полными и полными двудольными подграфами, изначально была сформулирована в топологических, а не в терминах теории графов.
^ Чанг, Клокс и Ли (2001).
^ Туран (1941).
^ Грэм, Ротшильд и Спенсер (1990).
^ Бартелеми, Леклерк и Монжарде (1986), стр. 200.
^ Карп (1972).
^ Хамзаоглу и Патель (1998).

Внешние ссылки

Вайсштейн, Эрик В. , «Клика», MathWorld
Вайсштейн, Эрик В. , «Число клики», MathWorld