Теорема о плоском сепараторе

В теории графов теорема о плоском разделителе - это форма изопериметрического неравенства для плоских графов , в которой говорится, что любой плоский граф можно разбить на более мелкие части, удалив небольшое количество вершин. В частности, удаление вершин из -vertex графа (где вызывает большое обозначение O ) может секционировать граф на непересекающиеся подграфы , каждый из которых имеет не более вершин.${\ displaystyle O ({\ sqrt {n}})}$${\ displaystyle n}$${\ displaystyle O}$${\ displaystyle 2n / 3}$

Более слабая форма теоремы о разделителе с вершинами в разделителе вместо была первоначально доказана Унгаром (1951) , а форма с точной асимптотической оценкой размера разделителя была впервые доказана Липтоном и Тарьяном (1979) . С момента их работы теорема о сепараторе была перефразирована несколькими способами, константа в члене теоремы была улучшена и была расширена на некоторые классы неплоских графов.${\ Displaystyle О ({\ sqrt {n}} \ log ^ {3/2} п)}$${\ displaystyle O ({\ sqrt {n}})}$${\ displaystyle O ({\ sqrt {n}})}$

Повторное применение теоремы о разделителе создает иерархию разделителей, которая может принимать форму разложения по дереву или разложения по ветвям графа. Иерархии разделителей могут использоваться для разработки эффективных алгоритмов «разделяй и властвуй» для плоских графов, а динамическое программирование на этих иерархиях может использоваться для разработки алгоритмов экспоненциального времени и управляемых алгоритмов с фиксированными параметрами для решения NP-сложных задач оптимизации на этих графах. Иерархии разделителей также могут использоваться во вложенном разрезе , эффективном варианте исключения Гаусса для решения разреженных системы линейных уравнений, возникающие из методов конечных элементов .

Теория Bidimensionality из Demaine , Фомина, Hajiaghayi и Thilikos обобщающей и значительно расширяет применимость теоремы сепаратора для огромного множества задач минимизации на плоских графов и в более общем плане графики за исключением фиксированного несовершеннолетнего .

Формулировка теоремы [ править ]

Как правило , указываются, отделитель теорема утверждает , что в любом -vertex планарного графа , существует разбиение вершин на три множества , и , таким образом, что каждый из и имеет в большинстве вершин, имеет вершины, и есть нет ребер с одной конечной точкой внутрь и одной конечной точкой внутрь . Не требуется , чтобы или форма подключены подграфами из . называется разделителем для этого раздела.${\ displaystyle n}$${\ Displaystyle G = (V, E)}$${\ displaystyle G}$${\ displaystyle A}$${\ displaystyle S}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle 2n / 3}$${\ displaystyle S}$${\ displaystyle O ({\ sqrt {n}})}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$ ${\ displaystyle G}$${\ displaystyle S}$

Эквивалентная формулировка является то , что края любого -vertex плоского графа может быть подразделена на два ребро непересекающихся подграфов , и таким образом , что оба подграфы имеют по меньшей мере вершины и такие , что пересечение множеств вершин двух подграфов имеют вершины в Это. Такая перегородка называется разделением . ^[1] Если задано разделение, то пересечение множеств вершин образует разделитель, а вершины, принадлежащие одному подграфу, но не другому, образуют отдельные подмножества, каждое из которых имеет не более чем вершины. В другом направлении, если один дано разбиение на три группы , и${\ displaystyle n}$${\ displaystyle G}$${\ displaystyle G_ {1}}$${\ displaystyle G_ {2}}$${\ displaystyle n / 3}$${\ displaystyle O ({\ sqrt {n}})}$${\ displaystyle 2n / 3}$${\ displaystyle A}$${\ displaystyle S}$${\ displaystyle B}$которые удовлетворяют условиям теоремы о плоском разделителе, то можно сформировать разделение, в котором ребра с концом в принадлежат , ребра с концом в принадлежат , а остальные ребра (с обоими концами в ) разделены произвольно.${\ displaystyle A}$${\ displaystyle G_ {1}}$${\ displaystyle B}$${\ displaystyle G_ {2}}$${\ displaystyle S}$

Константа в формулировке теоремы о разделителе является произвольной и может быть заменена любым другим числом в открытом интервале без изменения формы теоремы: разбиение на более равные подмножества может быть получено из менее четного разбиения путем многократного разбиения большие наборы в неравномерном разделе и перегруппировке полученных связанных компонентов. ^[2]${\ displaystyle 2/3}$ ${\ Displaystyle (1 / 2,1)}$

Пример [ править ]

Рассмотрим сетку графа со строками и столбцами; количество вершин равно . Так , например, на рисунке, , , и . Если нечетное, есть один центральный ряд, в противном случае есть два ряда, одинаково близких к центру; аналогично, если нечетное, есть один центральный столбец, а в противном случае есть два столбца, одинаково близких к центру. Выбрав любую из этих центральных строк или столбцов и удалив их из графа, он разбивает граф на два меньших связанных подграфа и , каждый из которых имеет самое большее количество вершин. Если (как на рисунке), то выбор центрального столбца даст разделитель${\ displaystyle r}$${\ displaystyle c}$${\ displaystyle n}$${\ displaystyle rc}$${\ displaystyle r = 5}$${\ displaystyle c = 8}$${\ displaystyle n = rc = 40}$${\ displaystyle r}$${\ displaystyle c}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle B}$${\displaystyle n/2}$${\displaystyle r\leq c}$${\displaystyle S}$с вершинами, и аналогично, если тогда выбор центральной строки даст разделитель с не более чем вершинами. Таким образом, каждый сеточный граф имеет разделитель максимального размера , при удалении которого он разбивается на две связанные компоненты, каждая из которых имеет размер не более . ^[3]${\displaystyle r\leq {\sqrt {n}}}$${\displaystyle c\leq r}$${\displaystyle {\sqrt {n}}}$${\displaystyle S}$${\displaystyle {\sqrt {n}}}$${\displaystyle n/2}$

