6
правок
Изменения
→Пример: Величина потока - сумма потока из источника.
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> (закон сохранения потока).
[[Файл:Flow-network.png|340px|center]]
Первое число означает величину потока, второе {{---}} пропускную способность ребра. Отрицательные величины потока не указаны (так как они мгновенно получаются из антисимметричности: <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>).
== Источники информации ==
