223
правки
Изменения
Нет описания правки
Число <tex>f(v,w)</tex> можно интерпретировать, например, как количество жидкости, поступающей из <tex>v</tex> в <tex>w</tex> по дуге <tex>(v,w)</tex>. С этой точки зрения значение <tex>f(v-)</tex> может быть интерпретировано как поток, втекающий в вершину <tex>v</tex>, а <tex>f(v+)</tex> - вытекающий из <tex>v</tex>.
Условие 1) называется условием ограничения по пропускной способности, а условие 2) - условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину <tex>v</tex>, отличную от <tex>s</tex> или <tex>t</tex>, равен вытекающему из неё потоку.
== Пример ==
Вот пример сети с источником <tex>s</tex> и стоком <tex>t</tex>.
[[Файл:Flow-network.jpg]]
Первое число означает величину потока, второе - пропускную способность ребра. Обратите внимание, что сумма входящих ребер везде (кроме источника и стока) равна сумме исходящих. Кроме того, величина потока никогда не превышает пропускную способность ребра.
== Литература ==
