Изменения

Перейти к: навигация, поиск

Алгоритм масштабирования потока

83 байта добавлено, 07:26, 19 декабря 2011
→‎Оценка сложности
<tex> \forall u \in A, v \in \overline{A} \colon c_1(u, v) \leq 1 </tex>.
<tex> \langle A, \overline{A} \rangle </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 </tex>.
}}
Андрей Козлов
272
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/14921»

Навигация