Изменения
→Определение потока
1) <tex>f(u,v)=-f(v,u)</tex> (антисимметричность);
2) <tex>|f(u,v)| \leqslant c(u,v)</tex> (ограничение пропускной способности), если ребра нет, то <tex>f(u,v)=0</tex>;
3) <tex>\sum\limits_v f(u,v)=0</tex> для всех вершин <tex>u</tex>, кроме <tex>s</tex> и <tex>t</tex> (закон сохранения потока).
1) <tex>0 \leqslant f(e) \leqslant c(e)</tex> для всех <tex>e\in E</tex>;
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,uw)</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(u,v)=-f(v,u)</tex>). Сумма входящих рёбер везде (кроме источника и стока) равна сумме исходящих и на то, что в общем <tex>c(u,v) \neq c(v, u)</tex>. Кроме того, величина потока на ребре никогда не превышает пропускную способность этого ребра.
Величина потока в этом примере равна <tex> 5 3 + 2 = 7 5 </tex> (считаем от вершины <tex>s</tex>).
== Источники информации ==
