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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теоремы)
Строка 19: Строка 19:
 
}}
 
}}
 
==Теоремы==
 
==Теоремы==
Идея доказательства следующая. Сперва мы
 
получим оценку длины слоистой сети с точки зрения величины максимального потока и другого интересующего нас
 
параметра(здесь мы рассматриваем P и C). Эта оценка будет возрастающей функцией интересующего параметра
 
и убывающей функцией от максимального потока. Мы разобьем вычисление максимального потока на 2 части.
 
В первой мы предполагаем, что поток достиг величины, находящейся в пределах <tex>\bar{F}</tex> от оптимального. Таким образом, потребуется
 
не больше <tex>\bar{F}</tex> дополнительных фаз перед завершением. В этом и состоит вторая часть вычислений. Теперь используем
 
оценку длины слоистой сети чтобы опредлить предел количества фаз, осуществляемых в 1 части.
 
<tex>\bar{F}</tex> выбрано так, что оно такого же порядка, что и длина слоистой сети в конце 1 части вычислений.
 
Таким образов количество фаз <tex>O(\bar{F})</tex>.
 
 
 
{{Лемма
 
{{Лемма
 
|about = 1
 
|about = 1
Строка 38: Строка 28:
 
|proof=
 
|proof=
 
Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex>, а <tex>V_i</tex> - набор вершин, удаленных от <tex>s</tex> на <tex>i</tex> <tex>(i \leq l)</tex>.  
 
Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex>, а <tex>V_i</tex> - набор вершин, удаленных от <tex>s</tex> на <tex>i</tex> <tex>(i \leq l)</tex>.  
<tex>V_i</tex> - разъединяющее множество узлов: при его удалении исчезают все направлнные пути из <tex>s</tex> в <tex>t</tex>.  
+
<tex>V_i</tex> - разъединяющее множество узлов: при его удалении исчезают все пути из <tex>s</tex> в <tex>t</tex>.  
 
Следуя правилу сохранения потока, если <tex>f</tex> обозначить как любой допустимый поток, то <tex>|f|</tex> единиц потока должно проходить через <tex>V_i</tex>.
 
Следуя правилу сохранения потока, если <tex>f</tex> обозначить как любой допустимый поток, то <tex>|f|</tex> единиц потока должно проходить через <tex>V_i</tex>.
 
Но суммарное количество потока, которое может проходить через любую вершину не превосходит ее потенциала.  
 
Но суммарное количество потока, которое может проходить через любую вершину не превосходит ее потенциала.  
Строка 69: Строка 59:
 
что и требовалось доказать.
 
что и требовалось доказать.
 
}}
 
}}
 
 
{{Теорема
 
{{Теорема
 
|id=th1.  
 
|id=th1.  
Строка 77: Строка 66:
 
Пусть <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>.
 
Пусть <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>.
  
<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>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>l \leq \frac{P}{F-|f|} + 1</tex>
 
<tex>l \leq \frac{P}{F-|f|} + 1</tex>
Строка 87: Строка 76:
 
|about = 3
 
|about = 3
 
|statement=
 
|statement=
Пусть в сети <tex>N</tex> нет параллельных ребер. <tex>f</tex> - поток в <tex>N</tex>, а <tex>F</tex> - максимальный поток в <tex>N(f)</tex>. Тогда расстояние <tex>l</tex> между <tex>s</tex> и <tex>t</tex> в <tex>N(f)</tex> таково: <tex>l \leq |V|\sqrt{\frac{2C}{F}} - 1</tex>.
+
Пусть в сети <tex>N</tex> нет [[Основные определения теории графов|параллельных ребер]]. <tex>f</tex> - поток в <tex>N</tex>, а <tex>F</tex> - максимальный поток в <tex>N(f)</tex>. Тогда расстояние <tex>l</tex> между <tex>s</tex> и <tex>t</tex> в <tex>N(f)</tex> таково: <tex>l \leq |V|\sqrt{\frac{2C}{F}} - 1</tex>.
 
|proof=
 
|proof=
 
Как и раньше, обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множество <tex>X = \bigcup_{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 \leq 2C|V_k||V_{k+1}|</tex>.
 
Как и раньше, обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множество <tex>X = \bigcup_{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 \leq 2C|V_k||V_{k+1}|</tex>.
Строка 99: Строка 88:
 
|proof=
 
|proof=
 
Если <tex>F \leq C^{1/3}|V|^{2/3}</tex>, то теорема очевидна.  
 
Если <tex>F \leq C^{1/3}|V|^{2/3}</tex>, то теорема очевидна.  
Положим, что <tex>F > C^{1/3}|V|^{2/3}</tex>, и рассотрим последнбб фазу, в которой поток <tex>f</tex> не превышает <tex>F - C^{1/3}|V|^{2/3}</tex>. В этот момент осталось не более <tex>C^{1/3}|V|^{2/3} + 1</tex> фаз, и <tex>N(f)</tex> - сеть с максимальным потоком <tex>F - |f| \ge C^{1/3}|V|^{2/3}</tex>. Мы можем применить Лемму(2), чтобы оценить длину <tex>l</tex> слоистой сети, и, соответственно, количество выполненных фаз:
+
Положим, что <tex>F > C^{1/3}|V|^{2/3}</tex>, и рассотрим последнюю фазу, в которой поток <tex>f</tex> не превышает <tex>F - C^{1/3}|V|^{2/3}</tex>. В этот момент осталось не более <tex>C^{1/3}|V|^{2/3} + 1</tex> фаз, и <tex>N(f)</tex> - сеть с максимальным потоком <tex>F - |f| \ge C^{1/3}|V|^{2/3}</tex>. Мы можем применить Лемму(2), чтобы оценить длину <tex>l</tex> слоистой сети, и, соответственно, количество выполненных фаз:
  
 
<tex>l \leq |V|{(\frac{2C}{F-|f|})}^{1/2} - 1 </tex>
 
<tex>l \leq |V|{(\frac{2C}{F-|f|})}^{1/2} - 1 </tex>
Строка 109: Строка 98:
  
 
== Литература ==
 
== Литература ==
* On the efficiency of Maximum-Flow Algorithms on Networks with Small Integer Capacities. David Fernandez-Baca and Charles U.Martel
+
* [http://www.springerlink.com/content/w0q006u3631gg124/fulltext.pdf On the efficiency of Maximum-Flow Algorithms on Networks with Small Integer Capacities. David Fernandez-Baca and Charles U.Martel]

Версия 20:29, 30 декабря 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].

Остаточную сеть обозначим [math]N(f)[/math].

Обозначим длину слоистой сети [math]l[/math] - как длину кратчайшего [math]s-t[/math] пути в [math]N(f)[/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(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]
Лемма (3):
Пусть в сети [math]N[/math] нет параллельных ребер. [math]f[/math] - поток в [math]N[/math], а [math]F[/math] - максимальный поток в [math]N(f)[/math]. Тогда расстояние [math]l[/math] между [math]s[/math] и [math]t[/math] в [math]N(f)[/math] таково: [math]l \leq |V|\sqrt{\frac{2C}{F}} - 1[/math].
Доказательство:
[math]\triangleright[/math]

Как и раньше, обозначим [math]V_i[/math] как набор вершин на расстоянии [math]i[/math] от [math]s[/math]. Множество [math]X = \bigcup_{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 \leq 2C|V_k||V_{k+1}|[/math].

Таким образом [math]F[/math] ограничен наименьшим из [math]|V_k||V_{k+1}|[/math]. Но этот минимум максимизируется, когда [math]|V_i| = |V|/(l+1)[/math] для [math]0 \leq i \leq n[/math], таким образом [math]F \leq 2C|V|^2(l+1)^2[/math]. Выражая [math]l[/math] получаем нужное.
[math]\triangleleft[/math]
Теорема (Вторая теорема Карзанова):
Число итераций алгоритма Диница с целочисленными пропускными способностями - [math]O(C^{1/3}|V|^{2/3})[/math].
Доказательство:
[math]\triangleright[/math]

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

[math]l \leq |V|{(\frac{2C}{F-|f|})}^{1/2} - 1 [/math]

[math]\leq 2^{1/2}C^{1/3}|V|^{2/3} - 1[/math].

Таким образом, прошло [math]O(C^{1/3}|V|^{2/3})[/math] фаз, и [math]O(C^{1/3}|V|^{2/3})[/math] фаз осталось. Теорема доказана.
[math]\triangleleft[/math]

Литература