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

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

Хотя изучение полных подграфов восходит по крайней мере к теории графам переформулировке теории Рамсея по Эрдешу и Szekeres (1935) , [1] термин клика происходит от Luce & Perry (1949) , который использовал полные подграфы в социальных сетях для модельные клики людей; то есть группы людей, которые все знают друг друга. У клик есть много других приложений в науке, особенно в биоинформатике .

Определения [ править ]

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

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

Максимальная клика графа, является кликой, таким образом, что нет клики с большим количеством вершин. Более того, кликовое число графа - это количество вершин в максимальной клике в .

Число пересечений из наименьшее число клик , которые вместе охватывают все ребра .

Число клик покрытия графа - это наименьшее количество клик , объединение которых покрывает множество вершин графа.

Максимальная кликой трансверсально графа является подмножеством вершин со свойством , что каждая максимальная клика графа содержит по меньшей мере одну вершину в подмножестве. [2]

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

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

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

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

  • Теорема Турана дает нижнюю оценку размера клики в плотных графах . [3] Если граф имеет достаточно много ребер, он должен содержать большую клику. Например, каждый граф с вершинами и более чем ребрами должен содержать клику с тремя вершинами.
  • Теорема Рамсея утверждает, что каждый граф или его дополнительный граф содержит клику, по крайней мере, с логарифмическим числом вершин. [4]
  • Согласно результату Moon & Moser (1965) , граф с 3 n вершинами может иметь не более 3 n максимальных клик. Графы, удовлетворяющие этой границе, являются графами Муна – Мозера K 3,3, ... , частным случаем графов Турана, возникающих как экстремальные случаи в теореме Турана.
  • Гипотеза Хадвигера , все еще не доказанная, связывает размер самой большой клики минор в графе (ее число Хадвигера ) с ее хроматическим числом .
  • Гипотеза Эрдеша – Фабера – Ловаса - еще одно недоказанное утверждение, связывающее раскраску графов с кликами.

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

  • Кластера график представляет собой график которого соединены компоненты являются кликами.
  • Блок - диаграмма представляет собой график , чьи двухсвязные компоненты являются кликами.
  • Хорда граф представляет собой граф, вершины которого можно заказать в совершенное упорядочение выбывания упорядочения , так что соседи каждой вершину V , которые приходят позже , чем V в упорядочении образуют клику.
  • Кограф представляет собой график , у которого все индуцированные подграфы обладают тем свойством , что любая максимальная клика пересекается с любым максимальным независимым множеством в одной вершине.
  • Граф интервалов представляет собой график , чьи максимальные клики могут быть упорядочены таким образом , что для каждой вершины V , клики , содержащих V являются последовательными в заказе.
  • Линейный график представляет собой график, ребро которого может быть покрыты краями непересекающихся кликами таким образом , что каждая вершина принадлежит ровно два из клик в крышке.
  • Совершенный график представляет собой график , в котором Клика число равно хроматического числа в каждом индуцированный подграф .
  • Сплит график представляет собой график , в котором некоторая клика содержит , по меньшей мере , один конец каждого ребра.
  • Граф без треугольников представляет собой график , который не имеет , кроме его вершин и ребер клика.

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

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

Тесно связанные понятия для полных подграфов - это подразделения полных графов и миноров полных графов . В частности, теорема Куратовского и Вагнера теорема характеризуют планарные графы запрещенными полных и полных двудольных подразделений и несовершеннолетних, соответственно.

Информатика [ править ]

Основная статья: проблема клики

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

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

Слово «клика» в его теоретико-графическом использовании возникло из работы Люса и Перри (1949) , которые использовали полные подграфы для моделирования клик (групп людей, которые все знают друг друга) в социальных сетях . Такое же определение использовал Фестингер (1949) в статье, в которой использовались менее технические термины. Обе работы посвящены выявлению клик в социальной сети с помощью матриц. О продолжающихся попытках моделирования социальных клик с помощью теории графов см., Например, Alba (1973) , Peay (1974) и Doreian & Woodard (1994) .

