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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Много различных задач биоинформатики смоделированы с помощью клик. Например, Бен-Дор, Шамир и Яхини[10] моделировали задачу разбиения на группы экспрессии генов, как задачу поиска минимального числа изменений, необходимых для преобразования графа данных в граф, сформированный несвязными наборами клик. Танай, Шаран и Шамир[11] обсуждают похожую задачу бикластеризации[en] данных экспрессии генов, в которой кластеры должны быть кликами. Сугихара[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..

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