Клик-сумма - Clique-sum
В теория графов, раздел математики, кликовая сумма представляет собой способ объединения двух графов путем их склейки в клика, аналогично связанная сумма операция в топология. Если два графика грамм и ЧАС каждая из них содержит клики равного размера, сумма клик грамм и ЧАС формируется из их несвязный союз путем определения пар вершин в этих двух кликах для формирования единой общей клики, а затем, возможно, удаления некоторых ребер клики. А 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]
Примечания
- ^ а б c Ловас (2006).
- ^ Как указано Кржиж и Томас (1990), которые перечисляют несколько дополнительных характеризаций семейств графов на основе клик-сумм.
- ^ Сеймур и Уивер (1984).
- ^ Дистель (1987).
- ^ Робертсон и Сеймур (2003)
- ^ Demaine et al. (2004); Demaine et al. (2005); Демейн, Хаджиагайи и Каварабаяши (2005).
- ^ Сеймур (1980).
Рекомендации
- Демейн, Эрик Д.; Фомин, Федор В .; Хаджиагайи, Мохаммед Таги; Тиликос, Димитриос (2005), "Субэкспоненциальные параметризованные алгоритмы на графах ограниченного рода и ЧАС-без минорных графиков », Журнал ACM, 52 (6): 866–893, arXiv:1104.2230, Дои:10.1145/1101821.1101823, МИСТЕР 2179550.
- Демейн, Эрик Д.; Хаджиагайи, Мохаммед Таги; Нисимура, Наоми; Рагде, Прабхакар; Тиликос, Димитриос (2004), «Алгоритмы приближения для классов графов, исключая графы с одним пересечением в качестве миноров», Журнал компьютерных и системных наук, 69 (2): 166–195, Дои:10.1016 / j.jcss.2003.12.001, МИСТЕР 2077379.
- Демейн, Эрик Д.; Хаджиагайи, Мохаммед Таги; Каварабаяси, Кен-ичи (2005), «Минорная теория алгоритмических графов: декомпозиция, аппроксимация и раскраска» (PDF), Материалы 46-го симпозиума IEEE по основам компьютерных наук (PDF), стр. 637–646, Дои:10.1109 / SFCS.2005.14.
- Дистель, Рейнхард (1987), "Свойство разделения плоских триангуляций", Журнал теории графов, 11 (1): 43–52, Дои:10.1002 / jgt.3190110108, МИСТЕР 0876203.
- Кржиж, Игорь; Томас, Робин (1990), "Кликовые суммы, древовидные разложения и компактность", Дискретная математика, 81 (2): 177–185, Дои:10.1016 / 0012-365X (90) 90150-G, МИСТЕР 1054976.
- Джонсон, Чарльз Р .; Макки, Терри А. (1996), "Структурные условия для циклических завершаемых графов", Дискретная математика, 159 (1–3): 155–160, Дои:10.1016 / 0012-365X (95) 00107-8, МИСТЕР 1415290.
- Ловас, Ласло (2006), «Теория графов минор», Бюллетень Американского математического общества, 43 (1): 75–86, Дои:10.1090 / S0273-0979-05-01088-8, МИСТЕР 2188176.
- Робертсон, Н.; Сеймур, П. Д. (2003), "Миноры графа XVI. Исключение неплоского графа", Журнал комбинаторной теории, Серия B, 89 (1): 43–76, Дои:10.1016 / S0095-8956 (03) 00042-X, МИСТЕР 1999736.
- Сеймур, П. Д. (1980), «Разложение обычных матроидов», Журнал комбинаторной теории, Серия B, 28 (3): 305–359, Дои:10.1016/0095-8956(80)90075-1, МИСТЕР 0579077.
- Сеймур, П. Д.; Уивер, Р. В. (1984), "Обобщение хордовых графов", Журнал теории графов, 8 (2): 241–251, Дои:10.1002 / jgt.3190080206, МИСТЕР 0742878.
- Вагнер, Клаус (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen, 114: 570–590, Дои:10.1007 / BF01594196.