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

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

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

Хотя изучение полных подграфов началось ещё с формулировки теоремы Рамсея в терминах теории графов Эрдёшем и Секерешем (Erdős, Szekeres, 1935),[1] термин "клика" пришёл из работы Люка и Пери (Luce, Perry, 1949), использовавших полные подграфы при изучении социальных сетей для моделировании клик людей, то есть групп людей, знакомых друг с другом. Клики имеют много других приложений в науке, и, в частности, в биоинформатике.

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

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

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

Максимальная клика – это клика максимального размера для данного графа. Кликовое число ω(G) графа G - это число вершин в максимальной клике графа G. Число пересечений[en] графа G – это наименьшее число клик, вместе покрывающих все рёбра графа G.

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

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

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

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

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

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

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

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

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

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

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

Приложения[править | править вики-текст]

Слово "клика" в теории графов возникло из работы Люка и Пери [7], в которой они использовали полные подграфы для моделирования клик (групп людей, знающих друг друга) в социальных сетях. О дальнейших работах в области моделирования социальных клик с помощью теории графов смотрите работы Альбы (Alba, 1973) [8] , Пия (Peay, 1974) [9] и Дориана с Вудардом (Doreian, Woodard, 1994). [10]

Много различных задач биоинформатики смоделированы с помощью клик. Например, Бен-Дор, Шамир и Яхини (Ben-Dor, Shamir, Yakhini, 1999) [11] моделировали задачу разбиения на группы экспрессии генов как задачу поиска минимального числа изменений, необходимых для преобразования графа данных в граф, сформированный несвязными наборами клик. Танай, Шаран и Шамир (Tanay, Sharan, Shamir) [12] обсуждают похожую задачу бикластеризации[en] данных экспрессии генов, в которой кластеры должны быть кликами. Сугихара (Sugihara,1984) [13] использовал клики для моделирования экологических ниш в пищевых сетях[en]. Дей и Санков (Day, Sankoff, 1986) [14] описывает задачу описания эволюционных деревьев как задачу нахождения максимальных клик в графе, в котором вершины представляют характеристики, а две вершины соединены ребром, если существует идеальная история развития[en], комбинирующая эти две характеристики. Самудрала и Молт (Samudrala, Moult, 1998) [15] моделировали предсказание структуры белка как задачу нахождения клик в графе, вершины которого представляют позиции частей белка, а путём поиска клик в схеме взаимодействия белок-белок[en], Спирит и Мирни (Spirin, Mirny, 2003) [16] нашли кластеры белков, которые взаимодействуют тесно друг с другом и имеют слабое взаимодействие вне кластера. Анализ мощности графа[en] – это метод упрощения сложных биологических систем путём нахождения клик и связанных структур в этих системах.

В электротехнике Прихар (Prihar, 1956) [17] использовал клики для анализа коммуникационных сетей, а Паул и Унгер (Paull, Unger, 1959) [18] использовали их для разработки эффективных схем для вычисления частично определённых булевских функций. Клики используются также в автоматических генерациях тестовых шаблонов[en] – большая клика в графе несовместимости возможных дефектов даёт нижнюю ганицу множества тестовов.[19] Конг и Смит (Cong, Smith, 1993) [20] описывают применение клик для поиска иерархических структур в электрических схемах.