Теорема о плоском разделителе утверждает, что подобное разбиение может быть построено в любом плоском графе. Случай произвольных плоских графов отличается от случая сеточных графов тем, что разделитель имеет размер, но может быть больше, чем , оценка размера двух подмножеств и (в наиболее распространенных версиях теоремы), а не , и эти два подмножества и не обязательно образуют связанные подграфы.${\displaystyle O({\sqrt {n}})}$${\displaystyle {\sqrt {n}}}$${\displaystyle A}$${\displaystyle B}$${\displaystyle 2n/3}$${\displaystyle n/2}$${\displaystyle A}$${\displaystyle B}$

Конструкции [ править ]

Слои в ширину [ править ]

Липтон и Тарьян (1979) при необходимости дополняют данный плоский граф дополнительными ребрами, чтобы он стал максимально плоским (каждая грань в плоском вложении является треугольником). Затем они выполняют поиск в ширину , начиная с произвольной вершины , и разбивают вершины на уровни по их расстоянию от . Если это средний уровень (уровень таким образом, что число вершин на более высоких и более низких уровней являются не более ) , то должно быть уровни , и которые являются шаги выше и ниже , соответственно , и которые содержат вершины, соответственно, ибо в противном случае было бы больше чем вершины на уровнях около${\displaystyle v}$${\displaystyle v}$${\displaystyle l_{1}}$${\displaystyle n/2}$${\displaystyle l_{0}}$${\displaystyle l_{2}}$${\displaystyle O({\sqrt {n}})}$${\displaystyle l_{1}}$${\displaystyle O({\sqrt {n}})}$${\displaystyle n}$${\displaystyle l_{1}}$. Они показывают , что должно быть разделитель , образованное объединением и , на концах ребра в том , что не принадлежит к широте-первых дереву поиска и что лежит между двумя уровнями, а вершины на два поиске в ширине древовидные пути от конечных точек до уровня . Размер сконструированного таким образом разделителя не больше . Вершины разделителя и двух непересекающихся подграфов могут быть найдены за линейное время .${\displaystyle S}$${\displaystyle l_{0}}$${\displaystyle l_{2}}$${\displaystyle e}$${\displaystyle G}$${\displaystyle e}$${\displaystyle l_{0}}$${\displaystyle S}$${\displaystyle {\sqrt {8n}}\approx 2.83{\sqrt {n}}}$

Это доказательство теоремы о разделителе применимо также к взвешенным планарным графам, в которых каждая вершина имеет неотрицательную стоимость. Граф может быть разделена на три группы , и таким образом, что и каждый имеет максимум от общей стоимости и имеет вершины, без ребер из и . ^[4] Более тщательно анализируя аналогичную конструкцию разделителя, Джиджев (1982) показывает, что ограничение на размер может быть уменьшено до .${\displaystyle A}$${\displaystyle S}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle 2/3}$${\displaystyle S}$${\displaystyle O({\sqrt {n}})}$${\displaystyle A}$${\displaystyle B}$${\displaystyle S}$${\displaystyle {\sqrt {6n}}\approx 2.45{\sqrt {n}}}$

Holzer et al. (2009) предлагают упрощенную версию этого подхода: они увеличивают граф, чтобы он стал максимально плоским, и строят дерево поиска в ширину, как и раньше. Затем для каждого ребра , не являющегося частью дерева, они образуют цикл, объединяясь с путем дерева, который соединяет его конечные точки. Затем они используют в качестве разделителя вершины одного из этих циклов. Хотя этот подход не может гарантировать нахождение небольшого разделителя для плоских графов большого диаметра, их эксперименты показывают, что он превосходит методы расслоения в ширину Липтона – Тарьяна и Джиджева на многих типах плоских графов.${\displaystyle e}$${\displaystyle e}$

Простые разделители цикла [ править ]

Для графа, который уже является максимально планарным, можно показать более сильную конструкцию простого разделителя циклов , цикл небольшой длины, такой, что внутренняя и внешняя части цикла (в единственном плоском вложении графа) имеют по большинство вершин. Миллер (1986) доказывает это (с размером разделителя ), используя технику Липтона – Тарьяна для модифицированной версии поиска в ширину, в которой уровни поиска образуют простые циклы.${\displaystyle 2n/3}$${\displaystyle {\sqrt {8n}}}$

