50
правок
Изменения
→Теоремы
Пусть в сети <tex>N</tex> нет [[Основные определения теории графов#def1|параллельных ребер]]. Пусть <tex>F</tex> {{---}} максимальный поток в <tex>N</tex>. Тогда расстояние <tex>l</tex> между <tex>s</tex> и <tex>t</tex> в <tex>N</tex> таково: <tex>l \leqslant |V|\sqrt{\dfrac{2C}{F}} - 1</tex>.
|proof=
Обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множества <tex>X = \bigcup_bigcup\limits_{i = 0}^k V_i</tex> и <tex>Y = V - X</tex> определяют разрез <tex>(X, Y)</tex>. Пропускная способность этого разреза не больше <tex>2C|V_k||V_{k + 1}|</tex>, так как все ребра между <tex>X</tex> и <tex>Y</tex> также являются ребрами между <tex>V_k</tex> и <tex>V_{k+1}</tex> и не более чем двумя параллельными ребрами, исходящими из какой-то вершины в остаточной сети. По теореме о максимальном потоке/минимальном разрезе, <tex>F \leqslant 2C|V_k||V_{k+1}|</tex>.Таким образом <tex>F</tex> ограничен наименьшим из <tex>|V_k||V_{k+1}|</tex>. Но эта величина максимальна, когда <tex>|V_i| = \dfrac{|V|}{(l+1)}</tex> для <tex>0 \leqslant i \leqslant n</tex>, таким образом <tex>F \leqslant 2C\dfrac{|V|^2 }{ (l+1)^2}</tex>. Выражая <tex>l</tex>, получаем нужноеиз чего следует необходимое неравенство.
}}
