График клики - Clique graph

Эта статья о графе, вершины которого соответствуют максимальным кликам в другом графе. Для использования в других целях см. Граф клики (значения).

В теория графов, а граф клики из неориентированный граф грамм это еще один график K(грамм), который представляет собой структуру клики в грамм.

Графы кликов обсуждались как минимум еще в 1968 году,[1] а характеристика графов клик была дана в 1971 г.[2]

Формальное определение

А клика графа грамм это набор Икс вершин грамм со свойством, что каждая пара различных вершин в Икс соседствуют в грамм.Максимальная клика графа грамм это клика Икс вершин грамм, такой, что нет клики Y вершин грамм который содержит все Икс и как минимум еще одна вершина.

Учитывая график грамм, его кликовый граф K(грамм) - граф такой, что

  • каждая вершина K(грамм) представляет собой максимальную клику грамм; и
  • две вершины K(грамм) смежны, когда базовые клики в грамм имеют хотя бы одну общую вершину.

Граф клики K(грамм) также можно охарактеризовать как граф пересечений максимальных клик грамм.[3]

Характеристика

График ЧАС граф клики K(грамм) другого графа тогда и только тогда, когда существует набор C клик в ЧАС объединение которых покрывает все ребра ЧАС, так что C образует Семья Хелли. Это означает, что если S это подмножество C с тем свойством, что каждые два члена S имеет непустое пересечение, то S сам по себе также должен иметь непустое пересечение. Однако клики в C не обязательно должны быть максимальными кликами.[2]

Когда ЧАС =K(грамм), семья C этого типа можно построить, в котором каждая клика в C соответствует вершине v в грамм, и состоит из клик в грамм которые содержат v. Все эти клики v в их пересечении, поэтому они образуют клику в ЧАС. Семья C построенный таким образом, обладает свойством Хелли, потому что любое подсемейство C с попарно непустыми пересечениями должна соответствовать клике в грамм, которая продолжается до максимальной клики, принадлежащей пересечению подсемейства.[2]

И наоборот, когда ЧАС есть семья Хелли C клик, покрывающих все ребра ЧАС, то это кликовый граф K(грамм) для графика грамм чьи вершины несвязный союз вершин ЧАС и элементы C. Этот график грамм имеет ребро для каждой пары клик в C с непустым пересечением, и для каждой пары вершины ЧАС и клика в C который его содержит. Однако он не содержит ребер, соединяющих пары вершин в ЧАС. Максимальные клики в этом графе грамм каждый состоит из одной вершины ЧАС вместе со всеми кликами в C которые содержат его, и их граф пересечения изоморфенЧАС.[2]

Однако эта характеристика не приводит к эффективным алгоритмам: проблема распознавания того, является ли данный граф графом клики, является НП-полный.[4]

Рекомендации

  1. ^ Хамелинк, Рональд С. (1968). «Частичная характеристика кликовых графов». Журнал комбинаторной теории. 5 (2): 192–197. Дои:10.1016 / S0021-9800 (68) 80055-9.
  2. ^ а б c d Робертс, Фред С.; Спенсер, Джоэл Х. (1971). «Характеристика кликовых графов». Журнал комбинаторной теории. Серия Б. 10 (2): 102–108. Дои:10.1016/0095-8956(71)90070-0.
  3. ^ Шварцфитер, Джейме Л.; Борнштейн, Клодсон Ф. (1994). «Кликовые графы хордовых и путевых графов». Журнал SIAM по дискретной математике. 7 (2): 331–336. CiteSeerX  10.1.1.52.521. Дои:10.1137 / S0895480191223191.
  4. ^ Алькон, Лилиана; Фариа, Луэрбио; де Фигейредо, Селина М. Х .; Гутьеррес, Мариса (2009). «Сложность распознавания кликового графа». Теоретическая информатика. 410 (21–23): 2072–2083. Дои:10.1016 / j.tcs.2009.01.018. МИСТЕР  2519298.

внешняя ссылка