Изменения
Нет описания правки
|about = 1
|statement=
Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex> в слоистой сети с текущим потоком, равным 0, и максимальным потоком, равным <tex>F</tex>.
Тогда <tex>l \leq \frac{P}{F} + 1</tex>
|about = 2
|statement=
Пусть <tex>N</tex> - сеть, а <tex>f</tex> - допустимый поток в этой сети. Тогда общий потенциал в остаточной сети <tex>N(f)</tex> равен общему потенциалу <tex>N</tex>.
|proof=
Пусть <tex>с_аc_f</tex> - функция пропускных способностей в <tex>N(f)</tex>, а <tex>p_f(v), in_f(v), out_f(v)</tex>- потенциал, множество входящих ребер и множество выходящих ребер вершины <tex>v</tex> из <tex>N(f)</tex>.
Достаточно доказать, что <tex>p_f(v) = p(v)</tex>. Ребру <tex>e</tex> из <tex>in(v)</tex> соответствуют ребро <tex>e_1</tex> из <tex>in_f(v)</tex> с пропускной способностью <tex>c(e) - f(e)</tex>, и ребро <tex>e_2</tex> из <tex>out_f(v)</tex> с пропускной способностью <tex>f(e)</tex>. Аналогично, ребру <tex>e</tex> из <tex>out(v)</tex> соответствуют ребра из <tex>out_f(v)</tex> с пропускной способностью <tex>c(v) - f (v)</tex> и <tex>in_f(v)</tex> с пропускной способностью <tex>f(e)</tex>. Используя правило сохранения потока, нетрудно проверить, что
<tex>\displaystyle\sum_{e\in in_f(v)} c_f(e) = \sum_{e\in in(v)}c(e)</tex>
и
<tex>\displaystyle\sum_{e\in out_f(v)} c_f(e) = \sum_{e\in out(v)}c(e)</tex>
что и требовалось доказать.
}}
{{Теорема
|id=th1.
|about=Первая теорема Карзанова
|statement=Число итераций алгоритма Диница в сети <tex>GN</tex> (<tex>s</tex>, <tex>t</tex> - исток и сток, соответственно.) с целочисленными пропускными способностями - <tex>O(\sqrt{c(G)P})</tex>.|proof=Разобьём все итерации на 2 группы: 1). Короткие фазы - когда Пусть <tex>\rho(s, t) \leq kF</tex>. 2). Длинные фазы - когда максимальный поток в сети <tex>\rho(s, t) > kN</tex>. Коротких фаз - Теорема верна для <tex>O(k)F \leq \sqrt{P}</tex> штук, т.к. так как после каждой итерации <tex>\rho(s, t)</tex> фазы поток увеличивается, но не может быть больше <tex>kхотя бы на 1. Если </tex>. Длинные фазы:Число длинных фаз <texF >\leq</tex> количество путей из <tex>ssqrt{P}</tex> , рассмотрим последнюю фазу, на момент выполнения которой поток в сети меньше, чем <tex>tF - \sqrt{P}</tex> длины . После этого потребуется не больше <tex>k</tex> <tex> \leq \fracsqrt{\sum\limits_{v \in V} c(v)}{k} = \frac{c(G)}{kP}</tex>фаз, чтобы найти максимальынй поток. На предыдущей фазе поток (т.к. через вершину <tex>vf</tex> не может пройти больше ) в <tex>c(v)N</tex> путей, а на каждом пути лежит был не больше <tex>F-\geq ksqrt{P}</tex> вершин.) Получается, что число длинных фаз - таким образом <tex>O(F-|f| \leq \fracsqrt{c(G)P}{k})</tex>.
}}
