79
правок
Изменения
м
Нет описания правки
2) <tex>f(v-) = f(v+)</tex> для всех <tex>v\in V, v\ne s, v\ne t</tex>, где <tex>f(v-)=\sum\limits_{w\in v-} f(w,v), f(v+)=\sum\limits_{w\in v+} f(v,u)</tex>.
Здесь <tex>s - </tex>'''источник''', а <tex>t - </tex>'''сток''' сети <tex>G</tex> (<tex>s</tex> имеет нулевую степень захода, а <tex>t</tex> имеет нулевую степень исхода); через <tex>v+</tex> обозначено множество вершин, к которым идут [[Основные определения теории графов#def_graph_edge_1|дуги]] из вершины <tex>v</tex>; через <tex>v-</tex> обозначено множество вершин, из которых идут дуги в вершину <tex>v</tex>; <tex>c(e)</tex> называется '''пропускной способностью''' дуги <tex>e</tex> и неотрицательно.
}}
Число <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>-</tex> условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину <tex>v</tex>, отличную от <tex>s</tex> или <tex>t</tex>, равен вытекающему из неё потоку.
== Пример ==
