Loading AI tools
Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами (здесь O обозначает «O» большое) можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин.
Более слабую теорему о планарном разбиении с O(√n log n) вершинами в сепараторе вместо O(√n) доказал Унгар (Ungar 1951), а теорему с более сильной асимптотической границей на размер сепаратора первыми доказали Липтон и Тарьян (Lipton, Tarjan 1979). После их статей теорема о планарном разбиении была передоказана несколькими различными путями, константа O(√n) в утверждении теоремы была улучшена. Теорема была расширена также на некоторые классы непланарных графов.
Повторное приложение теоремы о разбиении даёт иерархию сепараторов, которое может принять вид либо древесной декомпозиции, либо декомпозиции графа на ветви. Иерархию сепараторов можно использовать для разработки эффективных алгоритмов «Разделяй и властвуй» для планарных графов, а динамическое программирование на этих иерархиях можно использовать для разработки алгоритмов экспоненциального времени и фиксированно-параметрически разрешимых[англ.] алгоритмов для решения NP-трудных оптимизационных задач на этих графах. Иерархию сепараторов можно также использовать во вложенном рассечении[англ.], эффективном варианте исключений Гаусса для решения разреженных систем линейных алгебраических уравнений, возникающих в методе конечных элементов.
Теория двухмерности[англ.] Эрика Демайна, Фёдора Фомина, Мухаммеда Хаджигайи и Димитроса Тиликоса обобщает и существенно расширяет область применения теоремы о планарном разбиении на обширное множество задач на планарных графах и, более обще, на графах, не содержащих определённого минора.
В обычной формулировке теорема о планарном разбиении утверждает, что в любом планарном графе G = (V,E) с n вершинами существует разбиение вершин графа G на три множества A, S и B, таких, что каждое из множеств A и B имеет максимум 2n/3 вершин, S имеет O(√n) вершин, и не имеется рёбер, у которых один конец лежит в A, а другой — в B. Не требуется, чтобы A или B были связными подграфами графа G. Множество S называется сепаратором для этого разбиения.
Эквивалентная формулировка — что рёбра любого планарного графа G с n вершинами можно разбить на два не связанных рёбрами подграфа G1 и G2 таким образом, что оба подграфа имеют по меньшей мере по n/3 вершин, при этом пересечение множеств вершин этих двух подграфов имеет O(√n) вершин. Такое разбиение известно как разъединение[1]. Если разъединение задано, пересечение множеств вершин образует сепаратор, а вершины, принадлежащие одному подграфу, но не принадлежащие другому, образуют два подмножества с числом вершин, не превосходящим 2n/3. В обратную сторону, если задано разбиение на три множества A, S и B, удовлетворяющих условиям теоремы о планарном разбиении, то можно образовать разъединение, в котором рёбра с концами в A принадлежат G1, рёбра с концами в B принадлежат G2, а оставшиеся рёбра (с обоими концами в S) можно включать в любое из множеств.
Постоянная 2/3 в утверждении теоремы произвольна и может быть заменена на любое другое число из открытого интервала (1/2,1) без изменения формы теоремы — разбиение на подмножества более равного размера можно получить из менее одинаковых разбиений путём повторного разбиения большего множества на неравные части и перегруппировки получившихся связных компонент[2].
Рассмотрим решётку с r строками и c столбцами. Число n вершин этой решётки равно rc. Например, на рисунке, r = 5, c = 8 и n = 40. Если r нечётно, существует единственная центральная строка, в противном случае имеется две строки, одинаково близкие к центру. Подобным же образом, если c нечётно, имеется единственный центральный столбец, в противном случае имеется два столбца, одинаково удалённых от центра. Выбрав в качестве S эти центральные строки и столбцы и удалив S из графа, разбиваем граф на два меньших связных подграфа A и B, каждый из которых имеет не более n/2 вершин. Если r ≤ c (как на рисунке), выбор центрального столбца даст сепаратор S с r ≤ √n вершинами, и, аналогично, если c ≤ r, выбор центральной строки даст сепаратор с не более чем √n вершинами. Таким образом, любой граф решётки имеет сепаратор S с не более чем √n вершинами, удаление которого разбивает граф на две связные компоненты, размер которых не превосходит n/2[3].
Теорема о планарном разбиении утверждает, что аналогичное разбиение может быть построено для любого планарного графа. Случай произвольного планарного графа отличается от графа решётки тем, что в этом случае сепаратор имеет размер O(√n), что может быть больше числа √n, а размеры двух подмножеств A и B (в наиболее распространённой версии теоремы) не превосходят 2n/3, а не n/2, как для графов решёток. Кроме того, подмножества A и B не обязательно образуют связные подграфы.
Расслоение
Липтон и Тарьян[4] увеличивают заданный планарный граф путём добавления рёбер, если необходимо, так что он становится максимальным планарным графом (каждая грань планарного вложения является треугольником). Затем они осуществляют поиск в ширину, начиная с произвольной вершины v, и разбивают вершины на уровни согласно их расстоянию от v. Если l1 является медианой (уровнем, для которого число вершин выше него и ниже него не превышает n/2), то должны существовать уровни l0 и l2, находящиеся на O(√n) шагов выше и ниже l1, содержащие O(√n) вершин, в противном случае около уровня l1 находится более n вершин. Они показали, что должен существовать сепаратор S, образованный объединением l0 и l2 и концами рёбер графа G, которые лежат между этими двумя уровнями. Размер сепаратора S, построенного таким способом не превосходит √8√n, что примерно составляет 2.83√n. Вершины сепаратора и двух множеств разбиения можно найти за линейное время.
Это доказательство теоремы о планарном разбиении применимо также для взвешенных планарных графов, когда каждая вершина имеет неотрицательную цену. Граф можно разбить на три множества A, S и B, такие что A и B стоят не более 2/3 полной цены, а S имеет O(√n) вершин при отсутствии рёбер из A в B[4]. Анализируя подобные построения сепараторов более тщательно, Джиджев[2] показал, что граница размера S может быть уменьшена до √6√n, что примерно равно 2.45√n.
Хольцер, Шульц Вагнер, Прасинос и Заролигис[5] предложили упрощённую версию подхода — они расширяют граф до максимального планарного и осуществляют поиск в ширину так же, как описано выше. Затем для каждого ребра e, не принадлежащего дереву поиска, они образуют цикл, комбинируя e с путями в дереве, соединяющими концы ребра. Затем они используют в качестве сепаратора вершин один из таких циклов. Хотя этот подход не гарантирует нахождение сепаратора малого размера для планарных графов большого диаметра, их эксперименты показывают, что такой подход работает лучше, чем методы расслоения Липтона — Тарьяна и Диджева, на многих типах планарных графов.
Простые сепараторы-циклы
Для графа, который уже является максимальным планарным, можно показать строгое построение простого сепаратора-цикла, цикла малой длины, внутренняя и внешняя части которого (для конкретного планарного вложения) имеют не более 2n/3 вершин. Миллер[6] доказал это (с сепаратором размера √8√n), используя технику Липтона — Тарьяна для модифицированной версии поиска в ширину, в которой уровни образуют простые циклы.
Алон, Сеймур и Томас[7] доказали существование простого сепаратора-цикла более прямым путём — они рассматривали циклы C с не более чем √8√n вершинами, имеющими не более 2n/3 вершин вне цикла C, затем формировали разбиение на как можно более близкие части внутри и вне цикла. Они показали, что при всех этих условиях C необходимо будет сепаратором. В противном случае, расстояния внутри C должны быть равны расстояниям в диске, заключённом в C (кратчайший путь через внутренность диска образовал бы часть границы лучшего цикла). Кроме того, цикл C должен иметь длину в точности √8√n, в противном случае он может быть улучшен путём замены одного из рёбер двумя другими сторонами треугольника. Если вершины цикла C пронумерованы (по часовой стрелке) от 1 до √8√n и вершина i сопоставляется вершине √8√n − i + 1, то эти пары вершин можно соединить непересекающимися путями внутри диска (по одной из форм теоремы Менгера для планарных графов). Однако суммарная длина этих путей превысила бы n, получили противоречие. Проведя некоторые дополнительные выкладки, они показали, применив похожие методы, что существует простой сепаратор-цикл размера, не превышающего (3/√2)√n, что примерно равно 2.12√n.
Джиджев и Венкатесан[8] позднее улучшили константу в теореме о простом сепараторе-цикле до 1.97√n. Их метод позволяет также искать простые сепараторы-циклы для графов с неотрицательными весами вершин с размером сепаратора, не превосходящим 2√n. Метод позволяет создавать сепараторы и с меньшим размером, правда, за счёт большей разницы в размерах частей разбиения. В 2-связном планарном графе, не являющемся максимальным, существует простой сепаратор-цикл с размером, пропорциональным евклидовой норме вектора длин граней, который можно найти за почти линейное время[9].
Сепараторы-циклы
Согласно теореме Кёбе — Андреева — Тёрстона об упаковке кругов любой планарный граф можно представить как упаковку кругов на плоскости с непересекающимися внутренними областями, так что две вершины графа смежны в том и только в том случае, когда соответствующие круги соприкасаются. Как показали Миллер, Тенг, Тёрстон и Вавасис[10], для таких упаковок существует окружность, которой касаются, либо лежат внутри неё, не более 3n/4 дисков, не более 3n/4 дисков лежат вне окружности, либо касаются её, и которая пересекает O(√n) дисков.
Для доказательства этого Миллер и др. использовал стереографическую проекцию для отображения упаковки на поверхность единичной трёхмерной сферы. При осторожном выборе проекции центр сферы можно поместить в среднюю точку[англ.] центров дисков поверхности, так что любая плоскость, проходящая через центр сферы, будет делить сферу на две полусферы, каждая из которых содержит или пересекает не более 3n/4 дисков. Если плоскость через центр выбирать случайно и равномерно, диск будет пресечён с вероятностью, пропорциональной радиусу. Таким образом, ожидаемое число пересечённых дисков пропорционально сумме радиусов дисков. Однако сумма квадратов радиусов пропорциональна полной площади дисков, что не превосходит площади поверхности единичной сферы, константы. Доводы, использующие неравенство Йенсена, показывают, что в случае ограниченности суммы квадратов n неотрицательных чисел константой, сумма самих чисел не превосходит O(√n). Таким образом, ожидание числа пересечений дисков случайной плоскостью равно O(√n) и существует плоскость, пересекающая не более этого количества дисков. Эта плоскость пересекает сферу по большому кругу, проекция которого обратно на плоскость даёт желаемые свойства. Пересечённые этой окружностью O(√n) дисков соответствуют вершинам сепаратора планарного графа, который отделяет вершины, диски которых лежат внутри окружности, от вершин, диски которых лежат вне окружности, и каждое из этих подмножеств имеет не более 3n/4 вершин[10][11].
Этот метод приводит к вероятностному алгоритму, который находит сепаратор за линейное время[10] и менее практичному детерминированному алгоритму с той же линейной временной границей[12]. При тщательном анализе этого алгоритма и использовании известных границ плотности упаковки кругов можно показать, что можно найти сепараторы, не превосходящие по размеру
Хотя этот улучшенный размер сепаратора приводит к разбиению графа на более неравные части, Шпильман и Тенг[14] утверждают, что метод даёт улучшенный множитель в оценке времени работы для вложенного разбиения по сравнению с сепаратором Алона, Сеймура и Томаса[1]. Размер сепараторов можно, на практике, улучшить, если использовать неравномерное распределение случайных секущих плоскостей[15].
Стереографическую проекцию в аргументации Миллера и др. можно избежать, если рассматривать наименьшую окружность, содержащую постоянную долю центров дисков, расширяя затем на величину, выбранную равномерно в отрезке [1,2]. Легко показать, как и у Миллера, что пересечённые диски такой окружностью образуют правильный сепаратор, а тогда математическое ожидание числа пересечений даст правильный результат. Правда, получающиеся константы будут несколько хуже[16].
Спектральное разбиение
Методы спектральной кластеризации, в которых вершины графа группируются по координатам собственных значений матриц, полученных из графа, давно использовались в качестве эвристических методов решения задач разбиения графа для непланарных графов[17][18]. Как показали Шпильман и Тенг[19], спектральную кластеризацию можно также использовать для альтернативного доказательства ослабленной формы теоремы планарного разбиения, применённую к планарным графам с ограниченной степенью вершин. В их методе вершины заданного планарного графа сортируются по второй координате собственных векторов матрицы Кирхгофа графа, и этот порядок разбивается в точке, минимизирующей отношение числа удаляемых рёбер к числу вершин меньшей части разбиения. Как они показали, любой планарный граф с ограниченной степенью вершин имеет такое разбиение, в котором указанное отношение равно O(1/√n). Хотя это разбиение может не быть сбалансированным, повторение разбиения большей из двух частей и объединение разрезов, полученных на каждой итерации, в конечном счёте, приводит к сбалансированному разбиению с O(√n) рёбрами. Конечные вершины этих рёбер образуют сепаратор размера (√n).
Рёберные сепараторы
Вариант теоремы о планарном разложении говорит о рёберных сепараторах, небольших множествах рёбер, образующих разрез между двумя подмножествами A и B вершин графа. Два множества, A и B должны иметь размер, не превосходящий постоянную долю числа n вершин графа (обычно требуется, чтобы размер обоих множеств не превосходил 2n/3), и каждая вершина графа принадлежала только A или B. Сепаратор состоит из рёбер, имеющих один конец в A, а другой — в B. Границы размера рёберного сепаратора зависят как от степени вершин графа, так и от числа вершин в графе — планарные графы, в которых одна вершина имеет степень n − 1, куда попадают колёса и звёзды, не имеет сепаратора с сублинейным числом рёбер, поскольку любой рёберный сепаратор должен был бы включать все рёбра, соединяющие вершину с высокой степенью с вершинами другой стороны разреза. Однако любой планарный граф с максимальной степенью Δ имеет рёберный сепаратор размера O(√(Δn))[20]
Простой сепаратор-цикл в двойственном графе планарного графа образует рёберный сепаратор исходного графа[6][9]. Применение теоремы о простом сепараторе-цикле Гацита и Миллера[9] к двойственному графу заданного планарного графа усиливает оценку O(√(Δn)) размера рёберного сепаратора, поскольку показывает, что любой планарный граф имеет рёберный сепаратор, размер которого пропорционален евклидовой норме вектора степеней вершин графа.
Пападимитроу и Сидери[21] описали алгоритм полиномиального времени работы для поиска рёберного сепаратора, который разбивает граф G на два подграфа равного размера, если G является порождённым подграфом графа решётки без дыр или с постоянным числом дыр. Тем не менее, они высказали гипотезу, что задача является NP-полной для случая произвольных планарных графов, и показали, что сложность задачи для графов решёток с произвольным числом дыр та же самая, что и для произвольных планарных графов.
В графе решётки √n × √n множество S, содержащее s < √n точек, может окружить подмножество не более чем из s(s − 1)/2 точек решётки и максимум достигается, если расположить S на диагональной линии поближе к углу решётки. Таким образом, чтобы образовать сепаратор, который отделяет по меньшей мере n/3 точек от решётки, s должно иметь размер по меньшей мере √(2n/3), что примерно 0.82√n.
Существуют планарные графы с n вершинами (для произвольно больших значений n), такие, что для любого сепаратора S, разбивающего оставшийся граф на подграфы с не более чем 2n/3 вершинами, S имеет по меньшей мере √(4π√3)√n вершин, примерно 1.56√n[2]. Построение использует аппроксимацию сферы выпуклым многогранником путём замещения каждой грани многогранника треугольной сеткой. Затем применяется изопериметрическая теорема для поверхности сферы.
Сепараторы можно скомбинировать в иерархию сепараторов планарного графа, рекурсивную декомпозицию на меньшие графы. Иерархию сепараторов можно представить в виде двоичного дерева, в котором корень представляет сам граф, а две дочерних вершины корня являются корнями порождённых подграфов подмножеств A и B рекурсивно построенной иерархии сепараторов.
Иерархия сепараторов этого типа образует базис для древесной декомпозиции заданного графа, в которой множество вершин ассоциированных с узлом дерева является объединением сепараторов на пути от этого узла до корня дерева. Поскольку размеры графов уменьшается на постоянный множитель на каждом уровне дерева, верхние границы размеров сепараторов также уменьшаются на постоянный множитель на каждом уровне, так что размеры сепараторов на этих путях складываются в геометрической прогрессии к O(√n). То есть сепаратор, образованный таким образом, имеет ширину O(√n) и это может быть использовано, чтобы показать, что любой планарный граф имеет древесную ширину O(√n).
Построение иерархии сепараторов прямо, проходя двоичное дерево от вершины вниз и применяя алгоритм линейного времени для поиска планарного сепаратора к каждому из порождённых подграфов, ассоциированных с каждым узлом двоичного дерева, заняло бы общее время O(n log n) . Однако можно построить всю иерархию сепараторов за линейное время, если использовать подход расслоения в ширину Липтона — Тарьяна и использовать при этом подходящие cтруктуры данных для осуществления каждого шага разбиения за подлинейное время[22].
Если сформировать иерархии на основе не сепараторов, а разъединений, в которых две дочерние вершины становятся корнями для рекурсивного построения иерархий сепараторов для двух подграфов G1 и G2 разъединения данного графа, то полная структура образует декомпозицию графа на ветви, а не древесную декомпозицию. Ширина любого разъединения в этой декомпозиции снова ограничена суммой размеров сепараторов на пути из любого узла в корень иерархии, так что любая декомпозиция, полученная таким образом, имеет ширину O(√n) и любой планарный граф имеет ширину ветвления O(√n). Хотя многие другие связанные задачи разбиения графов являются NP-полными даже для планарных графов, можно найти декомпозицию планарного графа на ветви с минимальной шириной за полиномиальное время[23].
Применяя методы Алона, Сеймура и Томаса[7] более прямо для построения декомпозиции графа на ветви, Фомин и Тиликос[24] показали, что любой планарный граф имеет ширину ветвления, не превосходящую 2.12√n, то есть с той же константой, что и для теоремы разбиения простыми сепараторами-циклами Алона Алон, Сеймура и Томаса. Поскольку древесная ширина любого графа не превосходит 3/2 ширины ветвления, это также показывает, что планарные графы имеют древесную ширину, не превосходящую 3.18√n.
Некоторые разреженные графы не имеют сепараторов подлинейного размера — в экспандере удаление константной доли вершин оставляет одну связную компоненту[4][25].
Возможно, самой ранней теоремой о разбиении является результат Жордана[26] о том, что любое дерево можно разбить на два поддерева с максимум n/2 вершин в каждом путём удаления единственной вершины[10]. В частности, вершина, минимизирующая размер максимальной компоненты, обладает этим свойством. Применяя ту же самую технику к древесной декомпозиции произвольного графа, можно показать, что любой граф имеет сепаратор с размером, не превосходящим его древесной ширины.
Если граф G не планарен, но может быть вложен в поверхность рода g, то он имеет сепаратор с O((gn)1/2) вершинами. Гильберт, Хатчинсон и Тарьян[27] доказали это с помощью подхода, близкого к подходу Липтона и Тарьяна[4]. Они группируют вершины графа по уровням поиска в ширину и находят два уровня, удаление которых оставляет не более одной большой компоненты, состоящей из малого числа уровней. Эта оставшаяся компонента может быть сделана планарной путём удаления некоторого числа путей поиска в ширину, пропорционального роду графа, после чего можно применить метод Липтона — Тарьяна к оставшемуся планарному графу. Результат получается из аккуратной балансировки размера удалённых двух уровней и числа уровней между ними. Если вложение графа задано, его сепаратор может быть найден за линейное время. Графы рода g имеют сепараторы размера O((gΔn)1/2)[28].
Графы ограниченного рода образуют пример семейства графов, замкнутых относительно операции взятия миноров, и теоремы о разбиении применимы к произвольным семействам графов, замкнутых относительно взятия минора. В частности, если семейство графов имеет запрещённый минор с h вершинами, то он имеет сепаратор с O(h√n) вершинами и такой сепаратор может быть найден за время O(n1 + ε) для любого ε > 0[29]
Метод сепараторов-циклов Миллера, Тенга, Тёрстона и Вавасиса[10] обобщается для графов пересечений любой системы d-мерных шаров, имеющих свойство, что любая точка поверхности покрывается шарами не более чем некоторое постоянное число k раз, для графов k-ближайших соседей в пространстве размерности d[10], и для графов, возникающих в сетках конечных элементов[30]. Сферические сепараторы, построенные таким образом, разбивают входной граф на подграфы, имеющие не более n(d + 1)/(d + 2) вершин. Размер сепараторов для графов k-кратных перекрытий шарами и графов k-ближайших соседей равен O(k1/dn1 − 1/d)[10].
Алгоритмы «Разделяй и властвуй»
Разбиения сепаратором можно использовать для построения эффективных алгоритмов «Разделяй и властвуй» для решения задач на планарных графах. Пример задачи, которая может быть решена таким подходом — поиск кратчайшего цикла во взвешенном планарном ориентированном графе. Можно это сделать следующим образом:
- Разбиваем заданный граф G на три подмножества S, A и B согласно теореме о планарном разбиении
- Рекурсивно ищем кратчайшие циклы в A и B
- Используем алгоритм Дейкстры для поиска для каждого s из S кратчайшего цикла через s в G.
- Возвращаем найденный кратчайший цикл в предыдущий шаг.
Время двух рекурсивных вызовов для A и B в этом алгоритме доминируется временем работы O(√n) алгоритма Дейкстры, так что данный алгоритм находит кратчайший цикл за время O(n3/2 log n).
Более быстрый алгоритм для той же задачи поиска кратчайшего цикла, работающий за время O(n log3n), дал Вульф-Нильсен[31]. Его алгоритм использует ту же структуру «разделяй и властвуй», основанную на сепараторах, но в качестве сепараторов использует простые сепараторы-циклы, а не произвольные сепараторы, так что вершины множества S принадлежат одной грани (для внутреннего графа и для внешнего графа относительно сепаратора). Затем он заменяет O(√n) отдельных вызовов алгоритма Дейкстры более утончёнными алгоритмами для поиска кратчайших путей из всех вершин одной грани планарного графа и комбинирования расстояний из двух подграфов. Для взвешенных, но неориентированных планарных графов, кратчайший цикл эквивалентен наименьшему разрезу в двойственном графе и может быть найдено за время O(n log log n)[32], и кратчайший цикл во взвешенном цикле неориентированном планарном графе (его обхват) может быть найден за время O(n)[33]. (Однако более быстрый алгоритм для невзвешенных графов не основан на теореме о разбиении.)
Фредериксон предложил в 1986 году другой быстрый алгоритм для кратчайшего пути из единственного источника путём использования теоремы о разбиении для планарных графов[34]. Алгоритм является улучшением алгоритма Дейкстры с итеративным поиском на аккуратно выбранном подмножестве вершин. Эта версия работает за время O(n √(log n)) на графе с n вершинами. Сепараторы используются для поиска деления графа, то есть его разбиения на два или более подмножеств, называемых областями. Говорят, что узел содержится в области, если некоторое ребро области инцидентно узлу. Узел, содержащийся в более чем одной области, называется граничным узлом областей, содержащих его. Метод использует понятие r-деления графа с n узлами, что соответствует делению графа на O(n/r) областей, каждая из которых содержит O(r) узлов, включая O(√r) граничных узлов. Фредериксон показал, что r-деление может быть найдено за время O(n log n) путём рекурсивного применения теоремы о разбиении.
Набросок алгоритма для решения задачи.
1. Предварительная подготовка. Разбиваем граф на аккуратно подобранные подмножества вершин и находим кратчайшие пути между всеми парами вершин в этих подмножествах, в которых промежуточные вершины пути не принадлежат подмножеству. На этой фазе нужно планарный граф G0 преобразовать в G, не имеющего вершин со степенью, большей 3. Из формулы Эйлера число вершин в получившемся графе будет n ≤ 6n0 −12, где n0 — число вершин в графе G0 . Эта фаза также обеспечивает следующие свойства подходящих r-делений. Подходящее r-деление планарного графа — это r-деление, такое, что
- каждая граничная вершина содержится не более чем в трёх областях
- любая несвязная область состоит из связных компонент, каждая из которых имеет общие граничные вершины с тем же набором из одной или двух связных областей.
2. Поиск
- Главная атака — находим кратчайшие расстояния от источника до всех вершин подмножества. Если вершина v в подмножестве закрыта (если минимальное расстояние не известно, вершина считается открытой, если известно — закрытой), d(w) должно быть обновлено для всех вершин w в подмножестве, для которых существует путь из v в w.
- Очистка — определяем кратчайшие расстояния до всех оставшихся вершин.
Хенцингер с соавторами расширили технику r-деления Фредериксона для алгоритма поиска кратчайшего пути из единственного источника в планарных графах с неотрицательными длинами рёбер и предложили алгоритм линейного времени[35]. Их метод обобщает понятие разделение Фредрексона для графа, так что теперь (r,s)-разбиение графа с n узлами становится разбиением на O(n/r) областей, каждая из которых содержит r{O(1)} узлов и максимум s граничных узлов. Если (r, s)-разбиение последовательно повторять для разбиения на более мелкие области, это называется рекурсивным делением. Алгоритм использует примерно log*n уровней деления. Рекурсивное деление представляется корневым деревом, листья которого помечены различными рёбрами графа G. Корень дерева представляет область, состоящую из всего графа G, дети корня представляют подобласти, на которые область разбивается. Каждый лист представляет в точности одно ребро.
Вложенное рассечение[англ.] — это основанная на сепараторах вариация подхода «разделяй и властвуй» для метода исключений Гаусса для решения разреженных симметричных систем линейных алгебраических уравнений с планарной структурой графа, какие возникают в методе конечных элементов. Метод использует поиск сепаратора для графа описания системы равенств, рекурсивно исключая переменные в двух подзадачах, отделённых друг от друга сепаратором, а затем исключаются переменные в сепараторе[36]. Заполненность этого метода (число ненулевых коэффициентов результирующего разложения Холецкого для матрицы) равна O(n log n)[37][38], что позволяет этому методу конкурировать с итеративными методами для тех же задач[36].
Кляйн, Мозес и Вейманнn[39] предложили работающий за время O(n log2 n) алгоритм с линейной памятью для поиска кратчайших расстояний от s для всех узлов ориентированного планарного графа с положительными и отрицательными длинами дуг, не содержащего отрицательных циклов. Их алгоритм использует сепараторы планарного графа для поиска жордановой кривой C, которая проходит через O(√n) узлов (но не через дуги) так, что от n/3 до 2n/3 узлов оказываются внутри (области, ограниченной замкнутой) кривой C. Узлы, через которые кривая C проходит, являются граничными узлами. Исходный граф G разбивается на два подграфа G0 и G1, отсекая планарное вложение вдоль кривой C и дублируя граничные узлы. Для i=0 и 1, в Gi граничные узлы лежат в одной грани Fi .
Обзор этого подхода дан ниже.
- Рекурсивный вызов — На первом шаге рекурсивно вычисляются расстояния от r в Gi для i=0, 1.
- Расстояния границ внутри части — Для каждого графа G i вычисляем все расстояния в Gi между граничными узлами. Это занимает O(n log n) времени.
- Расстояния до границ внутри части для одного источника — Кратчайший путь в G, проходящий вперёд и назад между G0 и G1 для вычисления расстояний в G от r до всех граничных узлов. Чередуя итерации, используем все расстояния между границами в $G0 и $G1 . Число итераций равно O(√n), так что общее время выполнения этого шага равно O(n α(n)), где α(n) — функция, обратная функции Аккермана.
- Расстояния внутри части для одного источника — используются расстояния, вычисленные на предыдущем шаге, вместе с вычислениями Дейкстры в модифицированной версии каждого Gi для вычисления расстояний в G от r до всех узлов. Этот шаг занимает O(n log n) времени.
- Пересчёт расстояний для одного источника — расстояния от r в G преобразуются в неотрицательные длины, и снова используется алгоритм Дейкстры лоя вычисления расстояний от s. Шаг требует O(n log n) времени.
Важной частью этого алгоритма является использование Функций Цены и Приведённых Длин. Для ориентированного графа G с длинами дуг ι(•) функция цены — это функция φ из узлов графа G в вещественные числа. Для дуги uv приведённая длина по отношению к φ равна ιφ(uv)=ι(uv) + φ(u) − φ(v). Допустимая функция цены — это функция, которая даёт неотрицательные приведённые длины на всех дугах графа G. Полезно преобразовать задачу поиска кратчайшего пути, имеющую как положительные длины дуг, так и отрицательные, в задачу с неотрицательными длинами, что позволит использовать алгоритм Дейкстры.
Основанная на сепараторах парадигма «разделяй и властвуй» используется также для разработки структур данных для алгоритмов на динамических графах[англ.][40][41] и локализации точки[англ.][42], алгоритмов триангуляции многоугольников[22], поиска кратчайших путей[43][44], для построения графов ближайших соседей[45] и аппроксимационных алгоритмов поиска максимального независимого множества на планарных графах[42].
Точное решение NP-трудных оптимизационных задач
При использовании динамического программирования на древесной декомпозиции или декомпозиции ветви для планарного графа, многие классы NP-трудных оптимизационных задач можно решить за время, экспоненциально зависящее от √n или √n log n. Например, границы такого вида известны для поиска максимальных независимых множеств, деревьев Штейнера, гамильтоновых циклов и для решения задачи коммивояжёра на планарных графах[46]. Подобные методы, использующие теоремы о разбиении геометрических графов, можно использовать для решения евклидовой задачи коммивояжёра и построения дерева Штейнера в тех же временных границах[47].
Для параметризованных[англ.] задач, допускающих параметрическую редукцию, сохраняющую планарность и сокращающую входной файл до ядра с размером, линейно зависящим от параметра, этот подход можно использовать для построения фиксированно-параметрически разрешимых[англ.] алгоритмов, время выполнения которых зависит полиномиально от размера входного графа и экспоненционально от √k, где k — параметр алгоритма. Например, границы времени выполнения этого вида известны для поиска вершинных покрытий и доминирующих множеств размера k[48][49].
Аппроксимационные алгоритмы
Липтон и Тарьян[42] заметили, что теорему о разбиении можно использовать, чтобы получить приближенные схемы полиномиального времени для NP-трудных оптимизационных задач на планарных графах, таких как нахождение максимального независимого множества. В частности, путём усечения иерархии сепараторов в подходящем месте можно найти сепаратор размера O(n/√log n), удаление которого разбивает граф на подграфы размера c log n для любой константы c. По теореме о четырёх красках, существует независимое множество размера, не меньшего n/4, так что удалённые узлы образуют незначительную долю максимального независимого множества, и максимальные независимые множества в оставшихся подграфах можно найти независимо за время, экспоненционально зависящее от их размера. Комбинируя этот подход с методами линейного времени построения иерархии сепараторов[22] с поиском в таблице для сокращения времени поиска независимых множеств в изоморфных подграфах, можно построить независимые множества, отличающиеся от оптимальных на множитель 1 − O(1/√log n), за линейное время. Однако для гарантированной эффективности, даже более близкой к 1, чем этот множитель, более поздний подход Бейкера (Baker 1994) (основанный на древесном разложении, а не на планарных сепараторах) обеспечивает лучший компромисс между временем и качеством аппроксимации.
Похожие схемы аппроксимации, основанные на построении сепараторов, используются для аппроксимации других трудных задач, таких как задача о вершинном покрытии[50][51]. Арора, Григни, Каргер, Кляйн и Волошин[52] использовали сепараторы другим способом для аппроксимации задачи коммивояжёра для метрики кратчайшего пути на взвешенных планарных графах. Их алгоритм использует динамическое программирование для поиска кратчайшего маршрута, который, на каждом уровне иерархии сепараторов, пересекает сепаратор ограниченное число раз. Они показали, что при увеличении границы числа пересечений маршруты, построенные таким образом, имеют длину, аппроксимирующую оптимальный маршрут.
Сжатие графа
Сепараторы используются как часть алгоритмов cжатия данных для представления планарных графов и других разделимых графов с использованием малого числа бит. Главный принцип этих алгоритмов — выбор числа k и повторное разбиение заданного планарного графа с помощью сепараторов на O(n/k) подграфов размера, не превосходящего k, с O(n/√k) вершинами в сепараторах. При подходящем выборе k (максимум пропорциональном логарифму числа n) число неизоморфных планарных подграфов с k вершинами существенно меньше числа подграфов в декомпозиции, так что графы могут быть сжаты путём построения таблицы всех возможных неизоморфных подграфов и представления каждого подграфа в декомпозиции индексом в таблице. Остаток графа, образованного вершинами сепаратора, может быть представлен явно или с помощью рекурсивной версии той же структуры данных. Используя этот метод, планарные графы и более ограниченные семейства планарных графов можно закодировать с помощью оптимального числа бит (с точки зрения теории информации) — если имеются графы Pn с n вершинами в семействе графов, то индивидуальный граф из семейства может быть представлен с помощью всего (1 + o(n))log2Pn бит[53]. Можно также построить представления этого типа, в которых можно проверить смежность вершин, определить степень вершины, и список соседей вершин за постоянное время (на запрос), путём расширения таблицы подграфов дополнительной информацией данными, соответствующими запросам[54][55].
Универсальные графы
Универсальный граф для семейства графов F — это граф, который содержит любой элемент семейства F в качестве подграфа. Сепараторы можно использовать, чтобы показать, что планарные графы с n вершинами имеют универсальный граф с n вершинами и O(n3/2) рёбрами[56].
Построение использует усиленную форму теоремы о разбиении, в которой размер трёх подмножеств вершин в разбиении не зависит о структуры графа — существует число c, величина которого на постоянный множитель больше √n, такое, что вершины любого планарного графа с n вершинами могут быть разбиты на подмножества A, S и B с отсутствием рёбер из A в B и с размерами |S| = c, |A| = |B| = (n − c)/2. Это можно показать с помощью применения обычной формы теоремы о разбиении повторно к полученным разбиениям графа, пока все компоненты разбиения не будут собраны в два подмножества, размер каждого из которых менее n/2 вершин, с последующим переносом вершин из этих подмножеств в сепаратор, пока он не будет иметь заданный размер.
Теперь эта теорема может быть использована для получения иерархии сепараторов для планарного графа с n вершинами, который снова не зависит от структуры графа — древесная декомпозиция, полученная из этой иерархии имеет ширину O(√n) и может быть использована для любого планарного графа. Множество всех пар вершин в этой древесной декомпозиции, в которых каждая из двух вершин принадлежит общему узлу древесной декомпозиции, образует тривиально совершенный граф с O(n3/2) вершинами, который содержит любой планарный граф с n вершинами в качестве подграфа. Аналогичное построение показывает, что планарные графы ограниченной степени имеют универсальные графы с O(n log n) рёбрами, где константа, спрятанная в обозначении O, зависит от степени графа. Любой универсальный граф для планарных графов (или даже для деревьев неограниченной степени) должен иметь Ω(n log n) рёбер, но остаётся неизвестным, является ли эта нижняя граница или верхняя граница O(n3/2) точными для универсальных графов произвольных планарных графов[56].
- Вершинный сепаратор
- Геометрический сепаратор[англ.]
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
