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

Обозначения

Введём следующие обозначения:

• [math]N = (V,E,s,t,c)[/math] — сеть с целочисленными пропускными способностями,
• обозначим [math]C = \max\limits_{uv \in E} c_{uv}[/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(c^{+}(v), c^{-}(v))[/math] — потенциал вершины [math]v[/math],
• [math]P = \sum\limits_{v \in V, v \neq s,t}p(v)[/math] — общий потенциал,
• [math]G_f[/math] — остаточная сеть.

Теоремы

Лемма (1):

Пусть [math]l[/math] — расстояние между [math]s[/math] и [math]t[/math] в исходной сети, максимальный поток в этой сети равен [math]F[/math]. Тогда [math]l \leqslant \dfrac{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 \leqslant 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| \leqslant P_i[/math] для любого допустимого потока [math]f[/math]. В частности, [math]F \leqslant P_i[/math], таким образом получаем: [math](l - 1)F \leqslant \displaystyle \sum_{i = 1}^{l - 1} P_i \leqslant P[/math]

[math]\triangleleft[/math]

Лемма (2):

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

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

[math]\triangleright[/math]

По теореме о декомпозиции поток можно разбить на множество простых путей из [math]s[/math] в [math]t[/math] и циклов. Рассмотрим каждый путь (цикл) и убедимся, что, пуская по нему поток [math]f_i[/math], потенциал вершины не изменится. Действительно, рассмотрим вершину [math]v[/math], поток [math]f_i[/math] в неё течёт по ребру [math]uv[/math], а из неё по ребру [math]vw[/math]. Пусть [math]c_{f_i}[/math] — функция пропускных способностей в остаточной сети после пропускания потока по [math]i[/math]-ому пути (циклу). Рассмотрим [math]c^+_{f_1}(v) = c_{f_1}(uv) + c_{f_1}(wv)[/math]. [math]c_{f_1}(uv) = c(uv) - f_i[/math], а [math]c_{f_1}(wv) = c(wv) + f_i[/math], сложив эти два значения, получим, что [math]c^+(v)[/math] остаётся неизменной. Применив такое же рассуждение для [math]c^-(v)[/math], получим, что потенциал каждой вершины остаётся неизменным.

[math]\triangleleft[/math]

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

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

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

[math]\triangleright[/math]

Пусть [math]F[/math] — максимальный поток в сети [math]N[/math]. Теорема верна для [math]F \leqslant \sqrt{P}[/math], так как после каждой фазы поток увеличивается хотя бы на [math]1[/math]. Если [math]F \gt \sqrt{P}[/math], рассмотрим последнюю фазу, на момент начала выполнения которой поток в сети был меньше, чем [math]F - \sqrt{P}[/math]. После этого потребуется не больше [math]\sqrt{P}[/math] фаз, чтобы найти максимальный поток. На предыдущей фазе поток ([math]f[/math]) в [math]N[/math] был не больше [math]F-\sqrt{P}[/math], таким образом [math]F-|f| \geqslant \sqrt{P}[/math]. [math]G_f[/math] — сеть с максимальным потоком [math]F-|f|[/math] и потенциалом [math]P[/math] (по Лемме(2)). Поэтому можно воспользоваться Леммой(1), чтобы оценить расстояние между [math]s[/math] и [math]t[/math] в [math]G_f[/math], и получить оценку длины [math]l[/math] слоистой сети: [math]l \leqslant \dfrac{P}{F-|f|} + 1[/math] Так как каждая фаза увеличивает длину слоистой сети минимум на один, то осуществляется не больше [math]\sqrt{P}[/math] фаз. Таким образом происходит не более [math]2\sqrt{P}[/math] фаз.

[math]\triangleleft[/math]

Лемма (3):

Пусть в сети [math]N[/math] нет параллельных рёбер. Пусть [math]F[/math] — максимальный поток в [math]N[/math]. Тогда расстояние [math]l[/math] между [math]s[/math] и [math]t[/math] в [math]N[/math] таково: [math]l \leqslant |V|\sqrt{\dfrac{2C}{F}} - 1[/math].

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

[math]\triangleright[/math]

Обозначим [math]V_i[/math] как набор вершин на расстоянии [math]i[/math] от [math]s[/math]. Множества [math]X = \bigcup\limits_{i = 0}^k V_i[/math] и [math]Y = V - X[/math] определяют разрез [math](X, Y)[/math]. Пропускная способность этого разреза не больше [math]2C|V_k||V_{k + 1}|[/math], так как все рёбра между [math]X[/math] и [math]Y[/math] также являются рёбрами между [math]V_k[/math] и [math]V_{k+1}[/math] и не более чем двумя параллельными рёбрами, исходящими из какой-то вершины в остаточной сети. По теореме о максимальном потоке/минимальном разрезе, [math]F \leqslant 2C|V_k||V_{k+1}|[/math]. Таким образом [math]F[/math] ограничен наименьшим из [math]|V_k||V_{k+1}|[/math]. Но эта величина максимальна, когда [math]|V_i| = \dfrac{|V|}{(l+1)}[/math] для [math]0 \leqslant i \leqslant n[/math], таким образом [math]F \leqslant 2C\dfrac{|V|^2 }{ (l+1)^2}[/math], из чего следует необходимое неравенство.

[math]\triangleleft[/math]

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

Число итераций алгоритма Диница с целочисленными пропускными способностями — [math]O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})[/math].

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

[math]\triangleright[/math]

Если [math]F \leqslant C^{\frac{1}{3}}|V|^{\frac{2}{3}}[/math], то теорема очевидна. Положим, что [math]F \gt C^{\frac{1}{3}}|V|^{\frac{2}{3}}[/math], и рассмотрим последнюю фазу, в которой поток [math]f[/math] не превышает [math]F - C^{\frac{1}{3}}|V|^{\frac{2}{3}}[/math]. В этот момент осталось не более [math]C^{\frac{1}{3}}|V|^{\frac{2}{3}} + 1[/math] фаз, и [math]G_f[/math] — сеть с максимальным потоком [math]F - |f| \geqslant C^{\frac{1}{3}}|V|^{\frac{2}{3}}[/math]. Мы можем применить Лемму(3), чтобы оценить длину [math]l[/math] слоистой сети, и, соответственно, количество выполненных фаз: [math]l \leqslant |V|{\left(\dfrac{2C}{F-|f|}\right)}^{\frac{1}{2}} - 1 \leqslant 2^{\frac{1}{2}}C^{\frac{1}{3}}|V|^{\frac{2}{3}} - 1[/math]. Таким образом, прошло [math]O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})[/math] фаз, и [math]O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})[/math] фаз осталось.

[math]\triangleleft[/math]

См. также

• Схема алгоритма Диница

Источники информации

• On the efficiency of Maximum-Flow Algorithms on Networks with Small Integer Capacities. David Fernandez-Baca and Charles U.Martel
• Андрей Станкевич: Лекториум, дополнительные главы алгоритмов, лекция 12