Алон, Сеймур и Томас (1994) доказывают существование простых разделителей циклов более прямо: они позволяют быть циклом не более чем из вершин, с не более чем вершинами снаружи , который образует как можно более равномерное разделение внутреннего и внешнего, и они показывают что эти предположения заставляют быть разделителем. В противном случае расстояния внутри должны равняться расстояниям в диске, окруженном (более короткий путь через внутреннюю часть диска будет составлять часть границы лучшего цикла). Кроме того, он должен иметь ровную длину , иначе его можно улучшить, заменив одно из его ребер двумя другими сторонами треугольника. Если вершины в пронумерованы (по часовой стрелке) от${\displaystyle C}$${\displaystyle {\sqrt {8n}}}$${\displaystyle 2n/3}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle {\sqrt {8n}}}$${\displaystyle C}$${\displaystyle 1}$к , а вершина совпадает с вершиной , то эти согласованные пары могут быть соединены путями, не пересекающимися с вершинами, внутри диска в соответствии с формой теоремы Менгера для плоских графов. Однако общая длина этих путей обязательно будет больше , противоречие. С помощью некоторой дополнительной работы они аналогичным методом показывают, что существует простой разделитель циклов, размер которого не превышает максимума .${\displaystyle {\sqrt {8n}}}$${\displaystyle i}$${\displaystyle {\sqrt {8n}}-i+1}$${\displaystyle n}$${\displaystyle {\sqrt {9n/2}}\approx 2.12{\sqrt {n}}}$

Джиджев и Венкатесан (1997) улучшили постоянный множитель в теореме о разделителе простых циклов до . Их метод также может находить простые разделители циклов для графов с неотрицательными весами вершин, с максимальным размером разделителя , и может генерировать разделители с меньшим размером за счет более неравномерного разделения графа. В двусвязных плоских графах, которые не являются максимальными, существуют простые разделители циклов с размером, пропорциональным евклидовой норме вектора длин граней, которые можно найти за почти линейное время. ^[5]${\displaystyle 1.97{\sqrt {n}}}$${\displaystyle 2{\sqrt {n}}}$

Разделители кругов [ править ]

Согласно теореме Кебе-Андреева-Терстона об упаковке кругов , любой плоский граф может быть представлен упаковкой круговых дисков на плоскости с непересекающимися внутренностями, так что две вершины в графе смежны тогда и только тогда, когда соответствующая пара дисков касаются друг друга. Как Miller et al. (1997) показывают, что для такой упаковки существует круг, в котором не более дисков соприкасаются или внутри него, не более чем соприкасаются диски или снаружи, и который пересекает диски.${\displaystyle 3n/4}$${\displaystyle 3n/4}$${\displaystyle O({\sqrt {n}})}$

Чтобы доказать это, Миллер и др. используйте стереографическую проекцию, чтобы отобразить упаковку на поверхности единичной сферы в трех измерениях. Путем тщательного выбора проекции центр сферы может быть превращен в центральную точку диска с центрами на его поверхности, так что любая плоскость, проходящая через центр сферы, разделяет ее на два полупространства, каждое из которых содержит или пересекает не более${\displaystyle 3n/4}$дисков. Если плоскость, проходящая через центр, выбрана равномерно случайным образом, диск будет пересечен с вероятностью, пропорциональной его радиусу. Следовательно, ожидаемое количество пересекаемых дисков пропорционально сумме радиусов дисков. Однако сумма квадратов радиусов пропорциональна общей площади дисков, которая является постоянной величиной не более полной площади поверхности единичной сферы. Аргумент, связанный с неравенством Дженсена, показывает, что, когда сумма квадратов неотрицательных действительных чисел ограничена константой, сумма самих чисел равна . Следовательно, ожидаемое количество дисков, пересекаемых случайной плоскостью, равно, и существует плоскость, которая пересекает самое большее количество дисков. Эта плоскость пересекает сферу по${\displaystyle n}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$большой круг , который возвращается в круг на плоскости с желаемыми свойствами. Эти диски , пересекаемые эта окружность соответствует вершинам плоского графа сепаратора , который разделяет вершины, диски внутри круга из вершин , чьи диски находятся за пределами окружности, причем в большинстве вершин в каждом из этих двух подмножеств. ^[6]${\displaystyle O({\sqrt {n}})}$${\displaystyle 3n/4}$

Этот метод приводит к рандомизированному алгоритму , который находит такой разделитель линейного времени , ^[7] и менее практичный детерминированный алгоритм с тем же линейным временем связаны. ^[8] Анализируя этот алгоритм тщательно , используя известные оценки на плотности упаковки из окружности упаковки , можно показать , чтобы найти сепараторы размера не более ^[9]

Хотя эта улучшенная граница размера разделителя достигается за счет более неравномерного разбиения графа, Spielman & Teng (1996) утверждают, что она обеспечивает улучшенный постоянный коэффициент во временных рамках для вложенного рассечения по сравнению с разделителями Alon, Seymour & Томас (1990) . Размер производимых разделителей может быть дополнительно улучшен на практике за счет использования неравномерного распределения для произвольных плоскостей резания. ^[10]

Стереографическая проекция в Miller et al. Аргументации можно избежать, рассмотрев наименьший круг, содержащий постоянную долю центров дисков, а затем расширив его на константу, выбранную равномерно в диапазоне . Как и у Миллера и др., Диски, пересекающие расширенный круг, образуют допустимый разделитель, и, как ожидается, разделитель имеет правильный размер. Полученные константы несколько хуже. ^[11]${\displaystyle [1,2]}$

Спектральное разделение [ править ]

