Разрез в планарных графах
Особенности планарных графов позволяют реализовать поиск минимального разреза в планарном графе с лучшей асимптотикой, чем в произвольном графе, где поиск минимального разреза требует поиска максимального потока, то есть работает за . Лучший известный алгоритм для планарных графов работает с асимптотикой .
Содержание
Алгоритм за [править]
Идея алгоритма[править]
Рассмотрим граф двойственный данному графу . Рассмотрим кратчайший путь между вершинами и , принадлежащими граням и , соответствующим вершинам и в исходном графе. Определим -левые и -правые ребра, -левые будут лежать "слева" по пути из в , а -правые "справа". Формальное определение будет дано в следующем разделе. Тогда минимальный цикл в , ограничивающий , будет -циклом — циклом, содержащим ровно одно -левое и одно -правое ребро, причем -левое ребро входит в вершину .
,Каждый такой цикл соответствует разрезу в
. Тогда алгоритм можно записать так:- Построим граф , двойственный исходному графу
- Найдем кратчайший путь между вершинами и
- Для каждой вершины найдем кратчайший -цикл
- Найдем среди этих циклов цикл минимальной длины и построим соответствующий ему разрез в
Корректность и асимптотика[править]
Рассмотрим неориентированный граф триангулируем его, используя ребра нулевой пропускной способности, это не изменит значение минимального разреза. Минимальный разрез исходного графа будет состоять из ребер минимального разреза нового графа, которые есть и в исходном графе.
. Будем считать его трёхсвязным, если это не так,двойственный ему граф , при этом также трёхсвязен. Будем обозначать множество граней как , множество граней как . Между элементами каждой из пар множеств , и существует взаимно однозначное соответствие. Будем обозначать как элемент, соответствующий . Тогда длину ребра определим как .
трёхсвязен, поэтому существует единственныйБудем обозначать грани
, соответствующие вершинам и , как и соответственно. Далее будем считать, что — внешняя грань .Лемма: |
— минимальный разрез, тогда — цикл минимальной длины, ограничивающий . |
Доказательство: |
Формальное доказательство леммы громоздкое и здесь приведено не будет, однако сама лемма достаточно интуитивно понятна.[1] |
Пусть
, , — кратчайший путь между и в , — ребро между и для . Будем называть ребро -левым, если оно находится между и при обходе ребер, входящих в , по часовой стрелке от , и -правым, если оно находится между и . Для того, чтобы это определение имело смысл для первой и последней вершин пути, можно добавить две вершины и и два ребра и . Важно, что никакое ребро не является одновременно -левым и -правым.Будем называть
-циклом простой цикл, который содержит ровно одно -левое и одно -правое ребро, при этом -левое ребро входит в вершину . Любой -цикл ограничивает .Лемма: |
Пусть — кратчайший ограничивающий цикл. Тогда существует -цикл такой же длины. |
Доказательство: |
— кратчайший путь между и , поэтому любой содержащийся в путь между и также кратчайший. При этом любой ограничиващий цикл обязан пересекать . Цикл, не являющийся -циклом, не будет кратчайшим, так как его можно будет сократить вдоль пути . |
Для поиска минимального
-цикла построим из неориентированного графа ориентированный граф следующим образом: все -левые ребра ориентируем из вершин , все -правые ребра ориентируем в вершины , а остальные ребра заменим на два ребра и .Лемма: |
Пусть , — кратчайший нетривиальный путь из в в . Тогда соответствующий путь в является кратчайшим -циклом. |
Доказательство: |
Из определения | следует, что если нетривиальный путь из в содержит больше одного -правого или -левого ребра, то в нем есть самопересечение, то есть он не является простым, следовательно, не является кратчайшим -циклом.
Таким образом, нахождение минимального алгоритма Дейкстры. Так как в планарных графах , это равно . Максимум таких поисков дадут итоговую асимптотику .
-цикла эквивалентно нахождению кратчайшего нетривиального пути из в в . Это можно сделать за , например, с помощьюСм. также[править]
Примечания[править]
- ↑ "The following lemma is intuitive; however its formal proof is tedious, and therefore, omitted.", Maximum flow in planar networks, Itai & Shiloach, 1979, p. 147