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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(не показано 25 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
==Обозначения==
 +
Введём следующие обозначения:
 +
* <tex>N = (V,E,s,t,c)</tex> {{---}} [[Определение сети, потока|сеть]] с целочисленными пропускными способностями,
 +
* обозначим <tex>C =  \max\limits_{uv \in E} c_{uv}</tex> и <tex>F</tex> как максимальный поток,
 +
*<tex>c^{+}(v) = \sum\limits_{uv \in E} c_{uv}</tex>,
 +
*<tex>c^{-}(v) = \sum\limits_{vu \in E} c_{vu}</tex>,
 +
*<tex>p(v) = \min(c^{+}(v), c^{-}(v))</tex> {{---}} потенциал вершины <tex>v</tex>,
 +
*<tex>P = \sum\limits_{v \in V, v \neq s,t}p(v)</tex> {{---}} общий потенциал,
 +
*<tex>G_f</tex> {{---}} [[Дополняющая сеть, дополняющий путь|остаточная сеть]].
 +
 +
==Теоремы==
 
{{Лемма
 
{{Лемма
|statement=Пусть <tex>f</tex> - блокирующий поток в сети <tex>G</tex>. <tex>s</tex>, <tex>t</tex> - исток и сток, соответственно. Тогда <tex>\rho_{G}(s, t) < \rho_{G_{f}}(s, t)</tex>.
+
|about = 1
}}
+
|statement=
 +
Пусть <tex>l</tex> {{---}} расстояние между <tex>s</tex> и <tex>t</tex> в исходной сети, максимальный поток в этой сети равен <tex>F</tex>.  
  
{{Определение
+
Тогда <tex>l \leqslant \dfrac{P}{F} + 1</tex>.
|definition=
 
В графе <tex>G</tex>, в котором <tex>s</tex>, <tex>t</tex> - исток и сток, соответственно.
 
Для <tex>v</tex> - вершины, не являющейся истоком или стоком:
 
  
<tex>c^{+}(v) = \sum\limits_{uv \in E} c_{uv}</tex>.
+
|proof=
 +
Пусть <tex>l</tex> {{---}} расстояние между <tex>s</tex> и <tex>t</tex>, а <tex>V_i</tex> {{---}} набор вершин, удаленных от <tex>s</tex> на <tex>i</tex> <tex>(i \leqslant l)</tex>.
 +
<tex>V_i</tex> {{---}} разъединяющее множество узлов: при его удалении исчезают все пути из <tex>s</tex> в <tex>t</tex>.  
 +
Следуя закону [[Определение сети, потока|сохранения потока]], если <tex>f</tex> обозначить как любой допустимый поток, то <tex>|f|</tex> единиц потока должно проходить через <tex>V_i</tex>.
 +
Но суммарное количество потока, которое может проходить через любую вершину не превосходит её потенциала.
 +
Отсюда, если обозначить <tex>P_i</tex> как общий потенциал вершин из <tex>V_i</tex>, то мы имеем:
  
<tex>c^{-}(v) = \sum\limits_{vu \in E} c_{vu}</tex>.
+
<tex>|f| \leqslant P_i</tex>
  
<tex>c^{+}(s) = +\infty</tex>. <tex>c^{-}(t) = +\infty</tex>.
+
для любого допустимого потока <tex>f</tex>. В частности, <tex>F \leqslant P_i</tex>, таким образом получаем:
  
<tex>c(v) = min(c^{+}(v), c^{-}(v))</tex>.
+
<tex>(l - 1)F \leqslant \displaystyle \sum_{i = 1}^{l - 1} P_i \leqslant P</tex>
 +
}}
  
<tex>c(G) = \sum\limits_{v \in V}c(v)</tex>.
+
{{Лемма
 +
|about = 2
 +
|statement=
 +
Пусть <tex> N </tex> {{---}} сеть, а <tex>f</tex> {{---}} допустимый поток в этой сети. Тогда общий потенциал в остаточной сети <tex>G_f</tex> равен общему потенциалу <tex>N</tex>.
 +
|proof=
 +
По [[Теорема_о_декомпозиции | теореме о декомпозиции]] поток можно разбить на множество простых путей из <tex>s</tex> в <tex>t</tex> и циклов. Рассмотрим каждый путь (цикл) и убедимся, что, пуская по нему поток <tex>f_i</tex>, потенциал вершины не изменится. Действительно, рассмотрим вершину <tex>v</tex>, поток <tex>f_i</tex> в неё течёт по ребру <tex>uv</tex>, а из неё по ребру <tex>vw</tex>. Пусть <tex>c_{f_i}</tex> {{---}} функция пропускных способностей в остаточной сети после пропускания потока по <tex>i</tex>-ому пути (циклу).  Рассмотрим <tex>c^+_{f_1}(v) = c_{f_1}(uv) + c_{f_1}(wv)</tex>. <tex>c_{f_1}(uv) = c(uv) - f_i</tex>, а <tex>c_{f_1}(wv) = c(wv) + f_i</tex>, сложив эти два значения, получим, что <tex>c^+(v)</tex> остаётся неизменной. Применив такое же рассуждение для <tex>c^-(v)</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 \leqslant \sqrt{P}</tex>, так как после каждой фазы поток увеличивается хотя бы на <tex>1</tex>. Если <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| \geqslant \sqrt{P}</tex>.
  
1). Короткие фазы - когда <tex>\rho(s, t) \leq k</tex>.
+
<tex>G_f</tex> {{---}} сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому можно воспользоваться Леммой(1), чтобы оценить расстояние между <tex>s</tex> и <tex>t</tex> в <tex>G_f</tex>, и получить оценку длины <tex>l</tex> слоистой сети:
  
2). Длинные фазы - когда <tex>\rho(s, t) > k</tex>.
+
<tex>l \leqslant \dfrac{P}{F-|f|} + 1</tex>
  
Коротких фаз - <tex>O(k)</tex> штук, т.к. после каждой итерации <tex>\rho(s, t)</tex> увеличивается, но не может быть больше <tex>k</tex>.
+
Так как каждая фаза увеличивает длину слоистой сети минимум на один, то осуществляется не больше <tex>\sqrt{P}</tex> фаз. Таким образом происходит не более <tex>2\sqrt{P}</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> вершин.)
+
|about = 3
 
+
|statement=
Получается, что число длинных фаз - <tex>O(\frac{c(G)}{k})</tex>.
+
Пусть в сети <tex>N</tex> нет [[Основные определения теории графов#def1|параллельных рёбер]]. Пусть <tex>F</tex> {{---}} максимальный поток в <tex>N</tex>. Тогда расстояние <tex>l</tex> между <tex>s</tex> и <tex>t</tex> в <tex>N</tex> таково: <tex>l \leqslant |V|\sqrt{\dfrac{2C}{F}} - 1</tex>.
 
+
|proof=
Давайте возьмём <tex>k = \sqrt{c(G)}</tex>.
+
Обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множества <tex>X = \bigcup\limits_{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 \leqslant 2C|V_k||V_{k+1}|</tex>.
 
+
Таким образом <tex>F</tex> ограничен наименьшим из <tex>|V_k||V_{k+1}|</tex>. Но эта величина максимальна, когда <tex>|V_i| = \dfrac{|V|}{(l+1)}</tex> для <tex>0 \leqslant i \leqslant n</tex>, таким образом <tex>F \leqslant 2C\dfrac{|V|^2 }{ (l+1)^2}</tex>, из чего следует необходимое неравенство.
Получим, что количество фаз - <tex>O(\sqrt{c(G)})</tex>.
 
 
 
А, значит, что количество итераций тоже - <tex>O(\sqrt{c(G)})</tex>.
 
 
}}
 
}}
  
Строка 46: Строка 64:
 
|id=th2
 
|id=th2
 
|about=Вторая теорема Карзанова
 
|about=Вторая теорема Карзанова
|statement=Число итераций алгоритма Диница в сети <tex>G</tex> (<tex>s</tex>, <tex>t</tex> - исток и сток, соответственно.) с целочисленными пропускными способностями меньше <tex>c_{max}</tex> - <tex>O(\sqrt[3]{{|V|}^2 c_{max}})</tex>.
+
|statement=Число итераций алгоритма Диница с целочисленными пропускными способностями {{---}} <tex>O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})</tex>.
 +
