16
правок
Изменения
→Корректность и асимптотика: minor
|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, p. 147</ref>
}}
