Изменения

Рассмотрим граф <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>. Тогда алгоритм можно записать так: