Разделение (теория графов)

Граф с двумя нетривиальными сильными расщеплениями (вверху) и его расщепленное разложение (внизу). Три фактор-графа — это звезда (слева), простой граф (в центре) и полный граф (справа).

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

Разделение и разложение на разделение были впервые введены Каннингемом (1982), который также изучал варианты тех же понятий для направленных графов . ^[1]

Определения

Разрез неориентированного графа — это разбиение вершин на два непустых подмножества, стороны разреза. Подмножество ребер, имеющих одну конечную точку на каждой стороне, называется разрезом. Когда разрез образует полный двудольный граф , его разрез называется расщеплением. Таким образом, расщепление можно описать как разбиение вершин графа на два подмножества X и Y , такое, что каждый сосед X в Y смежн с каждым соседом Y в X. ^[2 ]

Разрез или расщепление тривиально, когда одна из его двух сторон имеет только одну вершину; каждое тривиальное сечение является расщеплением. Граф называется простым (относительно расщеплений), если он не имеет нетривиальных расщеплений. ^[2]

Говорят, что два расщепления пересекаются, если каждая сторона одного расщепления имеет непустое пересечение с каждой стороной другого расщепления. Расщепление называется сильным, если оно не пересекается никаким другим расщеплением. Как особый случай, каждое тривиальное расщепление является сильным. Сильные расщепления графа приводят к структуре, называемой декомпозицией расщепления или декомпозицией соединения графа. Это разложение может быть представлено деревом, листья которого соответствуют один к одному данному графу, а ребра соответствуют один к одному сильным расщеплениям графа, так что разбиение листьев, образованное удалением любого ребра из дерева, совпадает с разбиением вершин, заданным связанным сильным расщеплением. ^[2]

Каждый внутренний узел i дерева разбиения графа G связан с графом G _i , называемым графом факторизации для узла  i . Граф факторизации может быть сформирован путем удаления i из дерева, формирования подмножеств вершин в G, соответствующих листьям в каждом из полученных поддеревьев, и сворачивания каждого из этих множеств вершин в одну вершину. Каждый граф факторизации имеет одну из трех форм: это может быть простой граф, полный граф или звезда . ^[2]

Граф может иметь экспоненциально много различных разделений, но все они представлены в дереве разложения разделений либо как ребро дерева (для сильного разделения), либо как произвольное разбиение полного или звездообразного графа (для разделения, которое не является сильным). ^[2]

Примеры

В полном графе или полном двудольном графе каждое разрезание является разбиением.

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

Мост графа, не являющегося 2 -вершинно-связанным, соответствует разделению, при этом каждая сторона разделения образована вершинами с одной стороны моста. Сечение разделения представляет собой просто одно ребро моста, что является частным случаем полного двудольного подграфа. Аналогично, если v является точкой сочленения графа, не являющегося 2-вершинно-связанным , то граф имеет несколько расщеплений, в которых v и некоторые, но не все компоненты, образованные его удалением, находятся на одной стороне, а оставшиеся компоненты — на другой стороне. В этих примерах сечение разделения образует звезду .

Алгоритмы

Каннингем (1982) уже показал, что можно найти разложение расщепления за полиномиальное время . ^[1] После последующих улучшений алгоритма ^{[3] [4] Дальхаус (2000) [5]} и Шарби, де Монгольфье и Раффино (2012) открыли алгоритмы с линейным временем . ^[2]

Приложения

Раздельная декомпозиция была применена для распознавания нескольких важных классов графов:

• Дистанционно -наследственный граф — это граф, расщепленное разложение которого не содержит простых частных. На основе этой характеристики можно использовать расщепленное разложение для распознавания дистанционно-наследственных графов за линейное время. ^{[6] [7]}
• Графы четности можно распознать за линейное время как графы, в которых каждое частное разделения является либо полным, либо двудольным . ^[8]
• Круговой граф — это граф пересечений семейства хорд окружности. Данный граф является круговым графом тогда и только тогда, когда каждое из частных его разбиения на расщепление является круговым графом, поэтому проверка того, является ли граф круговым графом, может быть сведена к той же задаче на простых частных графа. Более того, когда круговой граф является простым, комбинаторная структура множества хорд, представляющих его, определяется однозначно, что упрощает задачу распознавания этой структуры. Основываясь на этих идеях, можно распознавать круговые графы за полиномиальное время. ^[3]

