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

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

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

Понятия, связанные с данным [ править ]

Кликовые суммы имеют тесную связь с шириной дерева : если два графа имеют ширину дерева не более k , то же самое делает и их k -clique-sum. Каждое дерево представляет собой 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]

Заметки [ править ]

  1. ^ a b c Ловас (2006) .
  2. ^ Как указано Kříž & Thomas (1990) , которые перечисляют несколько дополнительных характеристик семейств графов на основе клик-сумм.
  3. ↑ Сеймур и Уивер (1984) .
  4. ^ Дистель (1987) .
  5. ↑ Робертсон и Сеймур (2003)
  6. ^ Demaine et al. (2004) ; Demaine et al. (2005) ; Demaine, Hajiaghayi и Kawarabayashi (2005) .
  7. ^ Сеймур (1980) .

Ссылки [ править ]

  • Демейн, Эрик Д .; Фомин, Федор В .; Хаджиагайи, Мохаммед Таги; Thilikos, Димитриос (2005), "субэкспоненциальный параметрироваться алгоритмами на ограниченном-роде граф и H -минор-свободные графы", Журнал ACM , 52 (6): 866-893, Arxiv : 1104,2230 , DOI : 10,1145 / 1101821,1101823 , М.Р.  2179550.
  • Демейн, Эрик Д .; Хаджиагайи, Мохаммед Таги; Нисимура, Наоми; Рагде, Прабхакар; Thilikos, Димитриос (2004), «Приближенные алгоритмы для классов графов , за исключением одиночных пересечения графиков , как несовершеннолетние», журнал компьютерных и системных наук , 69 (2): 166-195, DOI : 10.1016 / j.jcss.2003.12.001 , MR  2077379.
  • Демейн, Эрик Д .; Хаджиагайи, Мохаммед Таги; Каварабаяси, Кен-ичи (2005), «Минорная теория алгоритмических графов: декомпозиция, аппроксимация и раскраска» (PDF) , Труды 46-го симпозиума IEEE по основам информатики (PDF) , стр. 637–646, doi : 10.1109 /SFCS.2005.14.
  • Diestel, Райнхард (1987), "Свойство разделения плоских триангуляции", Журнал теории графов , 11 (1): 43-52, DOI : 10.1002 / jgt.3190110108 , МР  0876203.
  • Кржиж, Игорь; Томас, Робин (1990), "Clique-сумма, дерево-разложение и компактность", дискретная математика , 81 (2): 177-185, DOI : 10.1016 / 0012-365X (90) 90150-G , МР  1054976.
  • Джонсон, Чарльз Р .; Макки, Терри А. (1996), «Структурные условия для циклических завершаемых графов», Дискретная математика , 159 (1–3): 155–160, DOI : 10.1016 / 0012-365X (95) 00107-8 , MR  1415290.
  • Lovász, Ласло (2006), "Теория графов минор", Бюллетень Американского математического общества , 43 (1): 75-86, DOI : 10,1090 / S0273-0979-05-01088-8 , MR  2188176.
  • Робертсон, Н .; Seymour, PD (2003), "Graph несовершеннолетний XVI исключающие непланарный граф.", Журнал комбинаторной теории , серии B, 89 (1): 43-76, DOI : 10.1016 / S0095-8956 (03) 00042-X , MR  1999736.
  • Seymour, PD (1980), "Разложение регулярных матроидов", Журнал комбинаторной теории , Series B, 28 (3): 305-359, DOI : 10,1016 / 0095-8956 (80) 90075-1 , МР  0579077.
  • Сеймур, PD ; Уивер, RW (1984), "Обобщение хордальных графов", Журнал теории графов , 8 (2): 241-251, DOI : 10.1002 / jgt.3190080206 , МР  0742878.
  • Вагнер, Клаус (1937), "Убер Eigenschaft дер сделайте ebenen Komplexe", Mathematische Annalen , 114 : 570-590, DOI : 10.1007 / BF01594196.