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

Хотя изучение полных подграфов началось ещё с формулировки теоремы Рамсея в терминах теории графов Эрдёшем и Секерешем . Термин «клика» пришёл из работы Люка и Пери , использовавших полные подграфы при изучении социальных сетей для моделировании клик людей , то есть групп людей, знакомых друг с другом . Клики имеют много других приложений в науке, и, в частности, в биоинформатике .

Определения

Кликой в неориентированном графе ${\displaystyle G=(V,E)}$ называется подмножество вершин ${\displaystyle C\subseteq V}$ , такое что для любых двух вершин в ${\displaystyle C}$ существует ребро, их соединяющее. Это эквивалентно утверждению, что подграф , порождённый ${\displaystyle C}$ , является полным .

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

Наибольшая клика или клика, максимальная по размеру — это клика максимального размера для данного графа.

Кликовое число ${\displaystyle \omega (G)}$ графа ${\displaystyle G}$ — это число вершин в наибольшей клике графа ${\displaystyle G}$ . Число пересечений графа ${\displaystyle G}$ — это наименьшее число клик, вместе покрывающих все рёбра графа ${\displaystyle G}$ .

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

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

Математика

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

• Теорема Турана даёт нижнюю границу числа клик в плотных графах . Если граф имеет достаточно много рёбер, он должен содержать клику. Например, любой граф с ${\displaystyle n}$ вершинами и более чем ${\displaystyle \scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil }$ рёбрами должен иметь клику из трёх вершин.
• Теорема Рамсея утверждает, что любой граф или его дополнительный граф содержит клику как минимум с логарифмическим числом вершин.
• Согласно результатам Муна и Мозера , граф с ${\displaystyle 3n}$ вершинами может содержать максимум ${\displaystyle 3^{n}}$ наибольших клики. Графы, удовлетворяющие этой границе — это графы Муна — Мозера ${\displaystyle K_{3,3,\dots }}$ — специальный случай графов Турана , возникающий как экстремальный случай теоремы Турана.
• Гипотеза Хадвигера , остающаяся недоказанной, связывает размер наибольшей клики минора в графе (его Число Хадвигера ) с его хроматическим числом .
• — это другое недоказанное утверждение относительно связи раскраски графа с кликами.

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

• Хордальный граф — это граф, вершины которого могут быть упорядочены в порядке совершенного исключения; порядке, при котором соседи каждой вершины ${\displaystyle v}$ идут после вершины ${\displaystyle v}$ .
• Кограф — это граф, все порождённые подграфы которого имеют свойство, что любая наибольшая клика пересекается с любым наибольшим независимым множеством в единственной вершине.
• Интервальный граф — это граф, наибольшие клики которого можно упорядочить так, что для любой вершины ${\displaystyle v}$ , клики, содержащие ${\displaystyle v}$ , идут последовательно.
• Рёберный граф — это граф рёбра которого могут быть покрыты кликами без общих рёбер, притом каждая вершина будет принадлежать в точности двум кликам.
• Совершенный граф — это граф, в котором кликовое число равно хроматическому числу в каждом порождённом подграфе .
• Расщепляемый граф — это граф, в котором некоторый набор клик содержит по крайней мере одну вершину из каждого ребра.
• Граф без треугольников — это граф, в котором нет других клик кроме вершин и рёбер.

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

• графа ${\displaystyle G}$ — это ${\displaystyle X(G)}$ с симплексом для каждой клики в ${\displaystyle G}$ ;
• — это неориентированный граф ${\displaystyle \kappa (G)}$ с вершинами для каждой клики в графе ${\displaystyle G}$ и рёбрами, соединяющими две клики, отличающиеся одной вершиной. Этот граф является примером медианного графа и связан с на кликах графа — медиана ${\displaystyle m(A,B,C)}$ трёх клик ${\displaystyle A}$ , ${\displaystyle B}$ и ${\displaystyle C}$ — это клика, вершины которой принадлежат по крайней мере двум кликам из ${\displaystyle A}$ , ${\displaystyle B}$ и ${\displaystyle C}$ ;
• Сумма по клике — это метод комбинирования двух графов путём их слияния по клике;
• Кликовая ширина — это категория сложности графов в терминах минимального числа различных меток вершин, необходимых для построения графа из разрозненных наборов с помощью операций разметки и операций соединения всех пар вершин с одинаковыми метками. Графы с кликовой шириной единица — это в точности разрозненные наборы клик;
• Число пересечений графа — это минимальное число клик, необходимых для покрытия всех рёбер графа.

Близкая концепция к полным подграфам — это разбиения графов на полные подграфы и полные миноры графа . В частности, и теорема Вагнера характеризуют планарные графы путём запрещения полных и полных двудольных подграфов и миноров, соответственно.

Информатика

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

Бесплатное программное обеспечение для поиска максимальной клики

Ниже приведён список свободно распространяемого программного обеспечение для поиска максимальной клики.

Применение