С помощью клик было смоделировано множество различных проблем биоинформатики . Например, Бен-Дор, Шамир и Яхини (1999) моделируют проблему кластеризации данных экспрессии генов как одну из задач нахождения минимального количества изменений, необходимых для преобразования графа, описывающего данные, в граф, сформированный как несвязанное объединение клик; Танай, Шаран и Шамир (2002) обсуждают аналогичную проблему бикластеризации для данных выражений, в которых требуется, чтобы кластеры были кликами. Сугихара (1984) использует клики для моделирования экологических ниш в пищевых сетях . Day & Sankoff (1986) описывают проблему выводаэволюционные деревья как один из способов нахождения максимальных клик в графе, вершинами которого являются характеристики вида, где две вершины имеют общее ребро, если существует идеальная филогения, объединяющая эти два символа. Samudrala & Moult (1998) моделируют предсказание структуры белка как проблему поиска клик в графе, вершины которого представляют положения субъединиц белка. И при поиске групп в сети межбелковых взаимодействий Спирин и Мирный (2003) обнаружили кластеры белков, которые тесно взаимодействуют друг с другом и мало взаимодействуют с белками вне кластера. Анализ графика мощности представляет собой метод упрощения сложных биологических сетей путем поиска клик и связанных структур в этих сетях.

В электротехнике , Prihar (1956) использует клики для анализа сетей связи, и Полл & Unger (1959) использовать их , чтобы разработать эффективные схемы для вычисления частично определенных булевых функций. Клики также использовались при автоматической генерации тестовых шаблонов : большая клика в графе несовместимости возможных ошибок обеспечивает нижнюю границу размера тестового набора. [7] Cong & Smith (1993) описывают применение клик для поиска иерархического разделения электронной схемы на более мелкие субъединицы.

В химии , Родос и др. (2003) используют клики для описания химических веществ в химической базе данных, которые имеют высокую степень сходства с целевой структурой. Kuhl, Crippen & Friesen (1983) используют клики для моделирования положений, в которых два химических вещества будут связываться друг с другом.

См. Также [ править ]

  • Clique Game

