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

Предположим, что это не так и узел В, получивший постоянную метку на к-м шаге, связывает с узлом Д> кратчайший маршрут, в котором наряду с узлами, имеющими постоянные метки, есть и узлы с временными метками и С - первый такой узел, считая от узла Д> (конечно, отличный от узла В).

Это означает, что существует маршрут из узла Д> в узел С, который проходит только через узлы с постоянными метками и имеет длину меньшую, чем маршрут из узла Д> в узел В, что противоречит выбору узла В (рис. 11).

Рис. 11

3.4. максимальный поток

Изложение начнем с введения некоторых полезных понятий.

Дуга сети называется ориентиро-

►(Л ванн°й> если узлы, которые она соеди-

А -с няет, упорядочены - один из них при-

А нят за начальный, а другой за

Рис. 12 конечный. На рисунках и схемах ори-

ентированная дуга обозначается стрелкой, которая показывает, из какого узла выходит эта дуга и в какой узел входит (рис. 12).

Сеть называется ориентированной, если ориентированы все ее дуги (рис. 13).

Рис. 14

Рис. 13

Узел сети, который является начальным для всех своих дуг (все эти дуги являются выходящими), называют источником, а узел, который является конечным для всех своих дуг (все эти дуги являются входящими), - стоком. Все другие узлы такой сети называются промежуточными.

Припишем каждой дуге ориентированной сети неотрицательное целое число

Cik = c(Ab Лк)>

которое будем называть пропускной

способностью этой дуги, интуитивно Cik /Т\

представляя пропускную способ- *\/

ность как максимально возможное количество продукта (например, жидкости или газа в трубопроводе),

которое может быть доставлено из узла А§ в узел Ак в единицу времени (рис. 14).

Такую сеть нередко называют транспортной [11].

В дальнейшем мы будем считать, что в транспортной сети есть ровно один источник и ровно один сток.

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

Итак, рассмотрим транспортную сеть с одним источником Д> и одним стоком А (рис. 15); Аи Ап-\ - промежуточные узлы.

Будем говорить, что в сети задан поток величины v, если каждой дуге AfAk сети приписано неотрицательное целое число

<Р* =<P(Ai>Ak)

Рис. 15

поток по дуге AfAk9 и при этом выполнены следующие условия:

1) поток по каждой дуге не превосходит ее пропускной способности,

2) сумма потоков по всем дугам, выходящим из источника Aq, равна v,

(здесь символ / Е {А0} означает, что суммирование ведется по всем дугам AoAh выходящим из источника Д>),

3) сумма потоков по всем дугам, входящим в каждый из промежуточных узлов Д>, Ап ь равна сумме потоков по всем дугам, выходящим из этого узла,

<p(At,Ak)=

k = 1, п - 1

(здесь символ i Е {Ак}+ означает, что суммирование ведется по всем дугам, входящим в промежуточный узел Ак, а символ lG{Ak}- что суммирование ведется по всем дугам, выходящим из промежуточного узла Л*).

Условие 3 означает, что из каждого промежуточного узла выходит ровно столько продукта, сколько в него поступило (и значит, никаких потерь продукта в узле Ак не происходит).

Покажем, что сумма потоков по всем дугам, входящим в сток Ат также равна величине v потока (иными словами, в сети нет никаких потерь).