1632
правки
Изменения
м
rollbackEdits.php mass rollback
Особенности [[укладка графа на плоскости | планарных графов]] позволяют реализовать поиск [[разрез, лемма о потоке через разрез | минимального разреза]] в планарном графе с лучшей асимптотикой, чем в произвольном графе, где поиск минимального разреза требует поиска максимального потока, то есть работает за <math>O(V^2E)</math>. Лучший известный алгоритм для планарных графов работает с асимптотикой <math>O(V\log V)</math>.
==Алгоритм за <mathtex>O(n^2 \log n)</mathtex>==
===Идея алгоритма===
{{Лемма
|statement=
<math>C</math> {{---}} минимальный <math>(s-t)-</math> разрез, тогда <math>C^d=\{\alpha \mid \alpha^d\in C\}</math> {{---}} цикл минимальной длины, ограничивающий <math>\varphi_t</math>. |proof=Формальное доказательство леммы громоздкое и здесь приведено не будет, однако сама лемма достаточно интуитивно понятна.<ref>"The following lemma is intuitive; however its formal proof is tedious, and therefore, omitted.", Maximum flow in planar networks, Itai & Shiloach, 1979, p. 147</ref>
}}
