19 × 3-вершинных клик (светло- и темно-синие треугольники) и
2 × 4-вершинные клики (темно-синие области).
11 светло-голубых треугольников образуют максимальные клики. Две темно-синие 4-клики являются как максимальными, так и максимальными, а число клик графа равно 4.
В теории графов клика ( / ˈ k l iː k / или / ˈ k l ɪ k / ) — это подмножество вершин неориентированного графа, такое, что каждые две различные вершины в клике являются смежными . То есть клика графа — это индуцированный подграф , который является полным . Клики являются одним из основных понятий теории графов и используются во многих других математических задачах и конструкциях на графах. Клики также изучались в информатике : задача поиска того, есть ли клика заданного размера в графе ( задача о клике ), является NP-полной , но, несмотря на этот результат сложности, было изучено много алгоритмов для поиска клик.
Хотя изучение полных подграфов восходит по крайней мере к переформулировке теории Рамсея на основе теории графов Эрдёшем и Секерешем (1935), [1] термин «клика» происходит от Люса и Перри (1949), которые использовали полные подграфы в социальных сетях для моделирования клик людей; то есть групп людей, все из которых знают друг друга. Клики имеют много других применений в науках и, в частности, в биоинформатике .
Определения
Клика , C , в неориентированном графе G = ( V , E ) — это подмножество вершин , C ⊆ V , такое, что любые две различные вершины являются смежными. Это эквивалентно условию, что индуцированный подграф G , индуцированный C, является полным графом . В некоторых случаях термин клика может также относиться к подграфу напрямую.
Максимальная клика — это клика, которая не может быть расширена включением еще одной смежной вершины, то есть клика, которая не существует исключительно в наборе вершин большей клики. Некоторые авторы определяют клики таким образом, что требуют, чтобы они были максимальными, и используют другую терминологию для полных подграфов, которые не являются максимальными.
Максимальная клика графа G — это клика, такая, что нет клики с большим количеством вершин. Более того, число клик ω ( G ) графа G — это число вершин в максимальной клике в G .
Число пересечений графа G — это наименьшее число клик, которые вместе покрывают все ребра графа G.
Числом покрытия клик графа G называется наименьшее число клик графа G , объединение которых покрывает множество вершин V графа.
Максимальная клика, трансверсальная графу, — это подмножество вершин, обладающее тем свойством, что каждая максимальная клика графа содержит по крайней мере одну вершину в подмножестве. [2]
Противоположностью клики является независимое множество , в том смысле, что каждая клика соответствует независимому множеству в дополнительном графе . Задача покрытия кликой заключается в нахождении как можно меньшего числа клик, включающих каждую вершину в графе.
Математические результаты, касающиеся клик, включают следующее.
Теорема Турана дает нижнюю границу размера клики в плотных графах . [3] Если граф имеет достаточно много ребер, он должен содержать большую клику. Например, каждый граф с вершинами и более чем ребрами должен содержать клику из трех вершин.
Теорема Рамсея утверждает, что каждый граф или его дополнение содержит клику с по крайней мере логарифмическим числом вершин. [4]
Согласно результату Муна и Мозера (1965), граф с 3 n вершинами может иметь не более 3 n максимальных клик. Графы, удовлетворяющие этой границе, — это графы Муна–Мозера K 3,3,... , частный случай графов Турана, возникающих как экстремальные случаи в теореме Турана.
Хордовый граф — это граф, вершины которого можно упорядочить в порядке совершенного исключения, то есть в таком порядке, что соседи каждой вершины v , которые идут позже v в порядке, образуют клику.
Кограф — это граф , все индуцированные подграфы которого обладают тем свойством, что любая максимальная клика пересекает любое максимальное независимое множество в одной вершине.
Интервальный граф — это граф, максимальные клики которого можно упорядочить таким образом, что для каждой вершины v клики, содержащие v, являются последовательными в упорядочении.
Линейный граф — это граф, ребра которого могут быть покрыты непересекающимися по ребрам кликами таким образом, что каждая вершина принадлежит ровно двум кликам в покрытии.
Симплексный граф — это неориентированный граф κ( G ) с вершиной для каждой клики в графе G и ребром, соединяющим две клики, которые отличаются одной вершиной. Это пример медианного графа и он связан с медианной алгеброй на кликах графа: медиана m ( A , B , C ) трех клик A , B , и C — это клика, вершины которой принадлежат по крайней мере двум из клик A , B , и C . [5]
Сумма клик — это метод объединения двух графов путем их слияния по общей клике.
Ширина клики — это понятие сложности графа с точки зрения минимального числа различных меток вершин, необходимых для построения графа из непересекающихся объединений, операций перемаркировки и операций, которые соединяют все пары вершин с заданными метками. Графы с шириной клики один — это в точности непересекающиеся объединения клик.
Число пересечений графа — это минимальное число клик, необходимое для покрытия всех ребер графа.
Слово «клика» в его графо-теоретическом использовании возникло из работы Люса и Перри (1949), которые использовали полные подграфы для моделирования клик (групп людей, которые все знают друг друга) в социальных сетях . То же самое определение использовал Фестингер (1949) в статье, использующей менее технические термины. Обе работы посвящены выявлению клик в социальной сети с использованием матриц. О дальнейших попытках моделирования социальных клик с помощью графа см., например, Альбу (1973), Пей (1974) и Дориана и Вударда (1994).
Многие различные проблемы биоинформатики были смоделированы с использованием клик. Например, Бен-Дор, Шамир и Якхини (1999) моделируют проблему кластеризации данных экспрессии генов как задачу нахождения минимального количества изменений, необходимых для преобразования графа, описывающего данные, в граф, сформированный как непересекающееся объединение клик; Танай, Шаран и Шамир (2002) обсуждают похожую задачу бикластеризации для данных экспрессии, в которой кластеры должны быть кликами. Сугихара (1984) использует клики для моделирования экологических ниш в пищевых сетях . Дэй и Санкофф (1986) описывают проблему вывода эволюционных деревьев как задачу нахождения максимальных клик в графе, вершинами которого являются характеристики вида, где две вершины имеют общее ребро, если существует идеальная филогения, объединяющая эти два признака. Samudrala & Moult (1998) моделируют предсказание структуры белка как проблему поиска клик в графе, вершины которого представляют позиции субъединиц белка. А путем поиска клик в сети белок-белкового взаимодействия Spirin & Mirny (2003) обнаружили кластеры белков, которые тесно взаимодействуют друг с другом и имеют мало взаимодействий с белками вне кластера. Анализ степенных графов — это метод упрощения сложных биологических сетей путем поиска клик и связанных структур в этих сетях.
В электротехнике Prihar (1956) использует клики для анализа сетей связи, а Paull & Unger (1959) используют их для проектирования эффективных схем для вычисления частично определенных булевых функций. Клики также использовались в автоматической генерации тестовых шаблонов : большая клика в графе несовместимости возможных неисправностей обеспечивает нижнюю границу размера тестового набора. [7] Cong & Smith (1993) описывают применение клик для поиска иерархического разбиения электронной схемы на более мелкие субъединицы.
В химии Родс и др. (2003) используют клики для описания химических веществ в химической базе данных , которые имеют высокую степень сходства с целевой структурой. Кул, Криппен и Фризен (1983) используют клики для моделирования позиций, в которых два химических вещества будут связываться друг с другом.
^ Более ранняя работа Куратовского (1930), характеризующая планарные графы с помощью запрещенных полных и полных двудольных подграфов, изначально была сформулирована в топологических, а не в теоретико-графовых терминах.
^ Чанг, Клокс и Ли (2001).
↑ Туран (1941).
^ Грэм, Ротшильд и Спенсер (1990).
^ Бартелеми, Леклерк и Монжарде (1986), стр. 200.
^ Карп (1972).
^ Хамзаоглу и Патель (1998).
Ссылки
Альба, Ричард Д. (1973), «Определение социометрической клики с точки зрения теории графов» (PDF) , Журнал математической социологии , 3 (1): 113–126, doi :10.1080/0022250X.1973.9989826, архивировано (PDF) из оригинала 2011-05-03 , извлечено 2009-12-14.
Бартелеми, Ж.-П.; Леклерк, Б.; Монжарде, Б. (1986), «Об использовании упорядоченных множеств в задачах сравнения и консенсуса классификаций», Журнал классификации , 3 (2): 187–224, doi :10.1007/BF01894188, S2CID 6092438.
Чанг, Мо-Шан; Клокс, Тон; Ли, Чуан-Мин (2001), "Максимальные трансверсали клики", Графовые концепции в информатике (Больтенхаген, 2001) , Lecture Notes in Comput. Sci., т. 2204, Springer, Берлин, стр. 32–43, doi :10.1007/3-540-45477-2_5, ISBN 978-3-540-42707-0, МР 1905299.
Конг, Дж.; Смит, М. (1993), «Параллельный алгоритм кластеризации снизу вверх с приложениями к разделению схем в проектировании СБИС», Труды 30-й Международной конференции по автоматизации проектирования , стр. 755–760, CiteSeerX 10.1.1.32.735 , doi :10.1145/157485.165119, ISBN 978-0897915779, S2CID 525253.
Дей, Уильям Х. Э.; Санкофф, Дэвид (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, архивировано (PDF) из оригинала 2020-05-22 , извлечено 2009-12-19.
Фестингер, Леон (1949), «Анализ социограмм с использованием матричной алгебры», Human Relations , 2 (2): 153–158, doi :10.1177/001872674900200205, S2CID 143609308.
Хамзаоглу, И.; Патель, Дж. Х. (1998), «Алгоритмы уплотнения тестового набора для комбинационных схем», Труды Международной конференции IEEE/ACM по автоматизированному проектированию 1998 г. , стр. 283–289, doi : 10.1145/288548.288615 , ISBN 978-1581130089, S2CID 12258606.
Карп, Ричард М. (1972), «Сводимость среди комбинаторных задач», в Miller, RE; Thatcher, JW (ред.), Complexity of Computer Computations (PDF) , Нью-Йорк: Plenum, стр. 85–103, архивировано из оригинала (PDF) 29-06-2011 , извлечено 13-12-2009.
Кул, Ф.С.; Криппен, Г.М.; Фризен, Д.К. (1983), «Комбинаторный алгоритм расчета связывания лиганда», Журнал вычислительной химии , 5 (1): 24–34, doi :10.1002/jcc.540050105, S2CID 122923018.
Куратовский, Казимеж (1930), «Sur le problème des courbes gauches en Topologie» (PDF) , Fundamenta Mathematicae (на французском языке), 15 : 271–283, doi : 10.4064/fm-15-1-271-283 , в архиве ( PDF) из оригинала 23 июля 2018 г. , получено 19 декабря 2009 г..
Люс, Р. Дункан ; Перри, Альберт Д. (1949), «Метод матричного анализа групповой структуры», Психометрика , 14 (2): 95–116, doi : 10.1007/BF02289146, hdl : 10.1007/BF02289146 , PMID 18152948, S2CID 16186758.
Полл, 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: поиск сходства в трехмерных базах данных с использованием обнаружения клик», Журнал химической информации и компьютерных наук , 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 , PMC 218723 , PMID 14517352.
Сугихара, Джордж (1984), «Теория графов, гомология и пищевые сети», в Левин, Саймон А. (ред.), Популяционная биология , Proc. Symp. Appl. Math., т. 30, стр. 83–101.
Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), «Обнаружение статистически значимых бикластеров в данных по экспрессии генов», Bioinformatics , 18 (Suppl. 1): S136–S144, doi : 10.1093/bioinformatics/18.suppl_1.S136 , PMID 12169541.
Туран, Пауль (1941), «Об экстремальной задаче теории графов», Matematikai és Fizikai Lapok (на венгерском языке), 48 : 436–452.