Разделение на части также использовалось для упрощения решения некоторых NP-трудных задач на произвольных графах: ^[9]

• Как уже заметил Каннингем (1982), максимальный независимый набор любого графа может быть найден с помощью алгоритма динамического программирования при обходе снизу вверх его дерева разбиения. В каждом узле мы выбираем максимальный вес независимого набора на его фактор-графе, взвешенный по размерам независимых наборов, уже вычисленных в дочерних узлах. ^[1]
• Хотя другой алгоритм, предложенный Каннингемом (1982), имеет недостатки, аналогичный обход снизу вверх может быть использован для вычисления максимальной клики графа путем объединения вычислений взвешенных максимальных клик в его фактор-графах. ^[9]
• Рао (2008) также представляет алгоритмы для связанных доминирующих множеств , полных доминирующих множеств и раскраски графов . ^[9]

Эти методы могут привести к полиномиальным алгоритмам времени для графов, в которых каждый факторный граф имеет простую структуру, которая позволяет эффективно вычислять его подзадачу. Например, это справедливо для графов, в которых каждый факторный граф имеет постоянный размер. ^[9]

Ссылки

1. Каннингем, Уильям Х. (1982), «Разложение ориентированных графов», SIAM Journal on Algebraic and Discrete Methods , 3 (2): 214–228, doi :10.1137/0603021, MR  0655562.
2. Charbit, Pierre; de ​​Montgolfier, Fabien; Raffinot, Mathieu (2012), «Повторный взгляд на линейное разложение по времени», SIAM Journal on Discrete Mathematics , 26 (2): 499–514, arXiv : 0902.1700 , doi : 10.1137/10080052X, MR  2967479.
3. Габор, Чаба П.; Суповит, Кеннет Дж.; Сюй, Вэнь Лянь (1989), «Распознавание круговых графов за полиномиальное время», Журнал ACM , 36 (3): 435–473, doi : 10.1145/65950.65951 , MR  1072233.
4. Ма, Це Хенг; Спинрад, Джереми (1994), « О ( n ² ) алгоритм для ненаправленного разбиения на части», Журнал алгоритмов , 16 (1): 145–160, doi :10.1006/jagm.1994.1007, MR  1251842.
5. Дальхаус, Элиас (2000), «Параллельные алгоритмы для иерархической кластеризации и приложения для разделения декомпозиции и распознавания графов четности», Журнал алгоритмов , 36 (2): 205–240, doi :10.1006/jagm.2000.1090, MR  1769515.
6. Гавой, Сирил; Поль, Кристоф (2003), «Схема маркировки расстояний и разбиение на сплиты», Дискретная математика , 273 (1–3): 115–130, doi : 10.1016/S0012-365X(03)00232-2 , MR  2025945.
7. Джоан, Эмерик; Пол, Кристоф (2012), «Разбиение на разделы и граф-меченые деревья: характеристики и полностью динамические алгоритмы для полностью разложимых графов», Дискретная прикладная математика , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016/j.dam.2011.05.007.
8. Cicerone, Serafino; Di Stefano, Gabriele (1997), "Об эквивалентности по сложности среди основных проблем на двудольных и четных графах", Алгоритмы и вычисления (Сингапур, 1997) , Lecture Notes in Comput. Sci., т. 1350, Springer, Берлин, стр. 354–363, doi :10.1007/3-540-63890-3_38, ISBN 978-3-540-63890-2, МР  1651043.
9. Рао, Михаэль (2008), «Решение некоторых NP-полных задач с использованием расщепленного разложения», Discrete Applied Mathematics , 156 (14): 2768–2780, doi : 10.1016/j.dam.2007.11.013 , MR  2451095.