272
правки
Изменения
→Оценка сложности
<tex> \forall u \in A, v \in \overline{A} \colon c_1(u, v) \leq 1 </tex>.
Рассмотрим максимальный поток <tex> f'_1 </tex> в графе <tex> G_1 </tex>. <tex> \langle A, \overline{A} \rangle </tex> — [[Разрез,_лемма_о_потоке_через_разрез|разрез]], значит:<tex> |f'_1| = f'_1(A, \overline{A}) \leq c(A, \overline{A}) \leq E , f_1 = f_0 + f'_1 </tex>.Пропускная способность каждого дополняющего пути не меньше <tex> 1 </tex>, а поиск каждого занимает <tex> O(E) </tex>времени. Значит, итоговое время работы — <tex> O(E^2) </tex>, q.e.d.
}}
