Кликовый граф неориентированного графа G — это другой граф K(G), который представляет структуру клик графа G.
Кликовые графы обсуждались по меньшей мере с 1968 года, а описание кликовых графов было дано в 1971 году.
Определение
Клика графа G — это множество X вершин графа G, обладающих свойством, что любая пара различных вершин X соединена ребром в G. Максимальная клика графа G — это клика X вершин графа G, такая, что нет клики Y вершин графа G, которая содержит все вершины X плюс по меньшей мере ещё одну вершину.
Если задан граф G, его кликовый граф K(G) — это граф, такой, что каждая вершина графа K(G) представляет максимальную клику графа G две вершины графа K(G) соединены ребром (смежны), если соответствующие клики имеют хотя бы одну общую вершину.
Замечания
Кликовый граф K(G) можно также определить как граф пересечений максимальных клик графа G.
Свойства Граф H является кликовым графом K(G) другого графа тогда и только тогда, когда существует набор C клик в H, набор которых покрывает все рёбра графа H, так что C образует семейство Хелли. Это означает, что если S является подмножеством набора C со свойством, что любые два элемента S имеют непустое пересечение, то S само должно иметь непустое пересечение. Однако клики в наборе C не обязательно должны быть максимальными кликами.
Если H =K(G), может быть построено семейство C этого типа, в котором каждая клика в C соответствует вершине v в G и состоит из клик графа G, содержащих v. Эти клики все имеют v в своём пересечении, так что они образуют клику в H. Семейство C, построенное таким образом, имеет свойство Хелли, поскольку любое подсемейство C с непустым попарным пересечением должно соответствовать клике в G, которая может быть расширена до максимальной клики, которая принадлежит пересечению подсемейства.
В обратную сторону, если H имеет семейство Хелли C клик, покрывающее все рёбра графа H, то это кликовый граф K(G) для графа G, вершинами которого служит дизъюнктное объединение вершин графа H и элементов C. Этот граф G имеет ребро для каждой пары клик в C с непустым пересечением и для каждой пары вершин графа H и клики в C, содержащей её. Однако этот граф не содержит каких-либо рёбер, соединяющих пары вершин в H. Максимальные клики в этом графе G состоят из одной вершины графа H со всеми кликами из C, содержащими её, а их граф пересечений изоморфен графу H.
Однако это описание не ведёт к эффективным алгоритмам — задача распознавания, является ли заданный граф кликовым, NP-полна.
См. также Флаговый комплекс
Примечания
Литература
Ссылки Information System on Graph Classes and their Inclusions : clique graph
Категория:Операции над графами