Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями

Определение:

Пусть [math]N = (V,E,s,t,c)[/math] - сеть с целочисленными пропускными способностями. Обозначим [math]C[/math] и [math]F[/math], как максимальная пропускная способность ребра и максимальный поток соответсвенно. [math]c^{+}(v) = \sum\limits_{uv \in E} c_{uv}[/math]. [math]c^{-}(v) = \sum\limits_{vu \in E} c_{vu}[/math]. [math]p(v) = min\big\{c^{+}(v), c^{-}(v)\big\}[/math] - потенциал вершины [math]v[/math]. Тогда общий потенциал выражается формулой: [math]P = \sum\limits_{v \in V, v \neq s,t}p(v)[/math].

Лемма (1):

Пусть [math]l[/math] - расстояние между [math]s[/math] и [math]t[/math] в сети с текущим потоком, равным 0, и максимальным потоком, равным [math]F[/math]. Тогда [math]l \leq \frac{P}{F} + 1[/math]

Доказательство:

[math]\triangleright[/math]

Пусть [math]l[/math] - расстояние между [math]s[/math] и [math]t[/math], а [math]V_i[/math] - набор вершин, удаленных от [math]s[/math] на [math]i[/math] [math](i \leq l)[/math]. [math]V_i[/math] - разъединяющее множество узлов: при его удалении исчезают все направлнные пути из [math]s[/math] в [math]t[/math]. Следуя правилу сохранения потока, если [math]f[/math] обозначить как любой допустимый поток, то [math]|f|[/math] единиц потока должно проходить через [math]V_i[/math]. Но суммарное количество потока, которое может проходить через любую вершину не превосходит ее потенциала. Отсюда, если обозначить [math]P_i[/math] как общий потенциал вершин из [math]V_i[/math], то мы имеем: [math]|f| \leq P_i[/math] для любого допустимого потока [math]f[/math]. В частности, [math]F \leq P_i[/math], таким образом получаем: [math](l - 1)F \leq \displaystyle \sum_{i = 1}^{l - 1} P_i \leq P[/math] и лемма доказана.

[math]\triangleleft[/math]

Лемма (2):

Пусть [math]N[/math] - сеть, а [math]f[/math] - допустимый поток в этой сети. Тогда общий потенциал в остаточной сети [math]N(f)[/math] равен общему потенциалу [math]N[/math].

Доказательство:

[math]\triangleright[/math]

Пусть [math]с_а[/math] - функция пропускных способностей в [math]N(f)[/math], а [math]p_f(v), in_f(v), out_f(v)[/math]

[math]\triangleleft[/math]

Теорема (Первая теорема Карзанова):

Число итераций алгоритма Диница в сети [math]G[/math] ([math]s[/math], [math]t[/math] - исток и сток, соответственно.) с целочисленными пропускными способностями - [math]O(\sqrt{c(G)})[/math].

Доказательство:

[math]\triangleright[/math]

Разобьём все итерации на 2 группы: 1). Короткие фазы - когда [math]\rho(s, t) \leq k[/math]. 2). Длинные фазы - когда [math]\rho(s, t) \gt k[/math]. Коротких фаз - [math]O(k)[/math] штук, т.к. после каждой итерации [math]\rho(s, t)[/math] увеличивается, но не может быть больше [math]k[/math]. Длинные фазы: Число длинных фаз [math]\leq[/math] количество путей из [math]s[/math] в [math]t[/math] длины больше [math]k[/math] [math] \leq \frac{\sum\limits_{v \in V} c(v)}{k} = \frac{c(G)}{k}[/math]. (т.к. через вершину [math]v[/math] не может пройти больше [math]c(v)[/math] путей, а на каждом пути лежит [math]\geq k[/math] вершин.) Получается, что число длинных фаз - [math]O(\frac{c(G)}{k})[/math]. Давайте возьмём [math]k = \sqrt{c(G)}[/math]. Получим, что количество фаз - [math]O(\sqrt{c(G)})[/math]. А, значит, что количество итераций тоже - [math]O(\sqrt{c(G)})[/math].

[math]\triangleleft[/math]

Теорема (Вторая теорема Карзанова):

Число итераций алгоритма Диница в сети [math]G[/math] ([math]s[/math], [math]t[/math] - исток и сток, соответственно.) с целочисленными пропускными способностями меньше [math]c_{max}[/math] - [math]O(\sqrt[3]{{|V|}^2 c_{max}})[/math].