Войти
Кликовая сумма двух плоских графов и графа Вагнера, образующая K 5 -без минор-граф. В теории графов, раздел математики, клика-сумма - это способ объединения двух графов путем склеивания их вместе в клике , аналогично операции связной суммы в топологии. Если два графа G и H содержат клики равного размера, клик-сумма графов G и H формируется из их непересекающегося объединения путем идентификации пар вершин в этих двух кликах для формирования единой общей клики, и затем возможно удаление некоторых ребер клики. K-кликовая сумма - это клик-сумма, в которой обе клики имеют не более k вершин. Можно также сформировать кликовые суммы и k-кликовые суммы более чем двух графов путем повторного применения операции кликовой суммы двух графов.
Различные источники расходятся во мнениях относительно того, какие ребра следует удалять как часть операции суммирования кликов. В некоторых контекстах, таких как декомпозиция хордовых графов или сжатых графов, никакие ребра не должны удаляться. В других контекстах, таких как SPQR-дерево разложение графов на их компоненты, связанные с 3 вершинами, все ребра должны быть удалены. И все же в других контекстах, таких как теорема о структуре графа для минорно-замкнутых семейств простых графов, естественно разрешить задавать набор удаленных ребер как часть операции.
Кликовые суммы имеют тесная связь с treewidth : если два графа имеют древовидную ширину не более k, то же самое делает и их k-clique-sum. Каждое дерево представляет собой 1-кликовую сумму своих ребер. Каждый последовательно-параллельный граф или, в более общем случае, каждый граф с шириной дерева не более двух, может быть сформирован как 2-кликовая сумма треугольников. Тот же тип результата распространяется на большие значения k: каждый граф с шириной дерева не более k может быть сформирован как клик-сумма графов с не более чем k + 1 вершиной; это обязательно k-кликовая сумма.
Существует также тесная связь между клик-суммой и связностью графа : если граф не (k + 1) - вершинно-связный (так что существует набор из k вершин, удаление которых разъединяет граф), то его можно представить как k-кликовую сумму меньших графов. Например, SPQR-дерево двусвязного графа представляет собой представление графа в виде 2-кликовой суммы его трехсвязных компонентов.
A удушенный граф, сформированный как клик-сумма максимального плоского графа (желтый) и двух хордовых графов (красный и синий) Клик-суммы важны в теории структур графов, где они используются для характеристики определенных семейств графов как графов, образованных клик-суммами более простых графов. Первым результатом этого типа была теорема Вагнера (1937), который доказал, что графы, не имеющие пятивершинного полного графа в качестве второстепенного, являются 3-кликой. -суммы планарных графов с восьмивершинным графом Вагнера ; эту структурную теорему можно использовать, чтобы показать, что теорема о четырех цветах эквивалентна случаю k = 5 из гипотезы Хадвигера. хордовые графы - это в точности графы, которые могут быть сформированы с помощью клик-сумм клик без удаления каких-либо ребер, а сжатые графы - это графы, которые могут быть сформированы с помощью клик-сумм клики и максимальные планарные графы без удаления ребер. Графы, в которых каждый индуцированный цикл длины четыре или больше образует минимальный разделитель графа (его удаление разбивает граф на две или более несвязанных компоненты, и ни одно подмножество цикла не имеет такого же свойства), именно клик-суммы клик и максимальных плоских графов, опять же без удаления ребер. Johnson McKee (1996) используют клик-суммы хордовых графов и последовательно-параллельных графов для характеристики частичные матрицы, имеющие положительно определенные завершения.
Можно вывести разложение на клик-сумму для любого семейства графов, замкнутого относительно второстепенных операций графа: графы в каждом минорно-замкнутом семействе могут быть сформированы из клик-сумм графов, которые «почти вложены» в поверхности ограниченного рода, что означает, что встраивание может опустить небольшое количество вершин (вершин, которые могут быть соединены с произвольным подмножеством других вершин) и вихрей (графы с низкой шириной пути, заменяющие грани вложения поверхности). Эти характеристики использовались как важный инструмент при построении алгоритмов аппроксимации и субэкспоненциальных точных алгоритмов для NP-полных задач оптимизации на семействах минорных замкнутых графов.
Теория клик-сумм может быть также обобщена с графов на матроиды. Примечательно, что теорема Сеймура о разложении характеризует обычные матроиды (матроиды, представленные полностью унимодулярными матрицами ) как 3-суммы графических матроидов (матроиды, представляющие остовные деревья на графике), кографических матроидов и определенного 10-элементного матроида.
