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

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

Хотя изучение полных подграфов восходит, по крайней мере, к теоретико-графовой переформулировке теории Рамсея Эрдешем и Секересом (1935) , ^[1] термин «клика» взят из работы Люса и Перри (1949) , которые использовали полные подграфы в социальных сетях для моделирования клик людей; то есть группы людей, все из которых знают друг друга. Клики имеют множество других применений в науке, особенно в биоинформатике .

Определения

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

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

Максимальная клика графа $G$ — это клика, в которой не существует клики с большим количеством вершин. Более того, кликовое число $ω (G)$ графа $G$ — это количество вершин в максимальной клике $G.$ в

Число пересечений G $ребра$ — это наименьшее количество клик, которые вместе покрывают все $G$ .

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

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

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

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

Математика

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

Теорема Турана дает нижнюю оценку размера клики в плотных графах . ^[3] Если граф имеет достаточно много ребер, он должен содержать большую клику. Например, каждый график с $n$ вершины и более $\scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil$ ребра должны содержать трехвершинную клику.
Теорема Рэмси утверждает, что каждый граф или граф-дополнение к нему содержит клику по крайней мере с логарифмическим числом вершин. ^[4]
Согласно результату Муна и Мозера (1965) , граф с 3n вершинами может иметь не более 3 ^н максимальные клики. Графы, удовлетворяющие этой границе, представляют собой графы Муна–Мозера K _3,3,... , частный случай графов Турана, возникающих как экстремальные случаи в теореме Турана.
Гипотеза Хадвигера , до сих пор не доказанная, связывает размер наибольшей минорной клики в графе (ее число Хадвигера ) с ее хроматическим числом .
Гипотеза Эрдеша – Фабера – Ловаса связывает раскраску графа с кликами.
Гипотеза Эрдеша-Хайнала утверждает, что семейства графов, определяемые характеризацией запрещенных графов, имеют либо большие клики, либо большие коклики .

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

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

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

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

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

Информатика

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

Приложения

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

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

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

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

См. также

Нажмите игру

Примечания

^ Более ранняя работа Куратовского (1930), характеризующая плоские графы запрещенными полными и полными двудольными подграфами, изначально была сформулирована в топологических, а не в терминах теории графов.
^ Чанг, Клокс и Ли (2001) .
^ Туран (1941) .
^ Грэм, Ротшильд и Спенсер (1990) .
^ Бартелеми, Леклерк и Монжарде (1986) , стр. 200.
^ Карп (1972) .
^ Хамзаоглу и Патель (1998) .

Ссылки