Спектральные кластерные методы, в которых вершина графа сгруппированы в зависимости от координат собственных векторов из матриц , полученных из графика, уже давно используются в качестве эвристики для графа разбиения задач для неплоских графов. ^[12] Как показывают Spielman & Teng (2007) , спектральная кластеризация также может использоваться для получения альтернативного доказательства ослабленной формы теоремы о планарном сепараторе, которая применяется к планарным графам с ограниченной степенью. В своем методе, вершины данного плоского графа сортируются по второй координате собственных векторов в лапласиана матрицыграфа, и этот отсортированный порядок разбивается в точке, которая минимизирует отношение количества ребер, вырезанных разбиением, к числу вершин на меньшей стороне разбиения. Как они показывают, каждый плоский граф ограниченной степени имеет такое разбиение, в котором отношение равно . Хотя это разделение может не быть сбалансированным, повторение разделения в пределах большей из двух сторон и объединение разрезов, образованных при каждом повторении, в конечном итоге приведет к сбалансированному разделению с краями. Концы этих ребер образуют разделитель размера .${\displaystyle O(1/{\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$

Разделители краев [ править ]

Вариант теоремы о плоском разделителе включает разделители ребер , небольшие наборы ребер, образующие разрез между двумя подмножествами и вершинами графа. Каждый из двух наборов и должен иметь размер не более постоянной доли от числа вершин графа (обычно оба набора имеют размер не более ), и каждая вершина графа принадлежит ровно одному из и . Разделитель состоит из ребер, которые имеют одну конечную точку внутри и одну конечную точку внутри . Границы размера разделителя ребер включают степень вершин, а также количество вершин в графе: плоские графы, в которых одна вершина имеет степень${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n}$${\displaystyle 2n/3}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n-1}$, В том числе колес графиков и звездных графиков , не имеет краев сепаратора с сублинейным числом ребер, потому что любая кромкой сепаратор должен включать в себя все ребра , соединяющие высокую вершину степени , до вершин на другой стороне разреза. Однако каждый плоский граф с максимальной степенью имеет разделитель ребер размера . ^[13]${\displaystyle \Delta }$${\displaystyle O({\sqrt {\Delta n}})}$

Простой разделитель циклов в двойственном графе планарного графа образует разделитель ребер в исходном графе. ^[14] Применение теоремы о простом разделителе циклов Газита и Миллера (1990) к двойственному графу данного плоского графа усиливает оценку размера разделителя ребер, показывая, что каждый плоский граф имеет разделитель ребер, размер которого пропорционален евклидова норма его вектора степеней вершин.${\displaystyle O({\sqrt {\Delta n}})}$

Пападимитриу и Сидери (1996) описывают алгоритм полиномиального времени для поиска наименьшего разделителя краев, который разбивает граф на два подграфа равного размера, когда это индуцированный подграф сеточного графа без отверстий или с постоянным количеством отверстий. Однако они предполагают, что проблема является NP-полной для произвольных плоских графов, и показывают, что сложность проблемы такая же для сеточных графов с произвольным количеством отверстий, как и для произвольных плоских графов.${\displaystyle G}$${\displaystyle G}$

Нижние границы [ править ]

В сетке графика, набор из точек можно заключить подмножество в большинстве точек сетки, где максимум достигается путем расположения в диагональной линии вблизи угла сетки. Следовательно, чтобы сформировать разделитель, который отделяет хотя бы точки от оставшейся сетки, должен быть как минимум .${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$${\displaystyle S}$${\displaystyle s<{\sqrt {n}}}$${\displaystyle s(s-1)/2}$${\displaystyle S}$${\displaystyle n/3}$${\displaystyle s}$${\displaystyle {\sqrt {2n/3}}\approx 0.82{\sqrt {n}}}$

Существуют плоские графы с -вершинниками (для сколь угодно больших значений ) такие, что для каждого разделителя , разбивающего оставшийся граф на подграфы не более чем с вершинами, должно быть не менее . ^[2] Конструкция включает в себя аппроксимирующую сферу посредством выпуклого многогранника , заменяя каждый из граней многогранника с помощью треугольной сетки, и применяя изопериметрические теоремы для поверхности сферы.${\displaystyle n}$${\displaystyle n}$${\displaystyle S}$${\displaystyle 2n/3}$${\displaystyle S}$${\displaystyle {\sqrt {4\pi n/{\sqrt {27}}}}\approx 1.56{\sqrt {n}}}$

Иерархии разделителей [ править ]

Разделители могут быть объединены в иерархию разделителей плоского графа, рекурсивное разложение на более мелкие графы. Иерархия разделителей может быть представлена двоичным деревом, в котором корневой узел представляет сам заданный граф, а два дочерних элемента корня являются корнями рекурсивно построенных иерархий разделителей для индуцированных подграфов, сформированных из двух подмножеств и разделителя.${\displaystyle A}$${\displaystyle B}$

Иерархия разделителей этого типа образует основу для древовидной декомпозиции данного графа, в которой набор вершин, связанных с каждым узлом дерева, является объединением разделителей на пути от этого узла к корню дерева. Поскольку размеры графов уменьшаются на постоянный коэффициент на каждом уровне дерева, верхние границы размеров разделителей также уменьшаются на постоянный коэффициент на каждом уровне, поэтому размеры разделителей на этих путях складываются в геометрическая прогрессия с . То есть сформированный таким образом разделитель имеет ширину и может использоваться, чтобы показать, что каждый планарный граф имеет ширину дерева .${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Непосредственное построение иерархии разделителей путем обхода двоичного дерева сверху вниз и применения алгоритма планарного разделителя с линейным временем к каждому из индуцированных подграфов, связанных с каждым узлом двоичного дерева, потребует всего времени. Тем не менее, можно построить всю иерархию разделителей за линейное время, используя подход Липтона – Тарьяна с расслоением в ширину и используя соответствующие структуры данных для выполнения каждого шага разделения в сублинейное время. ^[15]${\displaystyle O(n\log n)}$

Если один формирует связанный тип иерархии на основе разделения вместо разделителей, в котором два дочерних узла корневого узла являются корнями рекурсивно построенных иерархий для двух подграфов и разделения данного графа, тогда общая структура образует ветвь -разложение вместо разложения по дереву. Ширина любого разделения в этом разложении, опять же, ограничена суммой размеров разделителей на пути от любого узла к корню иерархии, поэтому любое разложение ветвей, сформированное таким образом, имеет ширину и любой планарный граф. имеет пропускную способность . Хотя многие другие связанные проблемы разбиения графа являются NP-полными${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$даже для плоских графов можно найти разложение ветвей минимальной ширины плоского графа за полиномиальное время. ^[16]

Применяя методы Алона, Сеймура и Томаса (1994) более непосредственно к построению разложений по ветвям , Фомин и Тиликос (2006a) показывают, что каждый плоский граф имеет ширину ветвления не более , с той же константой, что и в простом разделителе циклов. Теорема Алона и др. Поскольку ширина дерева любого графа не превышает ширины его ветвления, это также показывает, что планарные графы имеют не больше ширины дерева .${\displaystyle 2.12{\sqrt {n}}}$${\displaystyle 3/2}$${\displaystyle 3.18{\sqrt {n}}}$

Другие классы графиков [ править ]

Некоторые разреженные графы не имеют разделителей сублинейного размера: в графе-расширителе при удалении до постоянной части вершин остается только один компонент связности. ^[17]

Возможно, самая ранняя известная теорема о разделителе является результатом Джордана (1869), согласно которому любое дерево может быть разбито на поддеревья не более чем с вершинами каждое путем удаления одной вершины. ^[7] В частности, вершина, которая минимизирует максимальный размер компонента, обладает этим свойством, поскольку в противном случае ее сосед в уникальном большом поддереве сформировал бы еще лучшее разделение. Применяя ту же технику к древовидной декомпозиции произвольного графа, можно показать, что любой граф имеет разделитель размера, не более равного его ширине дерева .${\displaystyle n/2}$

Если граф не плоский, но может быть вложен на поверхность рода , то он имеет разделитель с вершинами. Гилберт, Хатчинсон и Тарджан (1984) доказывают это, используя подход, аналогичный подходу Липтона и Тарьяна (1979).${\displaystyle G}$ ${\displaystyle g}$${\displaystyle O({\sqrt {gn}})}$. Они группируют вершины графа на уровни в ширину и находят два уровня, при удалении которых остается не более одного большого компонента, состоящего из небольшого числа уровней. Этот оставшийся компонент можно сделать плоским, удалив ряд путей в ширину, пропорциональных роду, после чего к оставшемуся планарному графу можно применить метод Липтона – Тарьяна. Результат следует из тщательного уравновешивания размера удаляемых двух уровней с количеством уровней между ними. Если вложение графа задано как часть ввода, его разделитель может быть найден за линейное время . Графы рода также имеют граничные разделители размера . ^[18]${\displaystyle g}$${\displaystyle O({\sqrt {g\Delta n}})}$

Графы ограниченного рода образуют пример семейства графов, замкнутых относительно операции взятия миноров , а теоремы о разделителях также применимы к произвольным семействам минорных замкнутых графов. В частности, если в семействе графов есть запрещенный минор с вершинами, то в нем есть разделитель с вершинами, и такой разделитель можно найти вовремя для любого . ^[19]${\displaystyle h}$${\displaystyle O(h{\sqrt {n}})}$${\displaystyle O(n^{1+\varepsilon })}$${\displaystyle \varepsilon >0}$

Метод кругового разделителя Миллера и др. (1997) обобщает до пересечения графиков любой системы n - мерных шаров с тем свойством , что любая точка в пространстве покрыта не более чем на некоторое постоянное число шаров, чтобы - ближайшие соседи график в размерах, ^[7] и графики возникающие из сеток конечных элементов . ^[20] Сферы-разделители, построенные таким образом, разбивают входной граф на подграфы не более чем с вершинами. Размер разделителей для графов -сложных пересечений шаров и для графов- ближайших соседей составляет . ^[7]${\displaystyle d}$${\displaystyle k}$${\displaystyle k}$${\displaystyle d}$${\displaystyle n(d+1)/(d+2)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle O(k^{1/d}n^{1-1/d})}$

Приложения [ править ]

Алгоритмы «разделяй и властвуй» [ править ]

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

• Partition данного графа на три подмножества , , в соответствии с плоской Сепаратор теоремы${\displaystyle G}$${\displaystyle S}$${\displaystyle A}$${\displaystyle B}$
• Рекурсивный поиск кратчайших циклов в и${\displaystyle A}$${\displaystyle B}$
• Воспользуйтесь алгоритмом Дейкстры, чтобы найти для каждой вершины в вершине кратчайший цикл через точку в .${\displaystyle s}$${\displaystyle S}$${\displaystyle s}$${\displaystyle G}$
• Вернуть самый короткий из циклов, найденных вышеупомянутыми шагами.

Время для двух рекурсивных вызовов и в этом алгоритме определяется временем выполнения вызовов алгоритма Дейкстры, поэтому этот алгоритм находит самый короткий цикл во времени.${\displaystyle A}$${\displaystyle B}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n^{3/2}\log n)}$

Более быстрый алгоритм решения той же задачи наикратчайшего цикла, работающий во времени , был дан Wulff-Nilsen (2009) . Его алгоритм использует ту же структуру «разделяй и властвуй» на основе разделителей, но использует простые разделители циклов, а не произвольные разделители, так что вершины принадлежат одной грани графов внутри и вне разделителя циклов. Затем он заменяет отдельные вызовы алгоритма Дейкстры более сложными алгоритмами, чтобы найти кратчайшие пути от всех вершин на одной грани плоского графа и объединить расстояния от двух подграфов. Для взвешенных, но неориентированных плоских графов кратчайший цикл эквивалентен минимальному разрезу в двойном графе и может быть найден за время,${\displaystyle O(n\log ^{3}n)}$${\displaystyle S}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n\log \log n)}$^[21] и кратчайший цикл в невзвешенном неориентированном плоском графе (его обхват ) может быть найден во времени. ^[22] (Однако более быстрый алгоритм для невзвешенных графов не основан на теореме о разделителе.)${\displaystyle O(n)}$

Фредериксон предложил другой более быстрый алгоритм поиска кратчайших путей с одним источником, реализовав теорему о разделителе в плоских графах. ^[23] Это усовершенствование алгоритма Дейкстры с итеративным поиском по тщательно отобранному подмножеству вершин. Эта версия требует времени в графе вершины. Разделители используются, чтобы найти разделение графа, то есть разделение набора ребер на два или более подмножества, называемых регионами. Говорят, что узел содержится в области, если некоторый край области инцидентен узлу. Узел, содержащийся в более чем одной области, называется граничным узлом областей, в которых он находится. Метод использует понятие -division из в -node графа , который представляет собой график , деление на${\displaystyle O(n{\sqrt {\log n}})}$${\displaystyle n}$${\displaystyle r}$${\displaystyle n}$${\displaystyle O(n/r)}$области, каждая из которых содержит узлы, включая граничные узлы. Фредериксон показал, что -разбиение может быть найдено во времени с помощью рекурсивного применения теоремы о разделителе.${\displaystyle O(r)}$${\displaystyle O({\sqrt {r}})}$${\displaystyle r}$${\displaystyle O(n\log n)}$

Набросок его алгоритма решения проблемы выглядит следующим образом.

1. Фаза предварительной обработки: разделите граф на тщательно отобранные подмножества вершин и определите кратчайшие пути между всеми парами вершин в этих подмножествах, где промежуточные вершины на этом пути не входят в подмножество. Эта фаза требует преобразования плоского графа , в котором нет вершин со степенью выше трех. Из следствия формулы Эйлера количество вершин в получившемся графе будет , где - количество вершин в . Эта фаза также обеспечивает следующие свойства подходящего -разбиения. Подходящим -разбиением плоского графа называется -разбиение такое, что${\displaystyle G_{0}}$${\displaystyle G}$${\displaystyle n\leq 6n_{0}-12}$${\displaystyle n_{0}}$${\displaystyle G_{0}}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$
   • каждая граничная вершина содержится не более чем в трех областях, и
   • любая несвязная область состоит из компонентов связности, граничные вершины которых совпадают с одним и тем же набором из одной или двух связанных областей.
2. Фаза поиска:
   • Основная тяга: найдите кратчайшие расстояния от источника до каждой вершины в подмножестве. Когда вершина в подмножестве закрывается, предварительное расстояние должно быть обновлено для всех вершин в подмножестве, чтобы существовал путь от до .${\displaystyle v}$${\displaystyle d(w)}$${\displaystyle w}$${\displaystyle v}$${\displaystyle w}$
   • Зачистка: определите кратчайшие расстояния до каждой оставшейся вершины.

Henzinger et al. расширенный метод -разбиения Фредериксона для алгоритма кратчайшего пути с одним источником в планарных графах для неотрицательных длин ребер и предложен алгоритм линейного времени . ^[24] Их метод обобщает понятие Фредериксона граф-делений таким образом, что теперь -division из -node графа является разделение на области, каждая из которых содержит узлы, каждый из которых имеет в большинстве граничных узлов. Если -разбиение многократно делится на более мелкие области, это называется рекурсивным делением. В этом алгоритме используются приблизительные уровни делений, где обозначает повторную логарифмическую функцию. Рекурсивное деление представлено${\displaystyle r}$${\displaystyle (r,s)}$${\displaystyle n}$${\displaystyle O(n/r)}$${\displaystyle r^{O(1)}}$${\displaystyle s}$${\displaystyle (r,s)}$${\displaystyle \log ^{*}n}$${\displaystyle \log ^{*}}$укоренившееся дерево , листья которого помечены четкими краями . Корень дерева представляет собой область, состоящую из всех , дочерние элементы корня представляют собой подобласти, на которые эта область разделена, и так далее. Каждый лист (атомная область) представляет собой область, содержащую ровно одно ребро.${\displaystyle G}$${\displaystyle G}$

Вложенное рассечение - это вариация метода исключения Гаусса, основанная на разделении и подчинении, для решения разреженных симметричных систем линейных уравнений с плоской структурой графа, таких как системы, возникающие из метода конечных элементов . Он включает в себя поиск разделителя для графа, описывающего систему уравнений, рекурсивное удаление переменных в двух подзадачах, отделенных друг от друга разделителем, а затем удаление переменных в разделителе. ^[25] Наполнитель в этом методе (число ненулевых коэффициентов в результате разложения Холецкой матрицы) является , ^[26]${\displaystyle O(n\log n)}$позволяя этому методу быть конкурентоспособным с итерационными методами решения тех же проблем. ^[25]

Клейн, Мозес и Вейманн ^[27] предложили алгоритм линейного пространства с временным интервалом для нахождения кратчайшего пути от исходной вершины до всех других вершин для ориентированного плоского графа с положительной и отрицательной длинами дуги, не содержащего отрицательных циклов. Их алгоритм использует плоский граф разделители , чтобы найти кривой Жордан , которая проходит через узлы (и нет дуг) такое , что между и узлы заключены . Узлы, через которые проходят проходы, являются граничными узлами. Исходный граф разделяется на два подграфа и путем разрезания плоского вложения вдоль и дублирования граничных узлов. Граничные узлы в каждом графе${\displaystyle O(n\log ^{2}n)}$${\displaystyle s}$ ${\displaystyle C}$${\displaystyle O({\sqrt {n}})}$${\displaystyle n/3}$${\displaystyle 2n/3}$${\displaystyle C}$${\displaystyle C}$${\displaystyle G}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$${\displaystyle C}$${\displaystyle G_{i}}$лежат на границе одного лица .${\displaystyle F_{i}}$

Обзор их подхода приведен ниже.

• Рекурсивный вызов: на первом этапе рекурсивно вычисляются расстояния внутри каждого графа .${\displaystyle r}$${\displaystyle G_{i}}$
• Внутричастные границы-расстояния: для каждого графа вычислить все расстояния между граничными узлами. На это нужно время.${\displaystyle G_{i}}$${\displaystyle G_{i}}$${\displaystyle O(n\log n)}$
• Граничные расстояния между частями из одного источника: кратчайший путь проходит взад и вперед между и для вычисления расстояний от до всех граничных узлов. При чередовании итераций используются все-границы-расстояния в и . Число итераций равно , а общее время для этого этапа - где - обратная функция Аккермана .${\displaystyle G}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$${\displaystyle G}$${\displaystyle r}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n\alpha (n))}$${\displaystyle \alpha (n)}$
• Расстояния между частями от одного источника: Расстояния, вычисленные на предыдущих этапах, используются вместе с вычислением Дейкстры в модифицированной версии каждого G _i  для вычисления расстояний от до всех узлов. Этот этап требует времени.${\displaystyle G}$${\displaystyle r}$${\displaystyle O(n\log n)}$
• Корректировка расстояний от одного источника: расстояния от in преобразуются в неотрицательные длины, и снова алгоритм Дейкстры используется для вычисления расстояний от . Этот этап требует времени.${\displaystyle r}$${\displaystyle G}$${\displaystyle s}$${\displaystyle O(n\log n)}$

