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

Пусть потоки в одной и той же сети и пусть целое число. Тогда для каждой дуги потоки определяются с помощью следующих соотношений:

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

Отсюда следует, что если потоки из и в имеющие величины соответственно, то также является потоком из и имеет величину Аналогично, есть поток, имеющий величину и направленный от и к если или от к , если (Поток величины нуль можно считать направленным как от к так и от к ) И наконец, поток имеет величину и направлен от если и от к и, если

Упражнение 7.1. (см. скан)

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

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

сети называются совместно согласованными, если они попарно согласованы.

Упражнение 7.2. (см. скан)

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

Теорема 7.1. Если -множество совместно согласованных потоков в сети произвольный поток в то поток ограничен потоками

Доказательство. Пусть а — любая дуга сети. Если для то, очевидно,

Аналогично, если для то

Так как для любой дуги а имеет место одна из этих ситуаций, то теорема доказана.

Упражнение 7.3. (см. скан)