|proof=
 +
Если <tex>F \leqslant C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>, то теорема очевидна.
 +
Положим, что <tex>F > C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>, и рассмотрим последнюю фазу, в которой поток <tex>f</tex> не превышает <tex>F - C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>. В этот момент осталось не более <tex>C^{\frac{1}{3}}|V|^{\frac{2}{3}} + 1</tex> фаз, и <tex>G_f</tex> {{---}} сеть с максимальным потоком <tex>F - |f| \geqslant C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>. Мы можем применить Лемму(3), чтобы оценить длину <tex>l</tex> слоистой сети, и, соответственно, количество выполненных фаз:
 +
 
 +
<tex>l \leqslant |V|{(\dfrac{2C}{F-|f|})}^{\frac{1}{2}} - 1 \leqslant 2^{\frac{1}{2}}C^{\frac{1}{3}}|V|^{\frac{2}{3}} - 1</tex>.
 +
 
 +
Таким образом, прошло <tex>O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})</tex> фаз, и <tex>O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})</tex> фаз осталось.  
 
}}
 
}}
 +
 +
== См. также ==
 +
*[[Схема алгоритма Диница]]
 +
 +
== Источники информации ==
 +
* [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]
 +
* [https://www.youtube.com/watch?v=sEwp5ZAJJps&feature=youtu.be&t=26m41s Андрей Станкевич: Лекториум, дополнительные главы алгоритмов, лекция 12]
 +
 +
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Задача о максимальном потоке]]

Версия 17:46, 21 января 2017

Обозначения

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

  • [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|{(\dfrac{2C}{F-|f|})}^{\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]

См. также

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