Часть II issn 2072-0297

150
«Молодой учёный» . № 7 (66)  . Май, 2014 г.
Технические науки
Каждому из шести узлов соответствует строка, и каждой из девяти дуг соответствует столбец матрицы; числа +1 
и −1 полностью описывают связи между узлами и дугами. Задача определения максимального потока (сделать x
61
наи-
большим) превращается в обычную задачу линейного программирования (возможно использование симплекс-ме-
тода).
Укажем и другой подход (укороченный вариант). Разделим все узлы на две группы 
S
и 
S′
с источником в группе 
S
и стоком в 
S′
(разрез сети). Сумма пропускных способностей по всем дугам, идущим из 
S
в 
S′
, определит про-
пускную способность разреза (например, если 
S
содержит первый и третий узлы, то пропускная способность этого 
разреза равна 4 + 3 + 4 = 11; поток, превышающий 11, невозможен, так как не может пройти через разрез). Известно, 
максимальный поток в сети равняется пропускной способности минимального разреза (теорема о максимальном по-
токе и минимальном разрезе). Неравенство в одну сторону очевидно: поток не превосходит пропускной способности 
разреза (для произвольных значений потока и разреза). Никакой поток не в состоянии сделать больше, чем просто 
насытить все дуги, пересекающие разрез, и их общая пропускная способность является верхней гранью для потока 
(аналогично «слабой двойственности», простому неравенству ub ≤ cx," x, u). Определение достижимости равенства — 
более сложная задача, как и в теореме двойственности.
Пусть некоторый поток является максимальным. Рассмотрим все дуги, которые не достигли предела пропускной 
способности, и пусть 
S
содержит источник, а также все узлы, которые можно от него достичь по этим дугам. Остальные 
узлы образуют группу 
S′
. Тогда сток будет находиться в 
S′
; в противном случае поток не будет максимальным. Более 
того, каждая дуга, соединяющая 
S
с 
S′
, является заполненной. Иначе узел, в который она входит, принадлежал бы 
S
, а не 
S′
. Следовательно, поток действительно наполняет разрез, и равенство достигается. Это дает возможность 
проверить, что заданный поток является максимальным (нужно лишь найти соответствующий разрез). В рассматри-
ваемом примере максимальный поток равен 6 (максимальный поток и минимальный разрез указываются на рис. 2). 
Указанная теорема дает и алгоритм решения: для любого потока нужно вычислить неиспользованную пропускную 
способность каждой дуги. Если сток может быть достигнут по какому-то недозаполненному пути, то следует увеличить 
результат. Постепенно будет достигнут максимальный поток (в случае целочисленных пропускных способностей цело-
численным будет и поток — задача целочисленного программирования).
Рис.