Начал изучать потоки.
Пусть есть транспортная сеть G = (V, E). c(u, v) — пропускная способность. Если есть ребро (u, v), то нет (v, u). Исток s, сток t. Для любой вершины v верно то, что она достижима из s, и t достижима из v.
Пусть есть поток на этой сети f.
0 ≤ f(u, v) ≤ c(u, v).
Для любой верно .
То есть всё как в Кормене (3 издание). У меня такой вопрос. Верно ли то, что исходя из ограничений на функцию потока мы не можем пропустить через какое-то ребро (u, v) вещества меньше чем f(u, v). Иными словами, верно ли то, что если мы доставили вещество в сток, то не существует ребра, через которое прошло вещества меньше, чем f(u, v)? Или я вообще спрашиваю глупость?=)