Альба, Ричард Д. (1973), «Теоретико-графовое определение социометрической клики» (PDF) , Journal of Mathematical Sociology , 3 (1): 113–126, doi : 10.1080/0022250X.1973.9989826 , в архиве (PDF) из оригинала от 3 мая 2011 г. , получено 14 декабря 2009 г.
Бартелеми, Ж.-П.; Леклерк, Б.; Монжарде, Б. (1986), «Об использовании упорядоченных множеств в задачах сравнения и согласования классификаций», Journal of Classification , 3 (2): 187–224, doi : 10.1007/BF01894188 , S2CID 6092438 .
Бен-Дор, Амир; Шамир, Рон; Яхини, Зохар (1999), «Кластеризация моделей экспрессии генов», Journal of Computational Biology , 6 (3–4): 281–297, CiteSeerX 10.1.1.34.5341 , doi : 10.1089/106652799318274 , PMID 10582567 .
Чанг, Мау-Шанг; Клокс, Тон; Ли, Чуан-Мин (2001), «Максимальные трансверсали клики», Теоретико-графовые концепции в информатике (Boltenhagen, 2001) , Конспекты лекций по вычислениям. наук, том. 2204, Springer, Берлин, стр. 32–43, номер документа : 10.1007/3-540-45477-2_5 , ISBN. 978-3-540-42707-0 , МР 1905299 .
Конг, Дж.; Смит, М. (1993), «Алгоритм параллельной восходящей кластеризации с применением к разделению цепей при проектировании СБИС», Proc. 30-я Международная конференция по автоматизации проектирования , стр. 755–760, CiteSeerX 10.1.1.32.735 , doi : 10.1145/157485.165119 , ISBN 978-0897915779 , S2CID 525253 .
Дэй, Уильям Х.Э.; Санкофф, Дэвид (1986), «Вычислительная сложность определения филогении по совместимости», Systematic Zoology , 35 (2): 224–229, doi : 10.2307/2413432 , JSTOR 2413432 .
Дориан, Патрик; Вудард, Кэтрин Л. (1994), «Определение и определение ядер и границ социальных сетей», Social Networks , 16 (4): 267–293, doi : 10.1016/0378-8733(94)90013-2 .
Эрдеш, Пол ; Секерес, Джордж (1935), «Комбинаторная задача в геометрии» (PDF) , Compositio Mathematica , 2 : 463–470, заархивировано (PDF) из оригинала 22 мая 2020 г. , получено 19 декабря 2009 г.
Фестингер, Леон (1949), «Анализ социограмм с использованием матричной алгебры», Human Relations , 2 (2): 153–158, doi : 10.1177/001872674900200205 , S2CID 143609308 .
Грэм, Р .; Ротшильд, Б.; Спенсер, Дж. Х. (1990), Теория Рэмси , Нью-Йорк: Джон Уайли и сыновья, ISBN 978-0-471-50046-9 .
Хамзаоглу И.; Патель, Дж. Х. (1998), "Алгоритмы сжатия тестового набора для комбинационных схем", Proc. 1998 Международная конференция IEEE/ACM по автоматизированному проектированию , стр. 283–289, doi : 10.1145/288548.288615 , ISBN 978-1581130089 , S2CID 12258606 .
Карп, Ричард М. (1972), «Сводимость комбинаторных задач», в Miller, RE; Тэтчер, Дж. У. (ред.), Сложность компьютерных вычислений (PDF) , Нью-Йорк: Пленум, стр. 85–103, заархивировано из оригинала (PDF) 29 июня 2011 г. , получено 13 декабря 2009 г.
Куль, Ф.С.; Криппен, генеральный менеджер; Фризен, Д.К. (1983), «Комбинаторный алгоритм расчета связывания лигандов», Журнал вычислительной химии , 5 (1): 24–34, doi : 10.1002/jcc.540050105 , S2CID 122923018 .
Куратовский, Казимеж (1930), «К проблеме левых кривых в топологии» (PDF) , Fundamenta Mathematicae (на французском языке), 15 : 271–283, doi : 10.4064/fm-15-1-271-283 , в архиве ( PDF) из оригинала 23 июля 2018 г. , получено 19 декабря 2009 г.
Люс, Р. Дункан ; Перри, Альберт Д. (1949), «Метод матричного анализа групповой структуры», Psychometrika , 14 (2): 95–116, doi : 10.1007/BF02289146 , hdl : 10.1007/BF02289146 , PMID 18152948 , S2CID 16186758 .
Мун, Дж.В.; Мозер, Л. (1965), «О кликах в графах», Израильский математический журнал , 3 : 23–28, doi : 10.1007/BF02760024 , MR 0182577 .
Полл, MC; Унгер, SH (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 , S2CID 51654879 .
Родос, Николас; Уиллетт, Питер; Кальве, Ален; Данбар, Джеймс Б.; Хамблет, Кристина (2003), «CLIP: поиск по сходству в трехмерных базах данных с использованием обнаружения кликов», Journal of Chemical Information and Computer Sciences , 43 (2): 443–448, doi : 10.1021/ci025605o , PMID 12653507 .
Самудрала, Рам; Моулт, Джон (1998), «Теоретико-графовый алгоритм для сравнительного моделирования структуры белка», Journal of Molecular Biology , 279 (1): 287–302, CiteSeerX 10.1.1.64.8918 , doi : 10.1006/jmbi.1998.1689 , ПМИД 9636717 .
Спирин, Виктор; Мирный, Леонид А. (2003), «Белковые комплексы и функциональные модули в молекулярных сетях», Труды Национальной академии наук , 100 (21): 12123–12128, doi : 10.1073/pnas.2032324100 , PMC 218723 , PMID 14517352 .
Сугихара, Джордж (1984), «Теория графов, гомология и пищевые сети», в книге Левин, Саймон А. (ред.), Population Biology , Proc. Симп. Прил. Матем., вып. 30, стр. 83–101 .
Танай, Амос; Шаран, Родед; Шамир, Рон (2002), «Обнаружение статистически значимых бикластеров в данных об экспрессии генов», Bioinformatics , 18 (Приложение 1): S136–S144, doi : 10.1093/bioinformatics/18.suppl_1.S136 , PMID 12169541 .
Туран, Пауль (1941), «Об экстремальной задаче теории графов», Matematikai és Fizikai Lapok (на венгерском языке), 48 : 436–452.

Внешние ссылки

[1] Более ранняя работа Куратовского (1930), характеризующая плоские графы запрещенными полными и полными двудольными подграфами, изначально была сформулирована в топологических, а не в терминах теории графов.

[FOOTNOTEChangKloksLee2001-2] Чанг, Клокс и Ли (2001) .

[FOOTNOTETurán1941-3] Туран (1941) .

[FOOTNOTEGrahamRothschildSpencer1990-4] Грэм, Ротшильд и Спенсер (1990) .

[5] Бартелеми, Леклерк и Монжарде (1986) , стр. 200.

[FOOTNOTEKarp1972-6] Карп (1972) .

[7] Хамзаоглу и Патель (1998) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]