Определение прибавляющей цепи

Из теоремы Форда-Фолкерсона следует, что максимальный поток в сети не превосходит минимальной пропускной способности разреза, то есть

. (1)

Анализ неравенства (1) показывает, что величина потока совпадает с пропускной способностью разреза тогда и только тогда, когда выполняется условие:

(2)

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

Дадим определение прибавляющей цепи. Рассмотрим в сети цепь из источника в сток, то есть последовательность вершин

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

Пусть в сети задан поток . Цепь из в называется прибавляющей, если для каждой ее прямой дуги выполняется строгое неравенство , а для каждой обратной дуги – строгое неравенство .

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

Пример 1. Пусть прибавляющая цепь имеет вид (рис. 1):

Рис.1.

С помощью это цепи можно перейти к новому потоку (рис. 2.):

Рис. 1.