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