Клика (теория графов) - Clique (graph theory)

График с

23 × 1-вершинные клики (вершины),
42 × 2-вершинные клики (ребра),
19 × 3-вершинных клик (светлые и синие треугольники), и
2 × 4-вершинные клики (синие области).

11 голубых треугольников образуют максимальные клики. Две темно-синие 4-клики являются максимальными и максимальными, а число кликов графа равно 4.

в математический зона теория графов, а клика (/ˈkляk/ или же /ˈkлɪk/) - подмножество вершин неориентированный граф такие, что каждые две различные вершины в клике смежны; то есть его индуцированный подграф является полный. Клики являются одним из основных понятий теории графов и используются во многих других математических задачах и построениях на графах. Клики также изучались в Информатика: задача найти, есть ли клика заданного размера в график (в проблема клики ) является НП-полный, но, несмотря на такую жесткость результата, многие алгоритмы поиска клик были изучены.

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

Определения

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

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

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

В номер перекрестка из грамм наименьшее количество клик, которые вместе покрывают все ребраграмм.

В номер обложки клики графа грамм наименьшее количество клик грамм объединение которых покрывает множество вершин V графа.

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

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

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

Математика

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

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

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

А кластерный граф это граф, связанные компоненты клики.
А блочный граф это граф, двусвязные компоненты клики.
А хордовый граф является графом, вершины которого можно упорядочить в совершенный порядок исключения, такой порядок, что соседи каждой вершины v которые приходят позже чем v в заказе образуют клику.
А cograph - граф, все индуцированные подграфы которого обладают тем свойством, что любая максимальная клика пересекает любую максимальное независимое множество в одной вершине.
An интервальный график - граф, максимальные клики которого можно упорядочить таким образом, что для каждой вершины v, клики, содержащие v последовательны в заказе.
А линейный график - это граф, ребра которого покрываются реберно-непересекающимися кликами таким образом, что каждая вершина принадлежит ровно двум кликам покрытия.
А идеальный график это граф, в котором кликовое число равно хроматическое число в каждом индуцированный подграф.
А разделенный график - граф, в котором некоторая клика содержит хотя бы один конец каждого ребра.
А граф без треугольников - это граф, у которого нет других клик, кроме его вершин и ребер.

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

В кликовый комплекс графа грамм является абстрактный симплициальный комплекс Икс(грамм) с симплексом для каждой клики из грамм
А симплексный график - неориентированный граф κ (грамм) с вершиной для каждой клики в графе грамм и ребро, соединяющее две клики, различающиеся одной вершиной. Это пример медианный график, и связан с медианная алгебра на кликах графа: медиана м(А,B,C) трех клик А, B, и C клика, вершины которой принадлежат хотя бы двум из клик А, B, и C.^[5]
В кликовая сумма - это метод объединения двух графов путем их слияния по общей клике.
Ширина клики представляет собой понятие сложности графа с точки зрения минимального количества различных меток вершин, необходимых для построения графа из непересекающихся объединений, операций перемаркировки и операций, которые соединяют все пары вершин с заданными метками. Графы ширины клики единица - это в точности непересекающиеся объединения клик.
В номер перекрестка графа - это минимальное количество клик, необходимое для покрытия всех ребер графа.
В граф клики графика - это граф пересечений его максимальных клик.

Понятия, тесно связанные с полными подграфами: подразделения полных графиков и полных граф миноры. Особенно, Теорема Куратовского и Теорема Вагнера охарактеризовать планарные графы запрещенным полным и полный двудольный подразделения и несовершеннолетние соответственно.

Информатика

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

Приложения

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

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

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

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

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

Игра Clique

Примечания

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

внешняя ссылка

[1] Более ранняя работа Куратовский (1930) характеризуя планарные графы запрещенным полным и полный двудольный подграфы изначально были сформулированы в топологических, а не теоретико-графовых терминах.

[FOOTNOTEChangKloksLee2001-2] Чанг, Клокс и Ли (2001).

[FOOTNOTETurán1941-3] Туран (1941).

[FOOTNOTEGrahamRothschildSpencer1990-4] Грэм, Ротшильд и Спенсер (1990).

[5] Бартелеми, Леклерк и Монжарде (1986), стр.200.

[FOOTNOTEKarp1972-6] Карп (1972).

[7] Хамзаоглу и Пател (1998).

[1]

[2]

[3]

[4]

[5]

[6]

[7]