Важной частью этого алгоритма является использование функций цены и уменьшенных длин. Для ориентированного графа с длинами дуг функция цены представляет собой функцию от узлов до действительных чисел . Для дуги приведенная длина по отношению к составляет . Возможная функция цены - это функция цены, которая индуцирует неотрицательные уменьшенные длины на всех дугах . Это полезно для преобразования задачи поиска кратчайшего пути, включающей положительные и отрицательные длины, в задачу, включающую только неотрицательные длины, которая затем может быть решена с использованием алгоритма Дейкстры.${\displaystyle G}$${\displaystyle \ell (uv)}$${\displaystyle \varphi }$${\displaystyle G}$${\displaystyle uv}$${\displaystyle \varphi }$${\displaystyle \ell _{\varphi }(uv)=\ell (uv)+\varphi (u)-\varphi (v)}$${\displaystyle G}$

Сепаратор на основе разделяй и властвуй парадигма была также использована для проектирования структур данных для алгоритмов динамического графа ^[28] и положения точки , ^[29] алгоритмы для многоугольника триангуляции , ^[15] кратчайшие пути , ^[30] и строительство ближайших соседних графов , ^[31] и алгоритмы приближения для максимального независимого множества плоского графа. ^[29]

Точное решение NP-сложных задач оптимизации [ править ]

