Сплит (теория графов)
В теории графов разбиение разрез неориентированного графа — это , множество разрезов которого образует полный двудольный граф . Граф является простым, если он не имеет разбиений. Разбиения графа можно собрать в древовидную структуру, называемую разложением разделения или разложением соединения , которая может быть построена за линейное время. Это разложение использовалось для быстрого распознавания круговых графов и дистанционно-наследственных графов , а также для других задач графовых алгоритмов.
Сплиты и расщепленные декомпозиции были впервые введены Каннингемом (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 ]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Каннингем, Уильям Х. (1982), «Разложение ориентированных графов», SIAM Journal on Algebraic and Discrete Methods , 3 (2): 214–228, doi : 10.1137/0603021 , MR 0655562 .
- ^ Jump up to: а б с д и ж Шарби, Пьер; де Монгольфье, Фабьен; Раффино, Матье (2012), «Возврат к разложению по линейному времени», SIAM Journal on Discrete Mathematics , 26 (2): 499–514, arXiv : 0902.1700 , doi : 10.1137/10080052X , MR 2967479 .
- ^ Jump up to: а б Габор, Чаба П.; Суповит, Кеннет Дж.; Сюй, Вэнь Лянь (1989), «Распознавание круговых графов за полиномиальное время», Журнал ACM , 36 (3): 435–473, doi : 10.1145/65950.65951 , MR 1072233 .
- ^ Ма, Цзе Хэн; Спинрад, Джереми (1994), «The O ( n 2 ) алгоритм ненаправленной расщепленной декомпозиции», Journal of Algorithms , 16 (1): 145–160, doi : 10.1006/jagm.1994.1007 , MR 1251842 .
- ^ Дальхаус, Элиас (2000), «Параллельные алгоритмы для иерархической кластеризации и приложения для разделения декомпозиции и распознавания графов четности», Journal of Algorithms , 36 (2): 205–240, doi : 10.1006/jagm.2000.1090 , MR 1769515 .
- ^ Гавуа, Сирил; Пол, Кристоф (2003), «Схема дистанционной маркировки и расщепленная декомпозиция», Discrete Mathematics , 273 (1–3): 115–130, doi : 10.1016/S0012-365X(03)00232-2 , MR 2025945 .
- ^ Джоан, Эмерик; Пол, Кристоф (2012), «Разделение разложения и деревья с метками графов: характеристики и полностью динамические алгоритмы для полностью разложимых графов», Discrete Applied Mathematics , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016/j. плотина.2011.05.007 .
- ^ Цицерон, Серафино; Ди Стефано, Габриэле (1997), «Об эквивалентности по сложности основных задач на двудольных графах и графах четности», Алгоритмы и вычисления (Сингапур, 1997) , Конспекты лекций по вычислениям. наук., вып. 1350, Springer, Berlin, стр. 354–363, номер документа : 10.1007/3-540-63890-3_38 , ISBN. 978-3-540-63890-2 , МР 1651043 .
- ^ Jump up to: а б с д Рао, Микаэль (2008), «Решение некоторых NP-полных задач с использованием расщепленной декомпозиции», Discrete Applied Mathematics , 156 (14): 2768–2780, doi : 10.1016/j.dam.2007.11.013 , MR 2451095 .