Кликовый комплекс
Комплексы клик , комплексы флагов и конформные гиперграфы — это тесно связанные математические объекты в теории графов и геометрической топологии , каждый из которых описывает клики (полные подграфы) неориентированного графа .
Кликовый комплекс X ( G ) неориентированного графа G — это абстрактный симплициальный комплекс (т . е. семейство конечных множеств, замкнутых относительно операции взятия подмножеств), образованный множествами вершин в кликах графа G. Любое подмножество клики само является кликой, поэтому это семейство множеств удовлетворяет требованию абстрактного симплициального комплекса, согласно которому каждое подмножество множества в семействе также должно быть в семействе. Кликовый комплекс также можно рассматривать как топологическое пространство, в котором каждая клика из k вершин представлена симплексом размерности k − 1. 1 - скелет X ( G) (также известный как базовый граф комплекса) — неориентированный граф с вершиной для каждого набора из 1 элемента в семействе и ребром для каждого набора из 2 элементов в семействе; он изоморфен G . [1]
Комплексы клики также известны как комплексы Уитни , в честь Хасслера-Уитни . Триангуляция Уитни или чистая триангуляция двумерного многообразия — это вложение графа G в многообразие таким образом, что каждая грань является треугольником, а каждый треугольник — гранью. Если граф G имеет триангуляцию Уитни, он должен образовывать клеточный комплекс, изоморфный комплексу Уитни графа G . В этом случае комплекс (рассматриваемый как топологическое пространство) гомеоморфен основному многообразию. Граф Gимеет 2-многообразный кликовый комплекс и может быть вложен как триангуляция Уитни тогда и только тогда, когда G локально циклическая ; это означает, что для каждой вершины v в графе порожденный подграф , образованный соседями v , образует один цикл. [2]
Не каждый абстрактный симплициальный комплекс является кликовым комплексом. Например, рассмотрим абстрактный симплициальный комплекс над {1,2,3,4} с максимальными множествами {1,2,3}, {2,3,4}, {4,1}. Если бы это был X ( G ) некоторого графа G , то G должен был бы иметь ребра {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {4,1}, поэтому X ( G ) также должен содержать клику {1,2,3,4}.
Комплекс флагов - это абстрактный симплициальный комплекс , в котором каждое множество вершин, в котором все пары являются гранями комплекса, также является гранью комплекса. Таким образом, комплексы флагов и комплексы клик — это, по сути, одно и то же. Любой флаговый комплекс является кликовым комплексом своего 1-скелета. Однако во многих случаях удобно определять комплекс флагов непосредственно из некоторых данных, отличных от графа, а не косвенно, как кликовый комплекс графа, полученный из этих данных. [3]
Первичный граф G ( H ) гиперграфа — это граф на одном и том же множестве вершин, который имеет в качестве ребер пары вершин, появляющихся вместе в одном и том же гиперребре . Гиперграф называется конформным , если каждая максимальная клика его основного графа является гиперребром или, что то же самое, если каждая клика его основного графа содержится в некотором гиперребре. [4] Если требуется, чтобы гиперграф был замкнут вниз (чтобы он содержал все гиперребра, содержащиеся в некотором гиперребре), то гиперграф конформен именно тогда, когда он является комплексом флагов. Это роднит язык гиперграфов с языком симплициальных комплексов.
