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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 32: Строка 32:
  
 
Длинные фазы:
 
Длинные фазы:
Число длинных фаз <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>\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>O(\frac{c(G)}{k})</tex>.

Версия 08:41, 15 декабря 2011

Лемма:
Пусть [math]f[/math] - блокирующий поток в сети [math]G[/math]. [math]s[/math], [math]t[/math] - исток и сток, соответственно. Тогда [math]\rho_{G}(s, t) \lt \rho_{G_{f}}(s, t)[/math].


Определение:
В графе [math]G[/math], в котором [math]s[/math], [math]t[/math] - исток и сток, соответственно.

Для [math]v[/math] - вершины, не являющейся истоком или стоком:

[math]c^{+}(v) = \sum\limits_{uv \in E} c_{uv}[/math].

[math]c^{-}(v) = \sum\limits_{vu \in E} c_{vu}[/math].

[math]c^{+}(s) = +\infty[/math]. [math]c^{-}(t) = +\infty[/math].

[math]c(v) = min(c^{+}(v), c^{-}(v))[/math].

[math]c(G) = \sum\limits_{v \in V}c(v)[/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].