Guliash's blog

By Guliash, 9 years ago, In Russian

Начал изучать потоки.

Пусть есть транспортная сеть 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)? Или я вообще спрашиваю глупость?=)

  • Vote: I like it
  • 0
  • Vote: I do not like it