Используя динамическое программирование на древовидной декомпозиции или ветвящейся декомпозиции плоского графа, многие NP-трудные задачи оптимизации могут быть решены с экспоненциальным временем в или . Например, оценки такого вида известны для нахождения максимально независимых множеств , деревьев Штейнера и гамильтоновых циклов , а также для решения задачи коммивояжера на плоских графах. ^[32] Подобные методы, использующие теоремы о разделителях для геометрических графов, могут быть использованы для решения евклидовой задачи коммивояжера и задач построения дерева Штейнера с оценками времени одного вида.${\displaystyle {\sqrt {n}}}$${\displaystyle {\sqrt {n}}\log n}$^[33]

Для параметризованных задач, допускающих ядризацию, которая сохраняет планарность и сокращает входной граф до ядра размера, линейного по входному параметру, этот подход может использоваться для разработки управляемых алгоритмов с фиксированными параметрами , время работы которых полиномиально зависит от размера входной граф и экспоненциально на , где - параметр алгоритма. Например, временные границы этой формы известны для нахождения вершинных покрытий и доминирующих наборов размеров . ^[34]${\displaystyle {\sqrt {k}}}$${\displaystyle k}$${\displaystyle k}$

Алгоритмы аппроксимации [ править ]

Липтон и Тарьян (1980) заметили, что теорема о разделителе может быть использована для получения схем аппроксимации с полиномиальным временем для NP-сложных задач оптимизации на плоских графах, таких как поиск максимального независимого множества . В частности, усекая иерархию разделителей на соответствующем уровне, можно найти разделитель размера, удаление которого разбивает граф на подграфы максимального размера для любой константы . По теореме о четырех цветах существует независимое множество размером не менее${\displaystyle O(n/{\sqrt {\log n}})}$${\displaystyle c\log n}$${\displaystyle c}$${\displaystyle n/4}$, поэтому удаленные узлы составляют незначительную часть максимального независимого множества, а максимальные независимые множества в оставшихся подграфах могут быть найдены независимо во времени экспоненциально по их размеру. Комбинируя этот подход с более поздними методами линейного времени для построения иерархии разделителей ^[15] и с поиском в таблице для разделения вычислений независимых множеств между изоморфными подграфами, можно создать независимые наборы размера с коэффициентом оптимальности в линейное время. Однако для коэффициентов аппроксимации, даже более близких к единице, чем этот коэффициент, более поздний подход Бейкера (1994) (основанный на древовидной декомпозиции, но не на плоских разделителях) обеспечивает лучший компромисс между временем и качеством аппроксимации.${\displaystyle 1-1/{\sqrt {\log n}}}$

Подобные схемы аппроксимации на основе разделителей также использовались для аппроксимации других сложных задач, таких как вершинное покрытие . ^[35] Arora et al. (1998) используют разделители по-другому, чтобы аппроксимировать задачу коммивояжера для метрики кратчайшего пути на взвешенных плоских графах; их алгоритм использует динамическое программирование для поиска кратчайшего маршрута, который на каждом уровне иерархии разделителей пересекает разделитель ограниченное количество раз, и они показывают, что по мере увеличения границы пересечения построенные таким образом маршруты имеют длину, приближающуюся к оптимальной. тур.

Сжатие графика [ править ]

Разделители использовались как часть алгоритмов сжатия данных для представления плоских графов и других разделяемых графов с использованием небольшого количества битов. Основной принцип этих алгоритмов заключается в выборе числа и многократном разбиении данного плоского графа с помощью разделителей на подграфы размера не более , с вершинами в разделителях. При соответствующем выборе (при наиболее пропорциональном логарифм от ) чисел неизоморфны${\displaystyle k}$${\displaystyle O(n/k)}$${\displaystyle k}$${\displaystyle O(n/{\sqrt {k}})}$${\displaystyle k}$${\displaystyle n}$ ${\displaystyle k}$-вершинных плоских подграфов значительно меньше, чем количество подграфов в разложении, поэтому граф можно сжать, построив таблицу всех возможных неизоморфных подграфов и представив каждый подграф в разложении разделителя по его индексу в таблице. Остальная часть графа, образованная вершинами разделителя, может быть представлена ​​явно или с использованием рекурсивной версии той же структуры данных. Используя этот метод, планарные графы и многие другие ограниченные семейства графов могут быть закодированы с использованием количества битов, которое является оптимальным с теоретической точки зрения : если в семействе графов есть графы с вершинами, то отдельный граф в семействе могут быть представлены только битами. ^[36]${\displaystyle P_{n}}$ ${\displaystyle n}$${\displaystyle (1+o(1))\log _{2}P_{n}}$Также возможно построить представления этого типа, в которых можно проверять смежность между вершинами, определять степень вершины и составлять список соседей вершин за постоянное время для каждого запроса, дополняя таблицу подграфов дополнительной табличной информацией, представляющей ответы на запросы. ^[37]

