| |
Пускай каждой дуге (х,у)
сети G[N,A]
сопоставлено некоторое неотрицательное число С(х,у), называемое пропускной
способностью.
Сетью называется граф без
циклов и петель, ориентированный в одном общем направлении от вершин
U,
являющихся входами графа к вершинам
W
- выходам графа.
Транспортная сеть - это
сеть, характеризующаяся тремя признаками:
1)
имеется только один вход
2)
имеется только один выход
3)
каждой дуге сопоставлено число С(х,у).
С транспортной сетью тесно
связано понятие потока в сети.
Потоком
f
величины v
в сети G(E,Г,С)
из источника S
в сток T
называется действительная положительная функция, удовлетворяющая следующим
условиям:
1)
0<=f(x,y)<=C(x,y)
для любых(х,у), принадлежащих
G.
2)
f(x,E)-f(E,x)=0
для любого х из G,
х<>s,x<>t.
Сколько в узел втекло, столко и вытекло.
3)
f(S,E)-f(E,s)=v
4)
f(t,E)-f(E,t)=-v.
|
|