Клик-сумма - Clique-sum

Кликовая сумма двух плоских графов и графа Вагнера, образующая K5-безминорный граф.

В теория графов, раздел математики, кликовая сумма представляет собой способ объединения двух графов путем их склейки в клика, аналогично связанная сумма операция в топология. Если два графика грамм и ЧАС каждая из них содержит клики равного размера, сумма клик грамм и ЧАС формируется из их несвязный союз путем определения пар вершин в этих двух кликах для формирования единой общей клики, а затем, возможно, удаления некоторых ребер клики. А k-clique-sum - это сумма клик, в которой обе клики имеют не более k вершины. Можно также формировать клик-суммы и k-кликовые суммы более двух графов путем повторного применения операции клик-суммы двух графов.

Различные источники расходятся во мнениях относительно того, какие ребра следует удалить в рамках операции суммирования клик. В некоторых контекстах, таких как разложение хордовые графы или же удушенные графы, края не должны удаляться. В других контекстах, например SPQR-дерево разложение графов на их 3-вершинно-связные компоненты, все ребра должны быть удалены. И все же в других контекстах, таких как теорема о структуре графа для минорно-замкнутых семейств простых графов естественно разрешить указать набор удаленных ребер как часть операции.

Связанные понятия

Клик-суммы имеют тесную связь с ширина дерева: Если два графика имеют максимальную ширину дерева kи их k-кликовая сумма. Каждый дерево является 1-кликовой суммой его ребер. Каждый последовательно-параллельный граф, или, в более общем смысле, каждый график с ширина дерева не более двух, могут быть образованы как 2-кликовая сумма треугольников. Тот же тип результата распространяется на большие значения k: каждый график с ширина дерева в большинстве k может быть сформирована как клик-сумма графов с не более чем k + 1 вершина; это обязательно k-кликовая сумма.[1]

Также существует тесная связь между клик-суммой и графическое соединение: если график не (k + 1) -вершинно-связанный (так что существует набор k вершины, удаление которых разъединяет граф), то его можно представить в виде k-кликовая сумма меньших графов. Например, Дерево SPQR двусвязного графа - это представление графа в виде 2-кликовой суммы его трехкомпонентные компоненты.

Применение в теории структуры графов

А задушенный граф, образованный как клик-сумма максимальный планарный граф (желтый) и два хордовые графы (красный и синий)

Кликовые суммы важны в теории структур графов, где они используются для характеристики определенных семейств графов как графов, образованных клик-суммами более простых графов. Первый результат такого типа[2] была теорема Вагнер (1937), который доказал, что графы, не имеющие пятивершинного полного графа, как незначительный являются 3-кликовыми суммами планарные графы с восьмивершинником График Вагнера; эту структурную теорему можно использовать, чтобы показать, что теорема четырех цветов эквивалентно случаю k = 5 из Гипотеза Хадвигера. В хордовые графы - это в точности графы, которые могут быть сформированы из клик-сумм клик без удаления каких-либо ребер, а сжатые графы являются графами, которые могут быть образованы клик-суммой клик и максимальные планарные графы без удаления краев.[3] Графики, в которых каждый индуцированный цикл длины четыре или больше образует минимальный разделитель графа (его удаление разбивает граф на две или более несвязных компоненты, и ни одно подмножество цикла не обладает таким же свойством) являются в точности клик-суммами клик и максимальных планарные графы, опять же без удаления краев.[4] Джонсон и Макки (1996) использовать клик-суммы хордовых графов и последовательно-параллельных графов для характеристики частичных матрицы имея положительно определенный доработки.

Можно вывести разложение по клике для любого семейства графов, замкнутого относительно второстепенных операций над графами: графы в каждом минорно-замкнутом семействе могут быть сформированы из клик-сумм графов, которые «почти вложены» на поверхности ограниченного род, что означает, что встраивание может опустить небольшое количество вершины (вершины, которые могут быть соединены с произвольным подмножеством других вершин) и вихри (графики с низким ширина пути заменяющие грани вложения поверхности).[5] Эти характеристики использовались как важный инструмент при построении аппроксимационные алгоритмы и субэкспоненциально-точные алгоритмы для НП-полный задачи оптимизации на семействах минорно-замкнутых графов.[6]

Обобщения

Теорию клик-сумм можно также обобщить с графов на матроиды.[1] В частности, Теорема Сеймура о разложении характеризует обычные матроиды (матроиды, представимые полностью унимодулярные матрицы ) как 3-суммы графические матроиды (матроиды, представляющие остовные деревья в графе), кографические матроиды и некий 10-элементный матроид.[1][7]

Примечания

  1. ^ а б c Ловас (2006).
  2. ^ Как указано Кржиж и Томас (1990), которые перечисляют несколько дополнительных характеризаций семейств графов на основе клик-сумм.
  3. ^ Сеймур и Уивер (1984).
  4. ^ Дистель (1987).
  5. ^ Робертсон и Сеймур (2003)
  6. ^ Demaine et al. (2004); Demaine et al. (2005); Демейн, Хаджиагайи и Каварабаяши (2005).
  7. ^ Сеймур (1980).

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