Кликовый граф
Кликовый граф неориентированного графа 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) соединены ребром (смежны), если соответствующие клики имеют хотя бы одну общую вершину.
Замечания
править- Кликовый граф 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].
См. также
правитьПримечания
править- ↑ Hamelink1968, с. 192–197.
- ↑ 1 2 3 4 Roberts, Spencer, 1971, с. 102–108.
- ↑ Szwarcfiter, Bornstein, 1994, с. 331–336.
- ↑ 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.
Ссылки
править- Information System on Graph Classes and their Inclusions Архивная копия от 5 февраля 2019 на Wayback Machine: clique graph Архивная копия от 9 февраля 2019 на Wayback Machine
Для улучшения этой статьи желательно:
|