Рис. И.Юе и 3. Сконденсированный граф после 4-го (е) и 5 го (з) этапов.

© ©

Рис. 11.Юж. Т* после 4-го этапа.

Gч^)M5-©

© ©

Рис. 11.10и. Окончательное потоково эквивалентное дерево Т*.

вычислить непосредственно с помощью (11.10). Она имеет вид

Матрица

максимальных

потоков

Все 5 (в общем случае п - i) разрезов графа G, соответствующие ребрам дерева Т*, показаны пунктиром на рис. 11.11.

Следует заметить, что, вообще говоря, потоково эквивалентное дерево Т* не является единственным и что существуют другие

Рис. 11.11. Разрез, дающий дерево Т*.

Рис. 11.12. Другое потоково эквивалентное дерево.

деревья, также потоково эквивалентные графу G. Для нашего примера одно из таких деревьев, которое на самом деле будет гамильтоновой цепью, показано на рис. 11.12.

5. Поток минимальной стоимости от 5 к

в разделе 2 мы рассмотрели задачу максимизации потока от s к t безотносительно к какой-либо стоимости. Теперь мы рассмотрим задачу нахождения такого потока заданной величины v от s к t, стоимость которого минимальна. В этой задаче каждая дуга {xi, Xj) имеет два связанных с ней числа - пропускную способность и стоимость Cij единицы потока по этой дуге.

Очевидно, что если v болыпе, чем значение максимального потока от S к , то не существует никакого регпения. Если же v не превыгпает этого значения, то, вообще говоря, может существовать несколько различных потоков и требуется найти поток величины у, обеспечивающий минимальную стоимость. Наиболее известной процедурой регпения задачи о потоке с минимальной стоимостью является так называемый алгоритм беспорядка Форда и Фалкерсона, и интересующийся читатель может найти описание этого эффективного алгоритма в [12], [4] и [7]. Алгоритмы, которые мы здесь опигпем, принадлежат Клейну [20] и Басакеру и Гауэну [6]. Эти алгоритмы концептуально проще, чем метод беспорядка, и используют уже введенную технику. С вычислительной точки зрения эти методы сравнимы [2].

5.1. Алгоритм, основанаый на выявлении отрицательных циклов

Предположим, что в графе существует допустимый поток % со значением v и что этот поток известен. Такой поток может быть получен с помощью алгоритма максимального потока (от s к. f) из разд. 2 и добавления потока общей величины б (f) на всех аугментальных цепях (гпаги с 4 по 6 алгоритма) до тех пор, пока поток fst не достигнет значения v, которое по условию меныпе значения максимального потока.

Для этого допустимого потока определим новый инкрементальный граф (I) = {Х^, А^) ъ точности так, как это было объяснено в разд. 2.3, со следующими стоимостями дуг.

Для каждой дуги {х^,х^)А^ положим cfjCij. Для каждой дуги (xf, xf)6§ положим cji= - Ci.

Новый граф (I) дает теперь инкрементальные пропускные способности и стоимости (относительно начального потока ) любого дополнительного потока, введенного в G. Алгоритм основан на следующей теореме.

Теорема 5. Поток будет потоком минимальной стоимости со значением v тогда и только тогда, когда в G> {%) не существует никакого цикла Ф, сумма стоимости дуг которого отрицательна.