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

Сетью называется граф, элементам которого поставлены в соответст­вие некоторые параметры. Далее элементы множества N будем называть узлами, а множества А - дугами. Пусть каждой дуге некоторой сети G = [N, а] поставлено в соответствие неотрицательное (действительное) число , называемое пропускной способностью дуги . Функ­ция С, отображающая множество А в множество неотрицательных чисел, называется функцией пропускной способности. Пусть s и t - два различных узла из N. Стационарный поток величины v из s в t в сети [N, а] есть функция f, отображающая множество А в множество неотрицательных чисел, удовлетворяющая линейным уравнениям и неравенствам

(4)

для всех , (5)

где («после x»), («перед x»).

Будем называть узел s - источником, узел t - стоком, а остальные уз­лы - промежуточными.

Если дан поток f, то число f(x,y) называется дуговым пото­ком f(x,y) или потоком по дуге (х,у). Поскольку f=0 и v=0 удовлетво­ряют условиям (4) и (5), вопрос о существовании потока не возникает. Система уравнений (4) избыточна, так как складывая все строки ее матри­цы, мы получаем нулевой вектор. Таким образом, не нарушая общности, можно отбросить одно из уравнений системы.

Потоком в сети [N,A] или [N,C] назовем функцию f, сопоставляющую каж­дому ребру (х,у) сети целое число f(x,y) и обладающую следующими свойствами:

(кососимметрия),

(допустимость).

Поиск по сайту: