Теорема о плоском сепараторе - Planar separator theorem

В теории графов теорема о плоском разделителе - это форма изопериметрического неравенства для плоских графов , в котором говорится, что любой плоский граф можно разбить на более мелкие части, удалив небольшое количество вершин. В частности, удаление вершин из -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-сложных задач оптимизации на этих графах. Иерархии разделителей могут также использоваться во вложенном разрезе , эффективном варианте исключения Гаусса для решения разреженных систем линейных уравнений, возникающих из методов конечных элементов .

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

Формулировка теоремы

Как правило , указываются, отделитель теорема утверждает , что в любом -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 плоского графа может быть подразделена на два ребро непересекающихся подграфов , и таким образом , что оба подграфы имеют по меньшей мере вершины и такие , что пересечение множеств вершин двух подграфов имеют вершины в Это. Такая перегородка называется разделением . Если задано разделение, то пересечение множеств вершин образует разделитель, а вершины, принадлежащие одному подграфу, но не другому, образуют отдельные подмножества, каждое из которых имеет не более чем вершины. В другом направлении, если дано разбиение на три множества , и которые удовлетворяют условиям теоремы о плоском разделителе, тогда можно сформировать разделение, в котором ребра с концом в принадлежат , а ребра с концом в принадлежат , а остальные ребра (с обеими конечными точками внутри ) разбиваются произвольно. ${\ 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}$

Константа в формулировке теоремы о разделителе является произвольной и может быть заменена любым другим числом в открытом интервале без изменения формы теоремы: разбиение на более равные подмножества может быть получено из менее четного разбиения путем многократного разбиения большие наборы в неравномерном разделе и перегруппировке полученных связанных компонентов. ${\ 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}$${\ 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}} \ приблизительно 2,83 {\ sqrt {n}}}$

Это доказательство теоремы о разделителе применимо также к взвешенным планарным графам, в которых каждая вершина имеет неотрицательную стоимость. Граф может быть разделена на три группы , и таким образом, что и каждый имеет максимум от общей стоимости и имеет вершины, без ребер из и . Более тщательно анализируя подобную конструкцию разделителя, Джиджев (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}} \ приблизительно 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}} - я + 1}$${\ displaystyle n}$${\ displaystyle {\ sqrt {9n / 2}} \ приблизительно 2,12 {\ sqrt {n}}}$

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

Разделители кругов

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

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

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

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

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

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

Спектральные кластерные методы, в которых вершина графа сгруппированы в зависимости от координат собственных векторов из матриц , полученных из графика, уже давно используются в качестве эвристики для графа разбиения задач для неплоских графов. Как показывают 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}$${\ displaystyle \ Delta}$${\ displaystyle O ({\ sqrt {\ Delta n}})}$

Простой разделитель циклов в двойственном графе планарного графа образует разделитель ребер в исходном графе. Применение теоремы о простом разделителе циклов Газита и Миллера (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}} \ приблизительно 0,82 {\ sqrt {n}}}$

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

Иерархии разделителей

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

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

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

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

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

Другие классы графов

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

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

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

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

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

Если наследственное семейство графов имеет теорему о разделителях с разделителями размера для некоторых , то оно обязательно имеет полиномиальное расширение , полиномиальную оценку плотности его мелких миноров . И наоборот, графы с полиномиальным расширением имеют теоремы о сублинейных разделителях. ${\ displaystyle n ^ {c}}$${\ displaystyle c <1}$

Приложения

Алгоритмы разделяй и властвуй

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

• 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 О (п ^ {3/2} \ журнал п)}$

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

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

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

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

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

Вложенное рассечение - это вариант разделения Гаусса, основанный на разделении, для решения разреженных симметричных систем линейных уравнений с плоской структурой графа, таких как системы, возникающие из метода конечных элементов . Он включает в себя поиск разделителя для графа, описывающего систему уравнений, рекурсивное удаление переменных в двух подзадачах, отделенных друг от друга разделителем, а затем удаление переменных в разделителе. Заполнение этого метода (количество ненулевых коэффициентов результирующего разложения Холецкого матрицы) составляет , что позволяет этому методу быть конкурентоспособным с итерационными методами для тех же задач. ${\ Displaystyle О (п \ журнал п)}$

Кляйн, Мозес и Вейманн предложили алгоритм линейного пространства-времени для нахождения кратчайшего пути от исходной вершины до всех других вершин для ориентированного плоского графа с положительной и отрицательной длинами дуги, не содержащего отрицательных циклов. Их алгоритм использует плоский граф разделители , чтобы найти кривой Жордан , которая проходит через узлы (и нет дуг) такое , что между и узлы заключены . Узлы, через которые проходят проходы, являются граничными узлами. Исходный граф разделяется на два подграфа и путем разрезания плоского вложения вдоль и дублирования граничных узлов. Граничные узлы в каждом графе лежат на границе одной грани . ${\ Displaystyle О (п \ журнал ^ {2} п)}$${\ 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 О (п \ журнал п)}$
• Граничные расстояния между частями из одного источника: кратчайший путь проходит взад и вперед между и для вычисления расстояний от до всех граничных узлов. При чередовании итераций используются все-границы-расстояния в и . Число итераций равно , а общее время для этого этапа - где - обратная функция Аккермана .${\ displaystyle G}$${\ displaystyle G_ {0}}$${\ displaystyle G_ {1}}$${\ displaystyle G}$${\ displaystyle r}$${\ displaystyle G_ {0}}$${\ displaystyle G_ {1}}$${\ displaystyle O ({\ sqrt {n}})}$${\ Displaystyle О (п \ альфа (п))}$${\ Displaystyle \ альфа (п)}$
• Расстояния между частями от одного источника: Расстояния, вычисленные на предыдущих этапах, используются вместе с вычислением Дейкстры в модифицированной версии каждого G _i  для вычисления расстояний от до всех узлов. Этот этап требует времени.${\ displaystyle G}$${\ displaystyle r}$${\ Displaystyle О (п \ журнал п)}$
• Корректировка расстояний от одного источника: расстояния от in преобразуются в неотрицательные длины, и снова алгоритм Дейкстры используется для вычисления расстояний от . Этот этап требует времени.${\ displaystyle r}$${\ displaystyle G}$${\ displaystyle s}$${\ Displaystyle О (п \ журнал п)}$

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

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

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

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

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

Алгоритмы аппроксимации

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

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

Сжатие графика

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

Универсальные графики

Универсальный график для семейства графов представляет собой график , который содержит каждый член как подграфы. С помощью разделителей можно показать, что планарные графы -вершины имеют универсальные графы с вершинами и ребрами. ${\ Displaystyle {\ mathcal {F}}}$${\ Displaystyle {\ mathcal {F}}}$${\ displaystyle n}$${\ displaystyle n}$${\ Displaystyle О (п ^ {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 | = (NC) / 2}$${\ displaystyle n / 2}$

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

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

Смотрите также

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

Заметки

Рекомендации