Rambler's Top100





7
2. ОПРЕДЕЛЕНИЕ ПОТОКА. ЛЕММА О ПОТОКЕ
Определение 1
1) Сетью будем называть орграф без петель и кратных ребер.
2) Пусть дан орграф
)E,V(G
, зафиксированы две вершины
(
s
источник,
t
сток), и дана рѐберная функция
RE:)y,x(c
, на-
зываемая пропускной способностью. Тогда
))y,x(c,t,s,E,V(G
назы-
вается сетью с двумя выделенными вершинами
t,s
и пропускной спо-
собностью на дугах.
Определение 2
Дана сеть
))y,x(c,t,s,E,V(G
. Рѐберная функция
)y,x(f
назы-
вается потоком мощности
v
на сети, если выполняются условия:
1) для любого ребра
)b,a(
сети
G
)b,a(c)b,a(f0
;
2)
.tx,v
;t,sx,
;sx,v
)x,V(f)V,x(f
0
v)s,V(f)V,s(f
чистый вывоз,
v)t,V(f)V,t(f
чистый ввоз.
Если дан поток f, то число
)y,x(f
называют дуговым потоком или
потоком по дуге
)y,x(
.
Пример
4,4
s
4,2
2,2
2,1
2,1
2,1
2,1
1,1
1,1
3,1
Каждой дуге соответствует два числа: первое значение функции
пропускной способности, второе дуговой поток. Мощность потока
4v
.