| Определение: |
| Алгоритм масштабирования потока — алгоритм поиска максимального потока, работающий в предположении, что все пропускные способности рёбер целые, так как они легко представимы в двоичном виде. |
Идея
Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать поток по ним, а затем по всем остальным.
Пусть дан граф [math] G [/math] с целыми пропускными способностями: [math] \forall(u, v) \in EG \colon c(u,v) \in \mathbb{Z_+} [/math].
[math] U = \max\limits_{(u, v) \in EG} c(u, v) [/math] — максимальная пропускная способность. Запишем пропускную способность каждого ребра в двоичном виде. Тогда каждое число будет занимать [math] \lfloor \log_2 U \rfloor + 1 = n + 1 [/math] бит.
[math] c(u, v) = \sum\limits_{i = 0}^n a_i(u, v) \times 2^n, a_i(u, v) \in \{0, 1\} [/math]
Методом Форда-Фалкерсона находим поток [math] f_0 [/math] для графа [math] G_0 [/math] с урезанными пропускными способностями [math] c_0(u, v) = a_n(u, v) [/math].
Добавим следующий бит и находим следующее приближение для графа [math] G_1 [/math] с новыми пропускными способностями [math] c_1(u, v) = 2 a_n(u, v) + a_{n - 1}(u, v) - 2 f_0(u, v) [/math].
После [math] n + 1 [/math] итерации получим ответ к задаче.
Оценка сложности
| Утверждение: |
Сложность алгоритма — [math] O(E^2 \log U) [/math]. |
| [math]\triangleright[/math] |
|
Докажем, что сложность каждой итерации — [math] O(E^2) [/math].
| Лемма: |
Сложность первой итерации алгоритма — [math] O(E^2) [/math]. |
| Доказательство: |
| [math]\triangleright[/math] | |
На первом шаге ребра имеют пропускную способность [math] 1 [/math]. Значит, [math] |f_0| \leq V [/math]. Поиск каждого дополнительного пути требует [math] O(E) [/math] времени, а их количество не больше [math] V [/math]. Итоговая сложность первой итерации — [math] O(VE) \leq O(E^2) [/math]. | | [math]\triangleleft[/math] |
| Лемма: |
Сложность второй итерации алгоритма — [math] O(E^2) [/math]. |
| Доказательство: |
| [math]\triangleright[/math] | |
Полужирное начертание
 Разрез [math] \langle A, \overline{A} \rangle [/math]. Докажем оценку для второго шага (для остальных доказательство аналогично).
Граф [math] G_{f_0} [/math] — несвязен. Пусть [math] A [/math] — компонента связности, [math] s \in A, t \in \overline{A} [/math]. Тогда [math] c_{0_{f_0}}(A, \overline{A}) = 0 [/math].
Значит, в графе с пропускными способностями [math] c_1 [/math]:
[math] \forall u \in A, v \in \overline{A} \colon c_1(u, v) \leq 1 [/math].
Рассмотрим максимальный поток [math] f'_1 [/math] в графе [math] G_1 [/math].
[math] \langle A, \overline{A} \rangle [/math] — разрез, значит:
[math] |f'_1| = f'_1(A, \overline{A}) \leq c(A, \overline{A}) \leq E, f_1 = f_0 + f'_1 [/math].
Пропускная способность каждого дополняющего пути не меньше [math] 1 [/math], а поиск каждого занимает [math] O(E) [/math] времени. Значит, итоговое время работы — [math] O(E^2) [/math]. | | [math]\triangleleft[/math] |
Оценка сложности остальных итераций доказывается аналогично второму случаю. Количество итераций — [math] O(\log U) [/math]. Значит, общая сложность алгоритма — [math] O(E^2 \log U) [/math]. |
| [math]\triangleleft[/math] |
Литература
