В теории графов , разделе математики, кликовая сумма (или клико-сумма ) — это способ объединения двух графов путем склеивания их вместе в клику , аналогично операции связной суммы в топологии . Если два графа G и H содержат клики одинакового размера, клико-сумма G и H формируется из их непересекающегося объединения путем идентификации пар вершин в этих двух кликах для формирования одной общей клики, а затем удаления всех ребер клики (исходное определение, основанное на понятии суммы множеств) или, возможно, удаления некоторых ребер клики (ослабление определения). K -кликовая сумма — это клико-сумма, в которой обе клики имеют ровно (или иногда не более) k вершин. Можно также образовывать клико-суммы и k -клико-суммы более чем двух графов путем повторного применения операции клико-суммы.
Разные источники расходятся во мнениях о том, какие ребра следует удалять в рамках операции суммы клик. В некоторых контекстах, таких как разложение хордовых графов или ущемленных графов , не следует удалять ни одно ребро. В других контекстах, таких как разложение графов по SPQR-дереву на их компоненты с тремя вершинами связности, следует удалять все ребра. А в других контекстах, таких как теорема о структуре графа для замкнутых по минору семейств простых графов, естественно разрешить указывать множество удаленных ребер как часть операции.
Клико-суммы тесно связаны с древовидной шириной : если два графа имеют древовидную ширину не более 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] Эти характеристики использовались в качестве важного инструмента при построении алгоритмов приближения и точных алгоритмов с субэкспоненциальным временем для NP-полных задач оптимизации на замкнутых по минорам семействах графов. [6]
Теория кликовых сумм может быть также обобщена с графов на матроиды . [1] Примечательно, что теорема о разложении Сеймура характеризует регулярные матроиды (матроиды, представимые полностью унимодулярными матрицами ) как 3-суммы графических матроидов (матроидов, представляющих остовные деревья в графе), кографических матроидов и определенного 10-элементного матроида. [1] [7]