Я клика

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

В теории графов , разделе математики, клик-сумма (или клик-сумма ) — это способ объединения двух графов путем склеивания их по клике , аналогичный операции связной суммы в топологии . Если каждый из двух графов G и H содержит клики одинакового размера, сумма клик G и H формируется из их непересекающегося объединения путем идентификации пар вершин в этих двух кликах для формирования одной общей клики, а затем удаления всех ребер клики. (исходное определение, основанное на понятии суммы множества ) или, возможно, удаление некоторых ребер клики (ослабление определения). k - клика-сумма — это клик-сумма, в которой обе клики имеют ровно (или иногда не более) k вершин. Можно также формировать клик-суммы и k -кликовые суммы более чем двух графов путем многократного применения операции клик-суммы.

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

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

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

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

в теории

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

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

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

Обобщения

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

Ссылки

• Демейн, Эрик Д .; Фомин Федор Владимирович; Хаджиагайи, Мохаммед Таги; Тиликос, Димитриос (2005), «Субэкспоненциальные параметризованные алгоритмы на графах ограниченного рода и H -минорных графах», Journal of the ACM , 52 (6): 866–893, arXiv : 1104.2230 , doi : 10.1145/1101821.1101823 , MR   2179550 , S2CID   6238832 .
• Демейн, Эрик Д .; Хаджиагайи, Мохаммед Таги; Нисимура, Наоми; Рагде, Прабхакар; Тиликос, Димитриос (2004), «Алгоритмы аппроксимации классов графов, исключая графы с одним пересечением как минорные», Journal of Computer and System Sciences , 69 (2): 166–195, doi : 10.1016/j.jcss.2003.12.001 , МР   2077379 .
• Демейн, Эрик Д .; Хаджиагайи, Мохаммед Таги; Каварабаяши, Кен-ичи (2005), «Теория минорных алгоритмических графов: декомпозиция, аппроксимация и раскраска» (PDF) , Труды 46-го симпозиума IEEE по основам информатики (PDF) , стр. 637–646, doi : 10.1109 /SFCS.2005.14 , S2CID   13238254 .
• Дистель, Рейнхард (1987), «Свойство разделения плоских триангуляций», Журнал теории графов , 11 (1): 43–52, doi : 10.1002/jgt.3190110108 , MR   0876203 .
• Кржиж, Игорь; Томас, Робин (1990), «Кликовые суммы, древовидное разложение и компактность», Discrete Mathematics , 81 (2): 177–185, doi : 10.1016/0012-365X(90)90150-G , MR   1054976 .
• Джонсон, Чарльз Р.; Макки, Терри А. (1996), «Структурные условия для графов, завершаемых циклом», Discrete Mathematics , 159 (1–3): 155–160, doi : 10.1016/0012-365X(95)00107-8 , MR   1415290 .
• Ловас, Ласло (2006), «Теория граф-миноров», Бюллетень Американского математического общества , 43 (1): 75–86, doi : 10.1090/S0273-0979-05-01088-8 , MR   2188176 .
• Робертсон, Н .; Сеймур, П.Д. (2003), «Минорные графы XVI. Исключение непланарного графа», Журнал комбинаторной теории , серия B, 89 (1): 43–76, doi : 10.1016/S0095-8956(03)00042-X , МР   1999736 .
• Сеймур, П.Д. (1980), «Разложение правильных матроидов», Журнал комбинаторной теории , серия B, 28 (3): 305–359, doi : 10.1016/0095-8956(80)90075-1 , MR   0579077 .
• Сеймур, Полиция ; Уивер, Р.В. (1984), «Обобщение хордальных графов», Журнал теории графов , 8 (2): 241–251, doi : 10.1002/jgt.3190080206 , MR   0742878 .
• Вагнер, Клаус (1937), «О свойстве плоских комплексов», Mathematical Annals , 114 : 570–590, doi : 10.1007/BF01594196 , S2CID   123534907 .