Отношения между потоками и операции над ними

Задача о максимальном пути

Задача о максимальном пути формулируется следующим образом: в заданной сети N = (V,D,a) с выделенной вершиной v₀ для каждой вершины v V найти (v₀,v)-путь, имеющий максимальную длину среди всех возможных (v₀,v)-путей в сети N.

Отметим, что имеет смысл решать эту задачу лишь в сетях, не содержащих контуров положительной длины. Рассмотрев тогда сеть, отличающуюся от исходной только изменением знаков весов дуг, получим сеть, в которой нет контуров отрицательной длины. Применяя к новой сети алгоритм Форда-Беллмана, можно построить кратчайшие (v₀,v)-пути, которые будут путями максимальной длины в исходной сети.

Потоки в сетях ⁽³⁾

Если мы припишем каждой дуге ориентированного графа поток некоторого вещества, граф становится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с действительным или воображаемым движением товаров, информации или людей.

Для данной сети N = (V,D,a) определим поток через N как функцию, сопоставляющую каждой дуге a из D неотрицательное действительное число (называемое потоком через a) таким образом, что для любой дуги a; по отношению к сети N полустепень исхода и полустепень захода любой вершины (отличной от v и ) равны между собой. Рассуждая неформально, это означает, что поток через любую дугу не превосходит ее пропускной способности и что "полный поток", входящий в любую вершину (отличную от v и ), равен "полному потоку", выходящему из нее. Другим потоком является нулевой поток, при котором поток через каждую дугу равен нулю (любой другой поток называется ненулевым).

Дуга a, для которой , называется насыщенной; остальные дуги называются ненасыщенными.

Направление потока определяется знаком (а).

Вершины сети N обычно классифицируются по их воздействию на поток (создают, поглощают или сохраняют поток). Чтобы формализовать классификацию, обозначим через v V множество дуг, для которых v является начальной вершиной, а через V v —множество дуг, для которых v является конечной вершиной. Тогда целое число Q(v, ), определяемое соотношением

называется чистым потоком из v относительно .

Сеть в целом сохраняет любой поток в том смысле, что . Это хорошо видно из следующего выражения:

т.к. каждая дуга сети входит точно один раз в каждую двойную сумму.

Пусть и — потоки в одной и той же сети N=(V, D), и пусть р — целое число. Тогда для каждой

дуги аD потоки , и определяются с помощью следующих соотношений:

() (а)=(а) + (а),

() (а)= (а) - (а),

(а)=(а).

Легко видеть, что

Q(v,)=Q(v,)Q(v,),

Q(v,)=Q(v, ).

Будем писать <тогда и только тогда, когда (а)<(а) для каждой аD. Отношения между потоками, >иопределяются аналогично. Говорят, что поток ограничен значениями и , если величина (а) заключена между (a) и (а) для каждой дуги сети. Очевидно, что достаточным условием ограниченности потокапотоками и является выполнение одного из следующих соотношений: или . Вообще, по некоторым дугам поток может быть ограничен сверху потоком а по другим — потоком .

Потоки и называются согласованными, если (а)*(а)0 для каждой дуги аV. Другими словами, и согласованы, если не существует дуг а, для которых (а) и (а) отличны от нуля и противоположно направлены. Потоки {,...,} в одной и той же сети называются совместно согласованными, если они попарно согласованы.