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

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


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

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

[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].


Теорема (Первая теорема Карзанова):
Чило итераций алгоритма Диница в сети G с целочисленными пропускными способностями - [math]O(\sqrt{c(G)})[/math].
Доказательство:
[math]\triangleright[/math]
доказательство (необязательно)
[math]\triangleleft[/math]