Заметки [ править ]

  1. ^ Ранняя работа Куратовского (1930), характеризующая плоские графы запрещенными полными и полными двудольными подграфами, была первоначально сформулирована в топологических, а не теоретико-графовых терминах.
  2. ^ Чанг, Kloks & Lee (2001) .
  3. ^ Туран (1941) .
  4. ^ Грэм, Ротшильд и Спенсер (1990) .
  5. ^ Бартелеми, Леклерк и Monjardet (1986) , стр 200.
  6. ^ Карп (1972) .
  7. ^ Hamzaoğlu & Patel (1998) .

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

  • Alba, Richard D. (1973), "Граф теоретико-определение социометрических кликов" (PDF) , Журнал математической социологии , 3 (1): 113-126, DOI : 10,1080 / 0022250X.1973.9989826.
  • Barthélemy, J.P .; Leclerc, B .; Монжарде, Б. (1986), «Об использовании упорядоченных множеств в задачах сравнения и консенсуса классификаций», Журнал классификации , 3 (2): 187–224, doi : 10.1007 / BF01894188.
  • Бен-Дор, Амир; Шамир, Рон; Yakhini, Зохар (1999), "Кластеризация экспрессии генов структуры.", Журнал вычислительной биологии , 6 (3-4): 281-297, CiteSeerX  10.1.1.34.5341 , DOI : 10,1089 / 106652799318274 , PMID  10582567.
  • Чанг, Мо-Шан; Клокс, Тон; Ли, Чуан-Мин (2001), "Максимальные трансверсалии клик", теоретико-графические концепции в информатике (Болтенхаген, 2001) , конспекты лекций по вычислительной технике . Sci., 2204 , Springer, Berlin, стр. 32–43, DOI : 10.1007 / 3-540-45477-2_5 , ISBN 978-3-540-42707-0, MR  1905299.
  • Cong, J .; Смит, М. (1993), "Алгоритм параллельной восходящей кластеризации с приложениями к разделению схем в СБИС", Proc. 30 -я Международная конференция по автоматизированному проектированию ., Стр 755-760, CiteSeerX  10.1.1.32.735 , DOI : 10,1145 / 157485,165119 , ISBN 978-0897915779.
  • День, Уильям HE; Sankoff, Дэвид (1986), "Вычислительная сложность выводя филогенез по совместимости", Систематическая Зоология , 35 (2): 224-229, DOI : 10,2307 / 2413432 , JSTOR  2413432.
  • Дориан, Патрик; Вудард, Кэтрин Л. (1994), "Определение и центровки ядра и границы социальных сетей", Социальные сети , 16 (4): 267-293, DOI : 10,1016 / 0378-8733 (94) 90013-2.
  • Эрдеш, Пол ; Секерес, Джордж (1935), "Комбинаторная задача геометрии" (PDF) , Compositio Mathematica , 2 : 463–470.
  • Фестинджер, Leon (1949), "Анализ социограмм с использованием матричной алгебры", человеческие отношения , 2 (2): 153-158, DOI : 10,1177 / 001872674900200205.
  • Graham, R .; Ротшильд, В .; Спенсер, Дж. Х. (1990), Теория Рэмси , Нью-Йорк: Джон Вили и сыновья, ISBN 978-0-471-50046-9.
  • Hamzaoglu, I .; Patel, JH (1998), "Алгоритмы уплотнения тестового набора для комбинационных схем", Proc. 1998 IEEE / ACM Международная конференция по системе автоматизированного проектирования . С. 283-289, DOI : 10,1145 / 288548,288615 , ISBN 978-1581130089.
  • Карп, Ричард М. (1972), «Сводимость комбинаторных задач», Миллер, RE; Тэтчер, Дж. У. (ред.), Сложность компьютерных вычислений (PDF) , Нью-Йорк: Пленум, стр. 85–103..
  • Kuhl, FS; Криппен, GM; Фризен, ДК (1983), "Комбинаторный алгоритм вычисления связывания лиганда", Журнал вычислительной химии , 5 (1): 24-34, DOI : 10.1002 / jcc.540050105.
  • Kuratowski, Казимир (1930), "Sur Le problème де courbes gauches ан Topologie" (PDF) , Fundamenta Mathematicae (на французском языке), 15 : 271-283, DOI : 10,4064 / фм-15-1-271-283.
  • Люс, Р. Дункан ; Перри, Альберт Д. (1949), "Метод матричного анализа структуры группы", Psychometrika , 14 (2): 95-116, DOI : 10.1007 / BF02289146 , ЛВП : 10.1007 / BF02289146 , PMID  18152948.
  • Луна, JW; Мозер, Л. (1965), «О кликах в графах», Israel J. Math. , 3 : 23-28, DOI : 10.1007 / BF02760024 , МР  0182577.
  • Паулл, MC; Унгер, Ш. (1959), «Минимизация количества состояний в неполностью заданных последовательных функциях переключения», IRE Transactions on Electronic Computers , EC-8 (3): 356–367, doi : 10.1109 / TEC.1959.5222697.
  • Пия, Эдмунд Р. (1974), "Иерархические структуры клика", Социометрия , 37 (1): 54-65, DOI : 10,2307 / 2786466 , JSTOR  2786466.
  • Прихарь, З. (1956), "Топологические свойства телекоммуникационных сетей", Труды IRE , 44 (7): 927–933, DOI : 10.1109 / JRPROC.1956.275149.
  • Родос, Николас; Уиллетт, Питер; Кальве, Ален; Данбар, Джеймс Б.; Humblet, Christine (2003), "CLIP: сходство поиск 3D - баз данных с использованием функции обнаружения клике", Журнал химической информации и компьютерных наук , 43 (2): 443-448, DOI : 10.1021 / ci025605o , PMID  12653507.
  • Самудрала, Рам; Моулт, Джон (1998), "Теоретико-графический алгоритм для сравнительного моделирования структуры белка", Журнал молекулярной биологии , 279 (1): 287–302, CiteSeerX  10.1.1.64.8918 , doi : 10.1006 / jmbi.1998.1689 , PMID  9636717.
  • Спирин, Виктор; Мирный, Леонид А. (2003), "Белковые комплексы и функциональные модули в молекулярных сетях", Труды Национальной академии наук , 100 (21): 12123-12128, DOI : 10.1073 / pnas.2032324100 , КУПЫ  218723 , PMID  14517352.
  • Сугихара, Джордж (1984), «Теория графов, гомология и пищевые сети», в Levin, Simon A. (ed.), Population Biology , Proc. Symp. Прил. Матем., 30 , с. 83–101..
  • Танай, Амос; Шаран, Родед; Шамир, Рон (2002), "Обнаружение статистически значимые biclusters в экспрессии генов данных", биоинформатика , 18 (Suppl 1.): S136-S144, DOI : 10,1093 / биоинформатика / 18.suppl_1.S136 , PMID  12169541.
  • Туран, Пауль (1941), "Об одной экстремальной задаче теории графов", Matematikai és Fizikai Lapok (на венгерском языке), 48 : 436–452.

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

  • Вайсштейн, Эрик В. , "Clique" , MathWorld
  • Вайсштейн, Эрик В. , "Кликовое число" , MathWorld