Изменения
→Суть
== Суть ==
Этот алгоритм работает в предположении, что все пропускные способности ребер целые. Пусть у нас есть граф <tex>G</tex>, <tex>\forall (u,v)\in E: u_{(u,v)}\in\mathbb N</tex>. Пусть <tex>U</tex> - максимальная пропускная способность. Тогда запишем пропускную способность каждого ребра в двоичной записи, выделив для каждого ребра <tex>n:=\lfloor\log U\rfloor+1</tex> памяти. Занумеруем биты с младшего (0-ой) по старший (n-ный). Тогда<br>
<tex>\forall (u,v)\in E:c(u,v)=2^n*a_n(u,v)+...+2*a_1(u,v)+a_0(u,v); a_i(u,v)\in\{0,1\}</tex>
