В математической области теории графов , 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) использует клики для моделирования экологических ниш в пищевых сетях . Дэй и Санкофф (1986) описывают проблему вывода эволюционных деревьев как задачу нахождения максимальных клик в графе, вершинами которого являются характеристики вида, где две вершины имеют общее ребро, если существует идеальная филогения, сочетающая эти два символа. Samudrala & Moult (1998) моделируют предсказание структуры белка как проблему поиска клик в графе, вершины которого представляют положения субъединиц белка. И при поиске групп в сети межбелковых взаимодействий Спирин и Мирный (2003) обнаружили кластеры белков, которые тесно взаимодействуют друг с другом и мало взаимодействуют с белками вне кластера. Анализ графа мощности - это метод упрощения сложных биологических сетей путем поиска клик и связанных структур в этих сетях.
В электротехнике , Prihar (1956) использует клики для анализа сетей связи, и Полл & Unger (1959) использовать их , чтобы разработать эффективные схемы для вычисления частично определенных булевых функций. Клики также использовались при автоматической генерации тестовых шаблонов : большая клика в графе несовместимости возможных ошибок обеспечивает нижнюю границу размера тестового набора. [7] Cong & Smith (1993) описывают применение клик для поиска иерархического разделения электронной схемы на более мелкие субъединицы.
В химии , Родос и др. (2003) используют клики для описания химических веществ в химической базе данных, которые имеют высокую степень сходства с целевой структурой. Kuhl, Crippen & Friesen (1983) используют клики для моделирования положений, в которых два химических вещества будут связываться друг с другом.
Смотрите также
- Clique Game
Заметки
- ^ Ранняя работа Куратовского (1930), характеризующая плоские графы запрещенными полными и полными двудольными подграфами, была первоначально сформулирована в топологических, а не теоретико-графовых терминах.
- ^ Чанг, Kloks & Lee (2001) .
- ^ Туран (1941) .
- ^ Грэм, Ротшильд и Спенсер (1990) .
- ^ Бартелеми, Леклерк и Monjardet (1986) , стр 200.
- ^ Карп (1972) .
- ^ 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