В теории графов , A клика граф из неориентированного графа G представляет другой график K ( G ) , которая представляет собой структуру клик в G .
Графы клик обсуждались, по крайней мере, еще в 1968 г. [1], а характеристика графов клик была дана в 1971 г. [2]
Формальное определение
Клика графа G представляет собой набор X вершина G со свойством , что каждая пара различных вершин в X является смежной в G . Максимальная клика графа G - это клика X вершин графа G , такая, что не существует клики Y вершин графа G , содержащей все X и хотя бы одну другую вершину.
Для графа G его кликовый граф K ( G ) - это такой граф, что
- каждая вершина K ( G ) представляет собой максимальную клику G ; а также
- две вершины K ( G ) смежны, если лежащие в основе клики в G имеют хотя бы одну общую вершину.
Клика граф K ( G ) также можно охарактеризовать как граф пересечений максимальных клик G . [3]
Характеристика
Граф H является графом клик K ( G ) другого графа тогда и только тогда, когда существует набор C клик в H , объединение которого покрывает все ребра H , так что C образует семейство Хелли . Это означает, что если S является подмножеством C со свойством, что каждые два члена S имеют непустое пересечение, то сам S также должен иметь непустое пересечение. Однако клики в C не обязательно должны быть максимальными кликами. [2]
Когда H = K ( G ), может быть построено семейство C этого типа, в котором каждая клика в C соответствует вершине v в G и состоит из клик в G , содержащих v . Эти клики все имеют V в их пересечения, так что они образуют клику в H . Построенное таким образом семейство C обладает свойством Хелли, потому что любое подсемейство C с попарно непустыми пересечениями должно соответствовать клике в G , которая может быть расширена до максимальной клики, принадлежащей пересечению подсемейства. [2]
И наоборот, когда Н имеет Хелли семьи С его клик, охватывающую все ребра Н , то он является клика графом K ( G ) для графа G , вершины которого является несвязным объединением вершин H и элементов C . Этот граф G имеет ребро для каждой пары клик в C с непустым пересечением, а также для каждой пары вершины H и клики в C, которая ее содержит. Тем не менее, она не содержит каких - либо ребра , соединяющие пары вершин в H . Максимальные клики в этом графе G каждый состоит из одной вершины H вместе со всеми кликами в C , которые содержат его, и их график , пересечение которых изоморфна H . [2]
Однако эта характеристика не приводит к эффективным алгоритмам: проблема распознавания того, является ли данный граф графом клики, является NP-полной . [4]
Рекомендации
- ^ Hamelink, Рональд С. (1968). «Частичная характеристика клик-графов» . Журнал комбинаторной теории . 5 (2): 192–197. DOI : 10.1016 / S0021-9800 (68) 80055-9 .
- ^ а б в г Робертс, Фред С .; Спенсер, Джоэл Х. (1971). «Характеристика клик-графов». Журнал комбинаторной теории . Серия Б. 10 (2): 102–108. DOI : 10.1016 / 0095-8956 (71) 90070-0 .
- ^ Szwarcfiter, Jayme L .; Борнштейн, Клодсон Ф. (1994). «Кликовые графы хордовых и путевых графов». Журнал СИАМ по дискретной математике . 7 (2): 331–336. CiteSeerX 10.1.1.52.521 . DOI : 10.1137 / S0895480191223191 .
- ^ Алькон, Лилиана; Фариа, Луэрбио; де Фигейредо, Селина М.Х.; Гутьеррес, Мариса (2009). «Сложность распознавания графа клик» . Теоретическая информатика . 410 (21–23): 2072–2083. DOI : 10.1016 / j.tcs.2009.01.018 . Руководство по ремонту 2519298 .