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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
|about = 1
 
|about = 1
 
|statement=
 
|statement=
Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex> в сети с текущим потоком, равным 0, и максимальным потоком, равным <tex>F</tex>.  
+
Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex> в слоистой сети с текущим потоком, равным 0, и максимальным потоком, равным <tex>F</tex>.  
  
 
Тогда <tex>l \leq \frac{P}{F} + 1</tex>
 
Тогда <tex>l \leq \frac{P}{F} + 1</tex>
Строка 41: Строка 41:
 
|about = 2
 
|about = 2
 
|statement=
 
|statement=
Пусть <tex>N</tex> - сеть, а <tex>f</tex> - допустимый поток в этой сети. Тогда общий потенциал в остаточной сети <tex>N(f)</tex> равен общему потенциалу <tex>N</tex>.
+
Пусть <tex> N </tex> - сеть, а <tex>f</tex> - допустимый поток в этой сети. Тогда общий потенциал в остаточной сети <tex>N(f)</tex> равен общему потенциалу <tex>N</tex>.
 
|proof=
 
|proof=
Пусть <tex>с_а</tex> - функция пропускных способностей в <tex>N(f)</tex>, а <tex>p_f(v), in_f(v), out_f(v)</tex>
+
Пусть <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.  
 
|id=th1.  
 
|about=Первая теорема Карзанова
 
|about=Первая теорема Карзанова
|statement=Число итераций алгоритма Диница в сети <tex>G</tex> (<tex>s</tex>, <tex>t</tex> - исток и сток, соответственно.) с целочисленными пропускными способностями - <tex>O(\sqrt{c(G)})</tex>.
+
|statement=Число итераций алгоритма Диница в сети <tex>N</tex> (<tex>s</tex>, <tex>t</tex> - исток и сток, соответственно.) с целочисленными пропускными способностями - <tex>O(\sqrt{P})</tex>.
|proof=Разобьём все итерации на 2 группы:
+
|proof=
 
+
Пусть <tex>F</tex> - максимальный поток в сети <tex>N</tex>. Теорема верна для <tex>F \leq \sqrt{P}</tex>, так как после каждой фазы поток увеличивается хотя бы на 1. Если <tex>F > \sqrt{P}</tex>, рассмотрим последнюю фазу, на момент выполнения которой поток в сети меньше, чем <tex>F - \sqrt{P}</tex>. После этого потребуется не больше <tex>\sqrt{P}</tex> фаз, чтобы найти максимальынй поток. На предыдущей фазе поток (<tex>f</tex>) в <tex>N</tex> был не больше <tex>F-\sqrt{P}</tex>, таким образом <tex>F-|f| \leq \sqrt{P}</tex>.
1). Короткие фазы - когда <tex>\rho(s, t) \leq k</tex>.
 
 
 
2). Длинные фазы - когда <tex>\rho(s, t) > k</tex>.
 
 
 
Коротких фаз - <tex>O(k)</tex> штук, т.к. после каждой итерации <tex>\rho(s, t)</tex> увеличивается, но не может быть больше <tex>k</tex>.
 
 
 
Длинные фазы:
 
Число длинных фаз <tex>\leq</tex> количество путей из <tex>s</tex> в <tex>t</tex> длины  больше <tex>k</tex> <tex> \leq \frac{\sum\limits_{v \in V} c(v)}{k} = \frac{c(G)}{k}</tex>. (т.к. через вершину <tex>v</tex> не может пройти больше <tex>c(v)</tex> путей, а на каждом пути лежит <tex>\geq k</tex> вершин.)
 
 
 
Получается, что число длинных фаз - <tex>O(\frac{c(G)}{k})</tex>.
 
  
Давайте возьмём <tex>k = \sqrt{c(G)}</tex>.
+
<tex>N(f)</tex> - сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому мы можем использовать Лемму(1) чтобы оценить расстояние между <tex>s</tex> и <tex>t</tex> в <tex>N(f)</tex>. Отсюда получаем оценку длины (<tex>l</tex>) слоистой сети:
  
Получим, что количество фаз - <tex>O(\sqrt{c(G)})</tex>.
+
<tex>l \leq \frac{P}{F-|f|} + 1</tex>
  
А, значит, что количество итераций тоже - <tex>O(\sqrt{c(G)})</tex>.
+
Так как каждая фаза увеличивает длину слоистой сети минимум на один,то осуществляется не больше <tex>\sqrt{P}</tex> фаз. Таким образом происходит не более <tex>2\sqrt{P}</tex> фаз.
 
}}
 
}}
  

Версия 03:41, 25 декабря 2011

Определение:
Пусть [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]c_f[/math] - функция пропускных способностей в [math]N(f)[/math], а [math]p_f(v), in_f(v), out_f(v)[/math] - потенциал, множество входящих ребер и множество выходящих ребер вершины [math]v[/math] из [math]N(f)[/math].

Достаточно доказать, что [math]p_f(v) = p(v)[/math]. Ребру [math]e[/math] из [math]in(v)[/math] соответствуют ребро [math]e_1[/math] из [math]in_f(v)[/math] с пропускной способностью [math]c(e) - f(e)[/math], и ребро [math]e_2[/math] из [math]out_f(v)[/math] с пропускной способностью [math]f(e)[/math]. Аналогично, ребру [math]e[/math] из [math]out(v)[/math] соответствуют ребра из [math]out_f(v)[/math] с пропускной способностью [math]c(v) - f (v)[/math] и [math]in_f(v)[/math] с пропускной способностью [math]f(e)[/math]. Используя правило сохранения потока, нетрудно проверить, что

[math]\displaystyle\sum_{e\in in_f(v)} c_f(e) = \sum_{e\in in(v)}c(e)[/math]

и

[math]\displaystyle\sum_{e\in out_f(v)} c_f(e) = \sum_{e\in out(v)}c(e)[/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 \leq \sqrt{P}[/math], так как после каждой фазы поток увеличивается хотя бы на 1. Если [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| \leq \sqrt{P}[/math].

[math]N(f)[/math] - сеть с максимальным потоком [math]F-|f|[/math] и потенциалом [math]P[/math] (по Лемме(2)). Поэтому мы можем использовать Лемму(1) чтобы оценить расстояние между [math]s[/math] и [math]t[/math] в [math]N(f)[/math]. Отсюда получаем оценку длины ([math]l[/math]) слоистой сети:

[math]l \leq \frac{P}{F-|f|} + 1[/math]

Так как каждая фаза увеличивает длину слоистой сети минимум на один,то осуществляется не больше [math]\sqrt{P}[/math] фаз. Таким образом происходит не более [math]2\sqrt{P}[/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].