Универсальные графики [ править ]

Универсальный график для семейства графов представляет собой график , который содержит каждый член как подграфы. С помощью разделителей можно показать, что планарные графы -вершины имеют универсальные графы с вершинами и ребрами. ^[38]${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle O(n^{3/2})}$

Конструкция включает усиленную форму теоремы о разделителе, в которой размер трех подмножеств вершин в разделителе не зависит от структуры графа: существует число , величина которого не превышает константы раз , такое, что вершины плоского графа с каждой вершиной можно разделить на подмножества , и , без ребер из в , с и с . Это можно показать, используя обычную форму теоремы о разделителе несколько раз для разбиения графа до тех пор, пока все компоненты разбиения не могут быть организованы в два подмножества с числом вершин меньше , а затем перемещая вершины из этих подмножеств в разделитель по мере необходимости, пока он не станет имеет заданный размер.${\displaystyle c}$${\displaystyle {\sqrt {n}}}$${\displaystyle n}$${\displaystyle A}$${\displaystyle S}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle |S|=c}$${\displaystyle |A|=|B|=(n-c)/2}$${\displaystyle n/2}$

Как только теорема о разделителе этого типа показана, ее можно использовать для создания иерархии разделителей для плоских графов с вершинами, которая опять же не зависит от структуры графа: древовидная декомпозиция, сформированная из этой иерархии, имеет ширину и может использоваться для любых планарный граф. Множество всех пар вершин в этом древовидном разбиении, которые обе принадлежат общему узлу древовидного разбиения, образуют тривиально совершенный граф с вершинами, который содержит каждый планарный граф с каждой вершиной в качестве подграфа. Аналогичная конструкция показывает, что планарные графы ограниченной степени имеют универсальные графы с ребрами, где константа, скрытая в обозначении O${\displaystyle n}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n^{3/2})}$${\displaystyle n}$${\displaystyle O(n\log n)}$зависит от степени. Любой универсальный граф для плоских графов (или даже для деревьев неограниченной степени) должен иметь ребра. ^[38]${\displaystyle \Omega (n\log n)}$

Esperet, Joret & Morin (2020) объявили, что конструкция с использованием разделителей может быть улучшена, чтобы .${\displaystyle O(n^{3/2})}$${\displaystyle n^{1+o(1)}}$

См. Также [ править ]

• Разделитель вершин
• Геометрический разделитель

Заметки [ править ]

Ссылки [ править ]