В химии Родес и соавторы (Rhodes, Willett, Calvet, Dunbar, Humblet, 2003) [21] использовали клики для описания химических соединений в химической базе данных[en], имеющих высокую степень похожести. Кул, Крипен и Фризен (Kuhl, Crippen, Friesen, 1983) [22] использовали клики для моделирования позиций, в которых два химических соединения связываются друг с другом.

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

  1. Paul Erdős, George Szekeres A combinatorial problem in geometry // Compositio Math.. — 1935. — Т. 2. — С. 463–470.. Более ранние работы Kuratowski, 1930 по характеризации планарных графов путём запрещения полных и полных двудольных подграфов была сформулирована скорее в топологических терминах, а не в терминах теории графов.
  2. Paul Turán On an extremal problem in graph theory (Hungarian) // Matematikai és Fizikai Lapok. — 1941. — Т. 48. — С. 436–452.
  3. Ronald Graham, B. Rothschild, Joel Spencer Ramsey Theory. — New York: John Wiley and Sons, 1990. — ISBN 0-471-50046-1..
  4. Moon, J. W., Leo Moser On cliques in graphs // Israel J. Math.. — 1965. — Т. 3. — С. 23–28. — DOI:10.1007/BF02760024.
  5. 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. — В. 2. — Т. 3. — С. 200. — DOI:10.1007/BF01894188.
  6. *Richard M. Karp Complexity of Computer Computations / R. E. Miller, J. W. Thatcher. — New York: Plenum, 1972. — С. 85–103..
  7. R. Duncan Luce, Albert D. Perry A method of matrix analysis of group structure // Psychometrika. — 1949. — В. 2. — Т. 14. — С. 95–116. — DOI:10.1007/BF02289146 — PMID 18152948..
  8. Richard D. Alba A graph-theoretic definition of a sociometric clique // Journal of Mathematical Sociology. — 1973. — В. 1. — Т. 3. — С. 113–126. — DOI:10.1080/0022250X.1973.9989826.
  9. Edmund R. Peay Hierarchical clique structures // Sociometry. — 1974. — В. 1. — С. 54–65. — DOI:10.2307/2786466.
  10. Patrick Doreian, Katherine L. Woodard Defining and locating cores and boundaries of social networks // Social Networks. — 1994. — В. 4. — Т. 16. — С. 267–293. — DOI:10.1016/0378-8733(94)90013-2.
  11. Amir Ben-Dor, Ron Shamir, Zohar Yakhini Clustering gene expression patterns. // Journal of Computational Biology. — 1999. — В. 3–4. — Т. 6. — С. 281–297. — DOI:10.1089/106652799318274 — PMID 10582567..
  12. Amos Tanay, Roded Sharan, Ron Shamir Discovering statistically significant biclusters in gene expression data // Bioinformatics. — 2002. — В. Suppl. 1. — Т. 18. — С. S136–S144. — DOI:10.1093/bioinformatics/18.suppl_1.S136 — PMID 12169541..
  13. George Sugihara Population Biology / editor: Simon A. Levin. — 1984. — Т. 30. — С. 83–101..
  14. William H. E. Day, David Sankoff Computational complexity of inferring phylogenies by compatibility // Systematic Zoology. — 1986. — В. 2. — Т. 35. — С. 224–229. — DOI:10.2307/2413432.
  15. Ram Samudrala, John Moult A graph-theoretic algorithm for comparative modeling of protein structure // Journal of Molecular Biology. — 1998. — В. 1. — Т. 279. — С. 287–302. — DOI:10.1006/jmbi.1998.1689 — PMID 9636717..
  16. Victor Spirin, Leonid A. Mirny Protein complexes and functional modules in molecular networks // Proceedings of the National Academy of Sciences. — 2003. — В. 21. — Т. 100. — С. 12123–12128. — DOI:10.1073/pnas.2032324100 — PMID 14517352..
  17. Z. Prihar Topological properties of telecommunications networks // Proceedings of the IRE. — 1956. — В. 7. — Т. 44. — С. 927–933. — DOI:10.1109/JRPROC.1956.275149.
  18. M. C. Paull, S. H. Unger Minimizing the number of states in incompletely specified sequential switching functions. — 1959. — В. 3. — Vol. EC-8. — С. 356–367. — DOI:10.1109/TEC.1959.5222697.
  19. I. Hamzaoglu, J. H. Patel Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design. — 1998. — С. 283–289. — DOI:10.1145/288548.288615.
  20. J. Cong, M. Smith Proc. 30th International Design Automation Conference. — 1993. — С. 755–760. — DOI:10.1145/157485.165119.
  21. 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. — В. 2. — Т. 43. — С. 443–448. — DOI:10.1021/ci025605o — PMID 12653507..
  22. F. S. Kuhl, G. M. Crippen, D. K. Friesen A combinatorial algorithm for calculating ligand binding // Journal of Computational Chemistry. — 1983. — В. 1. — Т. 5. — С. 24–34. — DOI:10.1002/jcc.540050105.

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

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

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