Кликовый граф

Кликовый граф неориентированного графа 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) соединены ребром (смежны), если соответствующие клики имеют хотя бы одну общую вершину.

Замечания

Свойства

Граф 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].

См. также

Примечания
  1. Hamelink1968, с. 192–197.
  2. Roberts, Spencer, 1971, с. 102–108.
  3. Szwarcfiter, Bornstein, 1994, с. 331–336.
  4. Alcón, Faria, de Figueiredo, Gutierrez, 2009, с. 2072–2083.

Литература
  • Ronald C. Hamelink. A partial characterization of clique graphs // Journal of Combinatorial Theory. — 1968. — Т. 5. — С. 192–197. — doi:10.1016/S0021-9800(68)80055-9.
  • Fred S. Roberts, Joel H. Spencer. A characterization of clique graphs // Journal of Combinatorial Theory. — 1971. — Т. 10. — С. –108. — doi:10.1016/0095-8956(71)90070-0.
  • Jayme L. Szwarcfiter, Claudson F. Bornstein. Clique graphs of chordal and path graphs // SIAM Journal on Discrete Mathematics. — 1994. — Т. 7. — С. 331–336. — doi:10.1137/S0895480191223191.
  • Liliana Alcón, Luerbio Faria, Celina M. H. de Figueiredo, Marisa Gutierrez. The complexity of clique graph recognition // Theoretical Computer Science. — 2009. — Т. 410, вып. 21-23. — С. 2072–2083. — doi:10.1016/j.tcs.2009.01.018.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.