79
правок
Изменения
м
Нет описания правки
1) <tex>f(u,v)=-f(v,u)</tex> (антисимметричность);
2) <tex>f(u,v)\leqslant c(u,v)</tex> (ограничение пропускной способности), если ребра нет, то <tex>c(u,v)=0</tex>;0
3) <tex>\sum\limits_v f(u,v)=0</tex> для всех вершин <tex>u</tex>, кроме <tex>s</tex> и <tex>t</tex> (закон сохранения потока).
'''Величина''' потока <tex>f</tex> определяется как <tex>|f|=\sum\limits_{v\in V} f(s,v)</tex>.
|definition=
'''Потоком''' <tex>f</tex> в сети <tex>G=(V,E,c)</tex> называется функция <tex>f\colon E\to R</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,u)</tex>.
