Изменения

Особенности [[укладка графа на плоскости | планарных графов]] позволяют реализовать поиск [[разрез, лемма о потоке через разрез | минимального разреза]] в планарном графе с лучшей асимптотикой, чем в произвольном графе, где поиск минимального разреза требует поиска максимального потока, то есть работает за <math>O(V^2E)</math>. Лучший известный алгоритм для планарных графов работает с асимптотикой <math>O(V\log V)</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>.

Каждый такой цикл соответствует разрезу в <math>G</math>. Тогда алгоритм можно записать так:

{{Лемма

|statement=

}}