Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами (здесь O обозначает «O» большое) можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин.
Более слабую теорему о планарном разбиении с O(√n log n) вершинами в сепараторе вместо O(√n) доказал Унгар , а теорему с более сильной асимптотической границей на размер сепаратора первыми доказали Липтон и Тарьян . После их статей теорема о планарном разбиении была передоказана несколькими различными путями, константа 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) вершин. Такое разбиение известно как разъединение. Если разъединение задано, пересечение множеств вершин образует сепаратор, а вершины, принадлежащие одному подграфу, но не принадлежащие другому, образуют два подмножества с числом вершин, не превосходящим 2n/3. В обратную сторону, если задано разбиение на три множества A, S и B, удовлетворяющих условиям теоремы о планарном разбиении, то можно образовать разъединение, в котором рёбра с концами в A принадлежат G1, рёбра с концами в B принадлежат G2, а оставшиеся рёбра (с обоими концами в S) можно включать в любое из множеств.
Постоянная 2/3 в утверждении теоремы произвольна и может быть заменена на любое другое число из открытого интервала (1/2,1) без изменения формы теоремы — разбиение на подмножества более равного размера можно получить из менее одинаковых разбиений путём повторного разбиения большего множества на неравные части и перегруппировки получившихся связных компонент.
Пример
Рассмотрим решётку с 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. Вместо использования строк и столбцов в качестве сепаратора для разбиения графа Джорж использует их объединение и разбивает граф на четыре части..
Теорема о планарном разбиении утверждает, что аналогичное разбиение может быть построено для любого планарного графа. Случай произвольного планарного графа отличается от графа решётки тем, что в этом случае сепаратор имеет размер O(√n), что может быть больше числа √n, а размеры двух подмножеств A и B (в наиболее распространённой версии теоремы) не превосходят 2n/3, а не n/2, как для графов решёток. Кроме того, подмножества A и B не обязательно образуют связные подграфы.
Построения
Расслоение Липтон и Тарьян увеличивают заданный планарный граф путём добавления рёбер, если необходимо, так что он становится максимальным планарным графом (каждая грань планарного вложения является треугольником). Затем они осуществляют поиск в ширину, начиная с произвольной вершины 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. Анализируя подобные построения сепараторов более тщательно, Джиджев показал, что граница размера S может быть уменьшена до √6√n, что примерно равно 2.45√n.
Хольцер, Шульц Вагнер, Прасинос и Заролигис предложили упрощённую версию подхода — они расширяют граф до максимального планарного и осуществляют поиск в ширину так же, как описано выше. Затем для каждого ребра e, не принадлежащего дереву поиска, они образуют цикл, комбинируя e с путями в дереве, соединяющими концы ребра. Затем они используют в качестве сепаратора вершин один из таких циклов. Хотя этот подход не гарантирует нахождение сепаратора малого размера для планарных графов большого диаметра, их эксперименты показывают, что такой подход работает лучше, чем методы расслоения Липтона — Тарьяна и Диджева, на многих типах планарных графов.
Простые сепараторы-циклы Для графа, который уже является максимальным планарным, можно показать строгое построение простого сепаратора-цикла, цикла малой длины, внутренняя и внешняя части которого (для конкретного планарного вложения) имеют не более 2n/3 вершин. Миллер доказал это (с сепаратором размера √8√n), используя технику Липтона — Тарьяна для модифицированной версии поиска в ширину, в которой уровни образуют простые циклы.
Алон, Сеймур и Томас доказали существование простого сепаратора-цикла более прямым путём — они рассматривали циклы C с не более чем √8√n вершинами, имеющими не более 2n/3 вершин вне цикла C, затем формировали разбиение на как можно более близкие части внутри и вне цикла. Они показали, что при всех этих условиях C необходимо будет сепаратором. В противном случае, расстояния внутри C должны быть равны расстояниям в диске, заключённом в C (кратчайший путь через внутренность диска образовал бы часть границы лучшего цикла). Кроме того, цикл C должен иметь длину в точности √8√n, в противном случае он может быть улучшен путём замены одного из рёбер двумя другими сторонами треугольника. Если вершины цикла C пронумерованы (по часовой стрелке) от 1 до √8√n и вершина i сопоставляется вершине , то эти пары вершин можно соединить непересекающимися путями внутри диска (по одной из форм теоремы Менгера для планарных графов). Однако суммарная длина этих путей превысила бы n, получили противоречие. Проведя некоторые дополнительные выкладки, они показали, применив похожие методы, что существует простой сепаратор-цикл размера, не превышающего (3/√2)√n, что примерно равно 2.12√n.
Джиджев и Венкатесан позднее улучшили константу в теореме о простом сепараторе-цикле до 1.97√n. Их метод позволяет также искать простые сепараторы-циклы для графов с неотрицательными весами вершин с размером сепаратора, не превосходящим 2√n. Метод позволяет создавать сепараторы и с меньшим размером, правда, за счёт большей разницы в размерах частей разбиения. В 2-связном планарном графе, не являющемся максимальным, существует простой сепаратор-цикл с размером, пропорциональным евклидовой норме вектора длин граней, который можно найти за почти линейное время.
Сепараторы-циклы Согласно теореме Кёбе — Андреева — Тёрстона об упаковке кругов любой планарный граф можно представить как упаковку кругов на плоскости с непересекающимися внутренними областями, так что две вершины графа смежны в том и только в том случае, когда соответствующие круги соприкасаются. Как показали Миллер, Тенг, Тёрстон и Вавасис, для таких упаковок существует окружность, которой касаются, либо лежат внутри неё, не более 3n/4 дисков, не более 3n/4 дисков лежат вне окружности, либо касаются её, и которая пересекает O(√n) дисков.
Для доказательства этого Миллер и др. использовал стереографическую проекцию для отображения упаковки на поверхность единичной трёхмерной сферы. При осторожном выборе проекции центр сферы можно поместить в центров дисков поверхности, так что любая плоскость, проходящая через центр сферы, будет делить сферу на две полусферы, каждая из которых содержит или пересекает не более 3n/4 дисков. Если плоскость через центр выбирать случайно и равномерно, диск будет пресечён с вероятностью, пропорциональной радиусу. Таким образом, ожидаемое число пересечённых дисков пропорционально сумме радиусов дисков. Однако сумма квадратов радиусов пропорциональна полной площади дисков, что не превосходит площади поверхности единичной сферы, константы. Доводы, использующие неравенство Йенсена, показывают, что в случае ограниченности суммы квадратов n неотрицательных чисел константой, сумма самих чисел не превосходит O(√n). Таким образом, ожидание числа пересечений дисков случайной плоскостью равно O(√n) и существует плоскость, пересекающая не более этого количества дисков. Эта плоскость пересекает сферу по большому кругу, проекция которого обратно на плоскость даёт желаемые свойства. Пересечённые этой окружностью O(√n) дисков соответствуют вершинам сепаратора планарного графа, который отделяет вершины, диски которых лежат внутри окружности, от вершин, диски которых лежат вне окружности, и каждое из этих подмножеств имеет не более 3n/4 вершин.
Этот метод приводит к вероятностному алгоритму, который находит сепаратор за линейное время и менее практичному детерминированному алгоритму с той же линейной временной границей. При тщательном анализе этого алгоритма и использовании известных границ плотности упаковки кругов можно показать, что можно найти сепараторы, не превосходящие по размеру .