Много различных задач биоинформатики смоделированы с помощью клик. Например, Бен-Дор, Шамир и Яхини моделировали задачу разбиения на группы экспрессии генов как задачу поиска минимального числа изменений, необходимых для преобразования графа данных в граф, сформированный несвязными наборами клик. Танай, Шаран и Шамир обсуждают похожую задачу бикластеризации данных экспрессии генов, в которой кластеры должны быть кликами. Сугихара использовал клики для моделирования экологических ниш в пищевых цепях . Дей и Санков описывают задачу описания эволюционных деревьев как задачу нахождения максимальных клик в графе, в котором вершины представляют характеристики, а две вершины соединены ребром, если существует , комбинирующая эти две характеристики. Самудрала и Молт моделировали предсказание структуры белка как задачу нахождения клик в графе, вершины которого представляют позиции частей белка, а путём поиска клик в схеме . Спирит и Мирни нашли кластеры белков, которые взаимодействуют тесно друг с другом и имеют слабое взаимодействие вне кластера. — это метод упрощения сложных биологических систем путём нахождения клик и связанных структур в этих системах.

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

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

См. также

• Флаговый комплекс

Примечания

Литература

• Paul Erdős, George Szekeres. A combinatorial problem in geometry // Compositio Math. — 1935. — Т. 2 . — С. 463—470 .
• Luce R. Duncan, Albert D. Perry. A method of matrix analysis of group structure // Psychometrika. — 1949. — Т. 2 , вып. 14 . — С. 95—116 . — doi : . — .
• Moon, J. W., Leo Moser. On cliques in graphs // Israel J. Math.. — 1965. — Т. 3 . — С. 23–28 . — doi : .
• Ronald Graham, B. Rothschild, Joel Spencer. Ramsey Theory. — New York: John Wiley and Sons, 1990. — ISBN 0-471-50046-1 .
• Paul Turán. On an extremal problem in graph theory (венг.) // Matematikai és Fizikai Lapok. — 1941. — Т. 48 . — С. 436—452 .
• Richard D. Alba. A graph-theoretic definition of a sociometric clique // Journal of Mathematical Sociology. — 1973. — Т. 3 , вып. 1 . — С. 113—126 . — doi : .
• Edmund R. Peay. Hierarchical clique structures // Sociometry. — 1974. — Т. 37 , вып. 1 . — С. 54—65 . — doi : . — JSTOR .
• Patrick Doreian, Katherine L. Woodard. Defining and locating cores and boundaries of social networks // Social Networks. — 1994. — Т. 16 , вып. 4 . — С. 267—293 . — doi : .
• Richard M. Karp. Complexity of Computer Computations / R. E. Miller, J. W. Thatcher. — New York: Plenum, 1972. — С. 85–103 .
• Amir Ben-Dor, Ron Shamir, Zohar Yakhini. Clustering gene expression patterns // Journal of Computational Biology. — 1999. — Т. 6 , вып. 3—4 . — С. 281—297 . — doi : . — .
• Amos Tanay, Roded Sharan, Ron Shamir. Discovering statistically significant biclusters in gene expression data // Bioinformatics. — 2002. — Т. 18 , вып. Suppl. 1 . — С. S136—S144 . — doi : . — .
• George Sugihara. Population Biology / editor: Simon A. Levin. — 1984. — Т. 30 . — С. 83—101 .
• William H. E. Day, David Sankoff. Computational complexity of inferring phylogenies by compatibility // Systematic Zoology. — 1986. — Т. 35 , вып. 2 . — С. 224—229 . — doi : . — JSTOR .
• Ram Samudrala, John Moult. A graph-theoretic algorithm for comparative modeling of protein structure // Journal of Molecular Biology. — 1998. — Т. 279 , вып. 1 . — С. 287—302 . — doi : . — .
• Victor Spirin, Leonid A. Mirny. Protein complexes and functional modules in molecular networks // Proceedings of the National Academy of Sciences . — 2003. — Т. 100 , вып. 21 . — С. 12123—12128 . — doi : . — . — PMC .
• Z. Prihar. Topological properties of telecommunications networks // . — 1956. — Т. 44 , вып. 7 . — С. 927—933 . — doi : .
• M. C. Paull, S. H. Unger. Minimizing the number of states in incompletely specified sequential switching functions. — 1959. — Vol. EC-8. — Вып. 3 . — С. 356—367 . — doi : .
• J. Cong, M. Smith. Proc. 30th International Design Automation Conference. — 1993. — С. 755–760 . — doi : .
• Nicholas Rhodes, Peter Willett, Alain Calvet, James B. Dunbar, Christine Humblet. CLIP: similarity searching of 3D databases using clique detection // Journal of Chemical Information and Computer Sciences. — 2003. — Т. 43 , вып. 2 . — С. 443—448 . — doi : . — .
• F. S. Kuhl, G. M. Crippen, D. K. Friesen. A combinatorial algorithm for calculating ligand binding // Journal of Computational Chemistry. — 1983. — Т. 5 , вып. 1 . — С. 24–34 . — doi : .
• Kazimierz Kuratowski. Sur le probléme des courbes gauches en Topologie (фр.) // Fundamenta Mathematicae. — 1930. — Т. 15 . — С. 271—283 .

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .