В теории графов , А раскол из неориентированного графа является разрез которого вырез множество образует полный двудольный граф . Граф является простым, если он не имеет разбиений. Разбиения графа могут быть собраны в древовидную структуру, называемую декомпозицией разбиения или декомпозицией соединения , которую можно построить за линейное время. Это разложение использовалось для быстрого распознавания круговых графов и графов с дистанционной наследственностью , а также для решения других задач в алгоритмах графов.
Расщепление и разбиение были впервые введены Каннингемом (1982) , который также изучал варианты тех же понятий для ориентированных графов . [1]
Определения
Вырезать из неориентированного графа является разбиение вершин на два непустых подмножества, стороны разреза. Подмножество ребер, которые имеют по одной конечной точке на каждой стороне, называется набором разрезов. Когда набор разрезов образует полный двудольный граф , его разрез называется расщеплением. Таким образом, разделение может быть описано как разбиение вершин графа на два подмножества X и Y , так что каждый сосед X в Y находится рядом с каждым соседом Y в X . [2]
Разрез или расщепление тривиальны, если на одной из его двух сторон есть только одна вершина; каждый тривиальный разрез - это раскол. Граф называется простым (относительно разбиений), если он не имеет нетривиальных разбиений. [2]
Два разделения называются пересекающимися, если каждая сторона одного разделения имеет непустое пересечение с каждой стороной другого разделения. Раскол называется сильным, если он не пересекается никаким другим расколом. Как частный случай, каждое тривиальное расщепление является сильным. Сильное разбиение графа порождает структуру, называемую разбиением на разбиение или разбиением на соединения графа. Это разложение может быть представлено деревом , листья которого взаимно однозначно соответствуют данному графу, а ребра - взаимно однозначно с сильными разбиениями графа, так что разбиение листьев, образованное удалением любого ребра из дерево совпадает с разбиением вершин, заданным соответствующим сильным разбиением. [2]
Каждый внутренний узел i дерева разбиения графа G связан с графом G i , который называется фактор-графом для узла i . Фактор-граф может быть сформирован путем удаления i из дерева, формирования подмножеств вершин в G, соответствующих листьям в каждом из результирующих поддеревьев, и сворачивания каждого из этих наборов вершин в одну вершину. Каждый фактор-граф имеет одну из трех форм: это может быть граф простых чисел, полный граф или звезда . [2]
Граф может иметь экспоненциально много разных разбиений, но все они представлены в дереве разбиения либо как ребро дерева (для сильного разбиения), либо как произвольное разбиение полного или звездообразного фактор-графа (для разбиения, которое не сильно). [2]
Примеры
В полном графе или полном двудольном графе каждый разрез является разбиением.
В графе циклов длины четыре разбиение вершин, заданное 2-раскраской цикла, является нетривиальным разбиением, но для циклов любой большей длины нетривиальных разбиений нет.
Мост графа , который не 2-края подключенного соответствует доли, с каждой стороны раскола , образованной вершинами на одной стороне моста. Множество разрезов расщепления - это просто единственное мостовое ребро, которое является частным случаем полного двудольного подграфа. Точно так же, если v является точкой сочленения графа, который не связан с двумя вершинами , тогда граф имеет несколько разбиений, в которых v и некоторые, но не все компоненты, образованные его удалением, находятся на одной стороне, а остальные компоненты находятся на другой стороне. В этих примерах набор раскроя образует звезду .
Алгоритмы
Каннингем (1982) уже показал, что можно найти расщепление за полиномиальное время . [1] После последующих улучшений алгоритма [3] [4] алгоритмы линейного времени были открыты Дальхаусом (2000) [5] и Шарбит, де Монгольфье и Раффино (2012) . [2]
Приложения
Разбиение на разбиение было применено для распознавания нескольких важных классов графов:
- Расстояние наследственного граф называется графом, расщепленное разложение не содержит простую факторизации. Основываясь на этой характеристике, можно использовать разбиение для распознавания дистанционно-наследственных графов за линейное время. [6] [7]
- Графы четности можно распознать за линейное время как графы, в которых каждое разделенное частное является либо полным, либо двудольным . [8]
- Круговая диаграмма представляет собой граф пересечений семейства хорд окружности. Данный граф является круговым графом тогда и только тогда, когда каждое из частных его расщепленного разложения является круговым графом, поэтому проверка того, является ли граф круговым графом, может быть сведена к той же задаче на простых частных графах графа. Более того, когда круговой граф является простым, комбинаторная структура множества хорд, представляющих его, определяется однозначно, что упрощает задачу распознавания этой структуры. На основе этих идей можно распознать круговые графы за полиномиальное время. [3]
Разбиение на расщепление также использовалось для упрощения решения некоторых проблем, которые NP-трудны на произвольных графах: [9]
- Как уже заметил Каннингем (1982) , максимальный независимый набор любого графа может быть найден с помощью алгоритма динамического программирования при обходе снизу вверх его расщепленного дерева декомпозиции. В каждом узле мы выбираем независимый набор с максимальным весом на его фактор-графе, взвешенный по размерам независимых наборов, уже вычисленных в дочерних узлах. [1]
- Хотя другой алгоритм, предложенный Каннингемом (1982) , ошибочен, аналогичный восходящий обход может использоваться для вычисления максимальной клики графа путем объединения вычислений взвешенных максимальных клик в его фактор-графах. [9]
- Рао (2008) также представляет алгоритмы для связанных доминирующих множеств , полных доминирующих множеств и раскраски графов . [9]
Эти методы могут привести к алгоритмам с полиномиальным временем для графов, в которых каждый фактор-граф имеет простую структуру, позволяющую эффективно вычислять его подзадачу. Например, это верно для графов, в которых каждый фактор-граф имеет постоянный размер. [9]
Рекомендации
- ^ Б с Cunningham, William H. (1982), "Разложение ориентированных графов", SIAM Journal на алгебраических и дискретных методов , 3 (2): 214-228, DOI : 10,1137 / 0603021 , МР 0655562.
- ^ а б в г д е Шарбит, Пьер; де Монгольфье, Фабьен; Раффино, Матье (2012), «Возвращение к линейному разложению с разделением времени», SIAM Journal on Discrete Mathematics , 26 (2): 499–514, arXiv : 0902.1700 , doi : 10.1137 / 10080052X , MR 2967479.
- ^ а б Gabor, Csaba P .; Supowit, Kenneth J .; Хсу, Wen Lian (1989), "признавая круг графов за полиномиальное время", Журнал ACM , 36 (3): 435-473, DOI : 10,1145 / 65950,65951 , MR 1072233.
- ^ Ма, Цзе Хэн; Спинрад, Джереми (1994), "О О ( п 2 ) алгоритм для неориентированного разложения сплит", Journal алгоритмов , 16 (1): 145-160, DOI : 10,1006 / jagm.1994.1007 , МР 1251842.
- ^ Dahlhaus, Элиас (2000), "Параллельные алгоритмы иерархической кластеризации и приложений к разделенным разложения и распознавания графа четности", Journal алгоритмов , 36 (2): 205-240, DOI : 10,1006 / jagm.2000.1090 , МР 1769515.
- ^ Гавой, Сирил; Пол, Кристоф (2003), «Схема разметки расстояний и разбиение на части», Дискретная математика , 273 (1–3): 115–130, DOI : 10.1016 / S0012-365X (03) 00232-2 , MR 2025945.
- ^ Джоан, Эмерик; Пол, Кристоф (2012), «Расщепляемая декомпозиция и деревья, помеченные графами: характеризации и полностью динамические алгоритмы для полностью разложимых графов», Дискретная прикладная математика , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016 / j. плотина.2011.05.007.
- ^ Цицероне, Серафино; Ди Стефано, Габриэле (1997), "Об эквивалентности по сложности основных задач на двудольных графах и графах четности", Алгоритмы и вычисления (Сингапур, 1997) , Конспекты лекций по вычислениям . Sci . , 1350 ., Springer, Berlin, С. 354-363, DOI : 10.1007 / 3-540-63890-3_38 , ISBN 978-3-540-63890-2, Руководство по ремонту 1651043.
- ^ а б в г Рао, Майкл (2008), "Решение некоторых NP-полных задач с помощью разделения разложение", Дискретный прикладной математики , 156 (14): 2768-2780, DOI : 10.1016 / j.dam.2007.11.013 , МР 2451095.