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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф с 23 кликами, содержащими 1 вершину (вершины графа), 42 кликами, состоящими из 2 вершин (рёбра графа), 19 кликами, состоящими из 3 вершин (закрашенные треугольники) и двумя кликами, состоящими из 4 вершин (тёмно-синие области).
Шесть рёбер не входят ни в один треугольник и 11 светло-голубых треугольников образуют максимальные клики.
Две тёмно-синие 4-клики являются как наибольшими, так и максимальными, и кликовое число графа равно 4.

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

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

Определения[править | править вики-текст]

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

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

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

Кликовое число графа — это число вершин в максимальной клике графа . Число пересечений графа — это наименьшее число клик, вместе покрывающих все рёбра графа .

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

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

Математика[править | править вики-текст]

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

  • Теорема Турана[5] даёт нижнюю границу числа клик в плотных графах. Если граф имеет достаточно много рёбер, он должен содержать клику. Например, любой граф с вершинами и более чем рёбрами должен иметь клику из трёх вершин.
  • Теорема Рамсея[6] утверждает, что любой граф или его дополнительный граф содержит клику как минимум с логарифмическим числом вершин.
  • Согласно результатам Муна и Мозера[7], граф с вершинами может содержать максимум наибольших клики. Графы, удовлетворяющие этой границе — это графы Муна — Мозера — специальный случай графов Турана, возникающий как экстремальный случай теоремы Турана.
  • Гипотеза Хадвигера, остающаяся недоказанной, связывает размер наибольшей клики минора в графе (его Число Хадвигера) с его хроматическим числом.
  • Гипотеза Эрдёша — Фабера — Ловаша[en] — это другое недоказанное утверждение относительно связи раскраски графа с кликами.

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

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

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

  • Совокупность клик[en] графа — это абстрактная симплексная совокупность[en] с симплексом для каждой клики в ;
  • Симплекс-граф[en] — это неориентированный граф с вершинами для каждой клики в графе и рёбрами, соединяющими две клики, отличающиеся одной вершиной. Этот граф является примером медианного графа и связан с алгеброй медиан[en] на кликах графа — медиана трёх клик , и — это клика, вершины которой принадлежат по крайней мере двум кликам из , и [8];
  • Сумма по клике — это метод комбинирования двух графов путём их слияния по клике;
  • Кликовая ширина — это категория сложности графов в терминах минимального числа различных меток вершин, необходимых для построения графа из разрозненных наборов с помощью операций разметки и операций соединения всех пар вершин с одинаковыми метками. Графы с кликовой шириной единица — это в точности разрозненные наборы клик;
  • Число пересечений графа — это минимальное число клик, необходимых для покрытия всех рёбер графа.

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

Информатика[править | править вики-текст]

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

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

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

Название Лицензия Язык API Короткое описание
NetworkX BSD Python приближённое решение, смотри процедуру max_clique
maxClique CRAPL Java точные алгоритмы, реализации DIMACS
OpenOpt BSD Python точные и приближённые решения, возможность указать рёбра, которые должны быть включены (MCP)

Применение[править | править вики-текст]

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Erdős, Szekeres, 1935.
  2. Более ранние работы Казимира КуратовскогоKuratowski, 1930 по характеризации планарных графов путём запрещения полных и полных двудольных подграфов сформулирована скорее в топологических терминах, а не в терминах теории графов
  3. Luce, Perry, 1949.
  4. О дальнейших работах в области моделирования социальных клик с помощью теории графов смотрите работы АльбыAlba, 1973, Пия Peay, 1974 и Дориана с ВудардомDoreian, Woodard, 1994
  5. Turán, 1941.
  6. Graham, Rothschild, Spencer, 1990.
  7. Moon, Moser, 1965.
  8. J.-P. Barthélemy, B. Leclerc, B. Monjardet On the use of ordered sets in problems of comparison and consensus of classifications // Journal of Classification. — 1986. — Т. 3, вып. 2. — С. 200. — DOI:10.1007/BF01894188.
  9. Karp, 1972.
  10. Ben-Dor, Shamir, Yakhini, 1999.
  11. Tanay, Sharan, Shamir, 2002.
  12. Sugihara, 1984.
  13. Day, Sankoff, 1986.
  14. Samudrala, Moult, 1998.
  15. Spirin, Mirny, 2003.
  16. Prihar, 1956.
  17. Paull, Unger, 1959.
  18. I. Hamzaoglu, J. H. Patel Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design. — 1998. — С. 283—289. — DOI:10.1145/288548.288615.
  19. Cong, Smith, 1993.
  20. Rhodes, Willett, Calvet, Dunbar, Humblet, 2003.
  21. Kuhl, Crippen, Friesen, 1983.

Литература[править | править вики-текст]

  • 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 (Hungarian) // 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..

Внешние ссылки[править | править вики-текст]