Рис. 21а

Переходя к новой сети (рис. 21а), замечаем, что в ней нет ни одного ориентированного пути без дуги с нулевой пропускной способностью. Это означает, что построенный поток - полный. Но является ли его величина - 10 - наибольшей из возможных? Ответ на этот вопрос не столь очевиден. Вот маленький пример.

Пример 2. Обратимся к транспортной сети, представленной на рис. 22а.

Рис. 22а

Выбирая способы перемещения продукта от источника Д> к стоку А3

так:

сначала путь Д> -> Ах-> А2-> А3 (рис. 226),

затем путь Д> -> А{ -> Аъ (рис. 22в)

и наконец путь Ао->А2->А3 (рис. 22г), мы приходим к тому, что каждый путь из пункта Д> в пункт А3 содержит насыщенную дугу (рис. 22д). Тем самым, полученный поток величиной 3 - полный.

Рис. 22г

Однако, вновь обратившись к рисунку 22а, легко заметить, что пути Ао -* Ах -> Аъ и Aq -* А2 -* Аг обеспечивают поток величиной 4, а не 3, как это получилось у нас чуть раньше. Видимо, мы не так рачительно использовали отпущенные нам ресурсы.

Рис. 22д

Что же делать?

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

Более или менее ясно, что построение полного потока - задача достаточно простая. Но как проверить, обладает ли построенный полный поток максимально возможной пропускной способностью (в силу ограниченности пропускной способности транспортной сети поток с максимальной пропускной способностью всегда существует), и как следует поступать в случае отрицательного заключения.

Ответы на оба поставленных вопроса нашли Д. Фалкерсон и Л. Форд [11]. Они предложили критерий, посредством которого можно определить, является ли построенный поток максимальным или нет, а также способ, который позволял бы выйти из тупиковой ситуации и преобразовать полный (но не максимальный) поток в максимальный.

Начнем с описания критерия, в качестве которого они предложили использовать разрез {разделяющее сечение) сети.

Но сначала несколько новых обозначений.

Обозначим через X (какое-нибудь) множество узлов заданной транспортной сети, содержащее источник Ао и не содержащее сток Ат а через % - множество всех остальных узлов этой сети. Ясно, что стокЛл Е X.

Совокупность (Х9Х) всех дуг сети, начало которых принадлежит множеству X, а конец - множеству X, будем называть разрезом сети. Суммарная пропускная способность всех дуг разреза называется пропускной способностью разреза. Будем обозначать ее через С(Х,Х).

Заметим, что любой путь из источника Ао к стоку А содержит по меньшей мере одну дугу каждого разреза (Х,Х).

В самом деле, перемещаясь по произвольно выбранному пути из источника 4> Е % в сток Ап Е X, мы непременно наткнемся на узел А( Е X,