WikiSort.ru - Не сортированное

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

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

Определения

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

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

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

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

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

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

Математика

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

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

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

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

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

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

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

Информатика

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

Применение

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

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

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

См. также

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

Примечания

Литература

• 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:10.1007/BF02289146. — PMID 18152948.
• Moon, J. W., Leo Moser. On cliques in graphs // Israel J. Math.. — 1965. — Т. 3. — С. 23–28. — DOI:10.1007/BF02760024.
• 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:10.1080/0022250X.1973.9989826.
• Edmund R. Peay. Hierarchical clique structures // Sociometry. — 1974. — Т. 37, вып. 1. — С. 54—65. — DOI:10.2307/2786466.
• Patrick Doreian, Katherine L. Woodard. Defining and locating cores and boundaries of social networks // Social Networks. — 1994. — Т. 16, вып. 4. — С. 267—293. — DOI:10.1016/0378-8733(94)90013-2.
• 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:10.1089/106652799318274. — PMID 10582567.
• Amos Tanay, Roded Sharan, Ron Shamir. Discovering statistically significant biclusters in gene expression data // Bioinformatics. — 2002. — Т. 18, вып. Suppl. 1. — С. S136—S144. — DOI:10.1093/bioinformatics/18.suppl_1.S136. — PMID 12169541.
• 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:10.2307/2413432.
• Ram Samudrala, John Moult. A graph-theoretic algorithm for comparative modeling of protein structure // Journal of Molecular Biology. — 1998. — Т. 279, вып. 1. — С. 287—302. — DOI:10.1006/jmbi.1998.1689. — PMID 9636717.
• 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:10.1073/pnas.2032324100. — PMID 14517352.
• Z. Prihar. Topological properties of telecommunications networks // Proceedings of the IRE. — 1956. — Т. 44, вып. 7. — С. 927—933. — DOI:10.1109/JRPROC.1956.275149.
• 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:10.1109/TEC.1959.5222697.
• J. Cong, M. Smith. Proc. 30th International Design Automation Conference. — 1993. — С. 755–760. — DOI:10.1145/157485.165119.
• 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:10.1021/ci025605o. — PMID 12653507.
• 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:10.1002/jcc.540050105.

Ссылки

• Kazimierz Kuratowski. Sur le probléme des courbes gauches en Topologie (фр.) // Fundamenta Mathematicae. — 1930. — Т. 15. — С. 271—283..

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

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.