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

Лемма:

Пусть [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].

Теорема (Первая теорема Карзанова):

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

Доказательство:

[math]\triangleright[/math]

доказательство (необязательно)

[math]\triangleleft[/math]