16
правок
Изменения
Алгоритм за O(n^2 logn)
Особенности [[укладка графа на плоскости | планарных графов]] позволяют реализовать поиск [[разрез, лемма о потоке через разрез | минимального разреза]] в планарном графе с лучшей асимптотикой, чем в произвольном графе. Лучший известный алгоритм работает с асимптотикой <math>O(n\log n)</math>.
==Алгоритм за <math>O(n^2 \log n)</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>.
Будем обозначать грани <math>G^d</math>, соответствующие вершинам <math>s</math> и <math>t</math>, как <math>\varphi_s</math> и <math>\varphi_t</math> соответственно. Далее будем считать, что <math>\varphi_s</math> {{---}} внешняя грань <math>G^d</math>.
{{Лемма
|statement=
<math>C</math> {{---}} минимальный <math>(s-t)-</math> разрез, тогда <math>C^d=\{\alpha | \alpha^d\in C\}</math> {{---}} цикл минимальной длины, ограничивающий <math>\varphi_t</math>.
}}
Формальное доказательство леммы громоздкое и здесь приведено не будет, однако сама лемма достаточно интуитивно понятна.
Пусть <math>\xi^s\in\varphi_s</math>, <math>\xi^t\in\varphi_t</math>, <math>\Pi=(\xi^s=\xi_1, \ldots, \xi_k=\xi^t)</math> {{---}} кратчайший путь между <math>\xi^s</math> и <math>\xi^t</math> в <math>G^d</math>, <math>\alpha_i</math> {{---}} ребро между <math>\xi_{i-1}</math> и <math>\xi_i</math> для <math>i=2,\ldots,k</math>. Будем называть ребро <math>\xi-\xi_i\in A</math> <math>\Pi-</math> левым, если оно находится между <math>\alpha_i</math> и <math>\alpha_{i+1}</math> при обходе ребер, входящих в <math>\xi_i</math>, по часовой стрелке от <math>\alpha_i</math>, и <math>\Pi-</math> правым, если оно находится между <math>\alpha_{i+1}</math> и <math>\alpha_i</math>.
Для того, чтобы это определение имело смысл для первой и последней вершин пути, можно добавить две вершины <math>\xi_0</math> и <math>\xi_{k+1}</math> и два ребра <math>\alpha_1=\xi_0-\xi_1</math> и <math>\alpha_{k+1}=\xi_k-\xi_{k+1}</math>. Важно, что никакое ребро не является одновременно <math>\Pi-</math> левым и <math>\Pi-</math> правым.
Будем называть <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>.
}}
Из леммы следует алгоритм нахождения минимального ограничивающего <math>\varphi_t</math> цикла:
# Для <math>i=1,\ldots,k</math> найдем минимальный <math>\xi_i</math> - цикл
# Кратчайший из этих <math>k</math> путей будет минимальным ограничивающим <math>\varphi_t</math> циклом
Для поиска минимального <math>\xi_i</math> - цикла построим из неориентированного графа <math>G</math> ориентированный граф <math>\vec{G}^d</math> следующим образом: все <math>\Pi-</math> левые ребра ориентируем из вершин <math>\xi\in\Pi</math>, все <math>\Pi-</math> правые ребра ориентируем в вершины <math>\xi\in\Pi</math>, а остальные ребра <math>u-v</math> заменим на два ребра <math>u\rightarrow v</math> и <math>v\rightarrow u</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>.
==См. также==
* [[Двойственный граф планарного графа]]
* [[Разрез, лемма о потоке через разрез]]
* [[Укладка графа на плоскости]]
==Источники информации==
* [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]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов]]
==Алгоритм за <math>O(n^2 \log n)</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>.
Будем обозначать грани <math>G^d</math>, соответствующие вершинам <math>s</math> и <math>t</math>, как <math>\varphi_s</math> и <math>\varphi_t</math> соответственно. Далее будем считать, что <math>\varphi_s</math> {{---}} внешняя грань <math>G^d</math>.
{{Лемма
|statement=
<math>C</math> {{---}} минимальный <math>(s-t)-</math> разрез, тогда <math>C^d=\{\alpha | \alpha^d\in C\}</math> {{---}} цикл минимальной длины, ограничивающий <math>\varphi_t</math>.
}}
Формальное доказательство леммы громоздкое и здесь приведено не будет, однако сама лемма достаточно интуитивно понятна.
Пусть <math>\xi^s\in\varphi_s</math>, <math>\xi^t\in\varphi_t</math>, <math>\Pi=(\xi^s=\xi_1, \ldots, \xi_k=\xi^t)</math> {{---}} кратчайший путь между <math>\xi^s</math> и <math>\xi^t</math> в <math>G^d</math>, <math>\alpha_i</math> {{---}} ребро между <math>\xi_{i-1}</math> и <math>\xi_i</math> для <math>i=2,\ldots,k</math>. Будем называть ребро <math>\xi-\xi_i\in A</math> <math>\Pi-</math> левым, если оно находится между <math>\alpha_i</math> и <math>\alpha_{i+1}</math> при обходе ребер, входящих в <math>\xi_i</math>, по часовой стрелке от <math>\alpha_i</math>, и <math>\Pi-</math> правым, если оно находится между <math>\alpha_{i+1}</math> и <math>\alpha_i</math>.
Для того, чтобы это определение имело смысл для первой и последней вершин пути, можно добавить две вершины <math>\xi_0</math> и <math>\xi_{k+1}</math> и два ребра <math>\alpha_1=\xi_0-\xi_1</math> и <math>\alpha_{k+1}=\xi_k-\xi_{k+1}</math>. Важно, что никакое ребро не является одновременно <math>\Pi-</math> левым и <math>\Pi-</math> правым.
Будем называть <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>.
}}
Из леммы следует алгоритм нахождения минимального ограничивающего <math>\varphi_t</math> цикла:
# Для <math>i=1,\ldots,k</math> найдем минимальный <math>\xi_i</math> - цикл
# Кратчайший из этих <math>k</math> путей будет минимальным ограничивающим <math>\varphi_t</math> циклом
Для поиска минимального <math>\xi_i</math> - цикла построим из неориентированного графа <math>G</math> ориентированный граф <math>\vec{G}^d</math> следующим образом: все <math>\Pi-</math> левые ребра ориентируем из вершин <math>\xi\in\Pi</math>, все <math>\Pi-</math> правые ребра ориентируем в вершины <math>\xi\in\Pi</math>, а остальные ребра <math>u-v</math> заменим на два ребра <math>u\rightarrow v</math> и <math>v\rightarrow u</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>.
==См. также==
* [[Двойственный граф планарного графа]]
* [[Разрез, лемма о потоке через разрез]]
* [[Укладка графа на плоскости]]
==Источники информации==
* [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]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов]]
