Потоки в сетях

Определение 2.1.1. Пусть – конечное множество узлов сети (). Целочисленная функция называется пропускной способностью сети. Здесь – пропускная способность ребра .

Обозначим через сеть с функцией пропускной способности . Сеть определяется графом , где – множество ребер графа .

Если , то , т. е. ребро в сети отсутствует.

Определение 2.1.2. Потоком в сети называется целочисленная функция , определенная на , если она обладает свойствами:

· Допустимость потока: для любой пары .

· Кососимметричность потока: для любой пары .

Замечание 2.1.1. Рассмотрим произвольное ребро , пусть и , тогда чистый поток из в будет (чистый поток обладает свойством 2).

Замечание 2.1.2. Будем предполагать, что пропускная способность и поток принимают только целочисленные значения.

Пример 2.1.1 (потока).

Рис. 2.1

Дата добавления: 2014-01-07