16
правок
Изменения
рефакторинг
Особенности [[укладка графа на плоскости | планарных графов]] позволяют реализовать поиск [[разрез, лемма о потоке через разрез | минимального разреза]] в планарном графе с лучшей асимптотикой, чем в произвольном графе, где поиск минимального разреза требует поиска максимального потока, то есть работает за <math>O(V^2E)</math>. Лучший известный алгоритм для планарных графов работает с асимптотикой <math>O(nV\log nV)</math>.
==Алгоритм за <math>O(n^2 \log n)</math>==
===Идея алгоритма===Рассмотрим граф <math>G^d</math>, [[двойственный граф планарного графа | двойственный]] данному графу <math>G</math>. Рассмотрим кратчайший путь <math>\Pi</math> между вершинами <math>\xi^s</math> и <math>\xi^t</math>, принадлежащими граням <math>\varphi_s</math> и <math>\varphi_t</math>, соответствующим вершинам <math>s</math> и <math>t</math> в исходном графе. Определим <math>\Pi</math>-левые и <math>\Pi</math>-правые ребра, <math>\Pi</math>-левые будут лежать "слева" по пути из <math>\xi^s</math> в <math>\xi^t</math>, а <math>\Pi</math>-"правые" справа. Формальное определение будет дано в следующем разделе. Тогда минимальный цикл в <math>G^d</math>, ограничивающий <math>\varphi_t</math>, будет <math>\xi_i</math>-циклом {{---}} циклом, содержащим ровно одно <math>\Pi</math>-левое и одно <math>\Pi</math>-правое ребро, причем <math>\Pi</math>-левое ребро входит в вершину <math>\xi_i</math>. [[Файл:Xi_cycles.png|600px|thumb|center|Кси-циклы]] Каждый такой цикл соответствует разрезу в <math>G</math>. Тогда алгоритм можно записать так:# Построим граф <math>G^d</math>, двойственный исходному графу <math>G</math># Найдем кратчайший путь <math>\Pi</math> между вершинами <math>\xi^s</math> и <math>\xi^t</math># Для каждой вершины <math>\xi_i\in\Pi</math> найдем кратчайший <math>\xi_i</math>-цикл# Найдем среди этих циклов цикл минимальной длины и построим соответствующий ему разрез в <math>G</math> ===Корректность и асимптотика===Рассмотрим неориентированный граф <math>G=(V, E)</math>. Будем считать его трёхсвязным, если это не так, [[теорема Фари триангуляция полигонов (ушная + монотонная) | триангулируем]] его, используя ребра нулевой пропускной способности, это не изменит значение минимального <math>(s-t)-</math> разреза. Минимальный разрез исходного графа будет состоять из ребер минимального разреза нового графа, которые есть и в исходном графе.
<math>G</math> трёхсвязен, поэтому существует единственный [[двойственный граф планарного графа | двойственный]] ему граф <math>G^d=(X, A)</math>, при этом <math>G^d</math> также трёхсвязен. Будем обозначать множество граней <math>G</math> как <math>F</math>, множество граней <math>G^d</math> как <math>\Phi</math>. Между элементами каждой из пар множеств <math>V-\Phi</math>, <math>E-A</math> и <math>F-X</math> существует взаимно однозначное соответствие. Будем обозначать как <math>\alpha^d\in E</math> элемент, соответствующий <math>\alpha\in A</math>. Тогда длину ребра <math>\alpha</math> определим как <math>l(\alpha)=c(\alpha^d)</math>.
{{Лемма
|statement=
<math>C</math> {{---}} минимальный <math>(s-t)-</math> разрез, тогда <math>C^d=\{\alpha | \mid \alpha^d\in C\}</math> {{---}} цикл минимальной длины, ограничивающий <math>\varphi_t</math>.Формальное доказательство леммы громоздкое и здесь приведено не будет, однако сама лемма достаточно интуитивно понятна.<ref>"The following lemma is intuitive; however its formal proof is tedious, and therefore, omitted.", Maximum flow in planar networks, Itai & Shiloach, 1979</ref>
}}
Будем называть <math>\xi_i</math> - циклом простой цикл, который содержит ровно одно <math>\Pi-</math> -левое и одно <math>\Pi-</math> -правое ребро, при этом <math>\Pi-</math> -левое ребро входит в вершину <math>\xi_i</math>. Любой <math>\xi_i</math> - цикл ограничивает <math>\varphi_t</math>.
{{Лемма
|statement=
Пусть <math>C</math> {{---}} кратчайший ограничивающий <math>\varphi_t</math> цикл. Тогда существует <math>\xi_i</math> - цикл такой же длины.
|proof=
<math>\Pi</math> {{---}} кратчайший путь между <math>\xi^s</math> и <math>\xi^t</math>, поэтому любой содержащийся в <math>\Pi</math> путь между <math>\xi_i</math> и <math>\xi_j</math> также кратчайший. При этом любой ограничиващий <math>\varphi_t</math> цикл обязан пересекать <math>\Pi</math>. Цикл, не являющийся <math>\xi_i</math> - циклом, не будет кратчайшим, так как его можно будет сократить вдоль пути <math>\Pi</math>.
}}
{{Лемма
|statement=
Пусть <math>\xi_i\in\Pi</math>, <math>P_i</math> {{---}} кратчайший нетривиальный путь из <math>\xi_i</math> в <math>\xi_i</math> в <math>\vec{G}^d</math>. Тогда соответствующий путь в <math>G^d</math> является кратчайшим <math>\xi_i</math> - циклом.
|proof=
Из определения <math>\vec{G}^d</math> следует, что если нетривиальный путь из <math>\xi_i</math> в <math>\xi_i</math> содержит больше одного <math>\Pi-</math> -правого или <math>\Pi-</math> -левого ребра, то в нем есть самопересечение, то есть он не является простым, следовательно, не является кратчайшим <math>\xi_i</math> - циклом.
}}
Таким образом, нахождение минимального <math>\xi_i</math> - цикла эквивалентно нахождению кратчайшего нетривиального пути из <math>\xi_i</math> в <math>\xi_i</math> в <math>\vec{G}^d</math>. Это можно сделать за <math>O(m\log n)</math>, например, с помощью [[алгоритм Дейкстры | алгоритма Дейкстры]]. Так как в планарных графах <math>m=O(n)</math>, это равно <math>O(n\log n)</math>. Максимум <math>n</math> таких поисков дадут итоговую асимптотику <math>O(n^2\log n)</math>.
==См. также==
* [[Разрез, лемма о потоке через разрез]]
* [[Укладка графа на плоскости]]
==Примечания==
<references/>
==Источники информации==
* [http://verona.dei.unipd.it/~prin08/primo_meeting/italiano.pdf: Improved Algorithms for Min Cuts and Max Flows in Undirected Planar Graphs]* [https://pdfs.semanticscholar.org/b838/35db99723f922b7b286d10952b08c68970a7.pdf: Maximum flow in planar networks, Itai & Shiloach, 1979]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов]]
