}}
== Идея Алгоритм ==Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередьПусть дан [[Основные_определения_теории_графов|граф]] <tex> G </tex>, чтобы сразу сильно увеличивать поток по нимвсе ребра которого имеют целочисленную пропускную способность. Обозначим за <tex> U </tex> максимальную пропускную способность: <tex> U = \max\limits_{(u, v) \in EG} c(u, а затем по всем остальнымv) </tex>.
Пусть дан граф Если записать пропускную способность любого ребра в двоичном виде, то длина полученной битовой последовательности не будет превышать <tex> G \lfloor \log_2 U \rfloor + 1 = n + 1 </tex> с целыми пропускными способностямибит, а значение пропускной способности определяется формулой: <tex> \forall(u, v) \in EG \colon c(u,v) \in \mathbb{Z_+} </tex>.<tex> U = \maxsum\limits_{i = 0}^n a_i(u, v) \in EG} ctimes 2^n, a_i(u, v) </tex> — максимальная пропускная способность. Запишем пропускную способность каждого ребра в двоичном виде. Тогда каждое число будет занимать <tex> \lfloor in \log_2 U {0, 1\rfloor + 1 = n + 1 } </tex> бит.
<tex> c(uИдея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, v) = \sum\limits_{i = 0}^n a_i(uчтобы сразу сильно увеличивать поток по ним, v) \times 2^n, a_i(u, v) \in \{0, 1\} </tex>а затем по всем остальным.
Методом [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Форда-Фалкерсона]] находим поток <tex> f_0 </tex> для графа <tex> G_0 </tex> с урезанными пропускными способностями <tex> c_0(u, v) = a_n(u, v) </tex>.
