Рис. 27.2 27.2 Сокращение, (а) Вершины vi и V2. Здесь c(vi,V2) = 10 и c(v2, vi) = 4. (b) Ежедневно 8 ящиков перевозят из vi в V2. (с) Добавили встречные перевозки 3 ящиков в день из V2 в v\. (d) Сократили противоположные потоки - осталось 5 ящиков в день, (е) Добавили перевозку ещё 7 ящиков в день из V2 в vi.

Рис. 27.3 27.3 Задача о максимальном потока для нескольких истоков и стоков сводится к обычной, (а) Сеть с пятью истоками S = {si, S2, S3, S4, s5} и тремя стоками Т = {ti, t2, Ьз}. (b) Сооответствующая сеть с одним истоком и одним стоком; добавленные рёбра имеют бесконечную пропускную способность.

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

Один из возможных потоков показан на рис.27.1(b). Из вершины и в вершину v в день отправляется f(u, v) ящиков; если f(u, v) равно 0, ящики не отправляются; отрицательные значения f(u, v) соответствуют ящикам, прибывающим в и из v.

Внимательный читатель мог уже заметить, что реальная ситуация не вполне описывается нашей моделью. Именно, наша модель не учитывает встречные перевозки. Если из вершины v\ в v2 ежедневно везут восемь ящиков, а из v2 в v\ ежедневно везут три ящика, чему должны быть равны f(vi,v2) и f(v2,v\)l (Напомним, что эти величины должны быть противоположны.) Мы полагаем f(vi,v2) = 8 - 3 = 5, a f(v2,vi) = -5. Те же значения функции / соответствуют ежедневным перевозкам пяти ящиков из v\ в v2, так что в нашей модели встречные перевозки автоматически сокращаются. Впрочем, и в реальности встречные перевозки разумно «сократить» друг с другом, (экономика должна быть экономной), при этом места на грузовиках понадобится только меньше.

На рис. 27.2 показан пример сокращения потоков между вершинами v\ и v2 (27.2 (а)). Сначала из v\ в v2 возили ежедневно 8 ящиков (27.2 (Ь)). Затем стали возить 3 ящика в обратном направлении (27.2 (с)), пока не догадались вместо этого уменьшить число перевозимых в обратную сторону ящиков на 3 (27.2 (с!)). Эти две различные (в жизни) ситуации соответствуют одной и той же функции /: в обоих случаях f(v\,v2) = 5, a f(v2,vi) = -5. Если теперь руководство требует начать перевозки дополнительных 7 ящиков в день из v2 в v\, то нужно прежде всего отменить перевозки 5 ящиков в обратную сторону, после чего назначить перевозку дополнительных 2 ящиков (27.2 (е)). Тем самым требование будет выполнено (несмотря на то, кстати, что в грузовиках из v2 в v\ есть места только на 4 ящика.

Сети с несколькими истоками и стоками

Можно рассматривать задачу о максимальном потоке для слу-

чая нескольких истоков и стоков. Компания «Кленовые листья» может иметь то фабрик {si, s2,.. -sm} и п складов {t\, t2, , tn} (рис. 27.3 (а)). Но это не усложняет дела, потому что такой вариант проблемы можно свести к обычному. На рис. 27.3 (Ь) показана эквивалентная сеть с одним истоком и одним стоком. Мы добавили общий исток (supersource) s, из которого ведут рёбра бесконечной пропускной способности во все прежние истоки (c(s, s8) = 00 при всех г = 1,2,..., то). Аналогичным образом из всех прежних стоков проведены рёбра в общий сток (supersink) t. Легко видеть, что каждый поток в сети (а) соответствует потоку в сети (Ь) и наоборот (формальное доказательство оставляется читателю в качестве упр. 27.1-3) Обозначения

Мы будем использовать следующее соглашение: если в выражении на месте вершины стоит множество вершин, то имеется в виду сумма по всем элементам этого множества (неявное суммирование, inplicit summary notation). Это относится и к случаю нескольких переменных. Например, если А и У - множества вершин, то

дх,у) = ЕЕЛжу)-

хех yeY

В этих обозначениях закон сохранения потока запишется как f(u, V) = 0 для всех и £ V - {s,t}. Кроме того, в неявных суммах мы опускаем фигурные скобки (например, в равенстве f(s, V\s) = f(s, V) символ V \ s обозначает V \ {s}.

Вот несколько полезных свойств таких сумм (доказательство мы оставляем читателю как упр. 27.1-4):

Лемма 27.1

Пусть / - поток в сети G = (V,E). Тогда для любого X С У выполнено

f(X,X) = 0. Для любых X, Y С V выполнено

f(X,Y) = -f(Y,X).

Для любых X, Y, Z С V из X П У = 0 следует

f(X UY,Z) = f(X, Z) + f(Y, Z)

и

f(Z,XUY) = f(Z,X) + f(Z,Y).

Для примера докажем с использованием таких обозначений, что величина потока равна сумме потоков из всех вершин в сток:

\f\=f(V,t).

(27.3)

Интуитивно это ясно (куда ж ему ещё деваться), но можно провести и формальное рассуждение. Вот оно: По определению,

\f\ = f(s,V) Применяя лемму 27.1, имеем

f(s, V) = f(V, V) - f(V \s,V) = f(V, V\s) = f(V, t) + f(V,V\s\t).

По закону сохранения потока второе слагаемое равно 0, и остаётся f(V,t).

Обобщение леммы 27.1 будет доказано ниже (лемма 27.5)

Упражнения

27.1-1

Следуя образцу рис. 27.2, изобразите две вершины и и v, для которых с(и, v) = 5, c(v, и) = 8, из и в v пересылаются 3 единицы, а из v в и - 4. Чему равен поток из и в и?

27.1-2

Проверьте, что функция / рис.27.1 (Ь) действительно является потоком. 27.1-3

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

27.1-4

Докажите лемму 27.1. 27.1-5

Для сети G = (V, Е) и потока / на рис.27.1 (Ь), укажите пример подмножеств X, Y С V, для которых f(X, У) = -f(V\X,Y, а также подмножеств X, Y С V, для которых f(X, У) ф - f(V\X, Y.

27.1-6

Пусть имеется сеть G = (V, Е) и два потока fi и f2 на ней. Рассмотрим их сумму (функцию из V X V в Ж):

(Л + /2)(Щ v) = Ми, v) + f2(u, v)(27.4)

Каким требованиям из определения потока она удовлетворяет обязательно, а каким может не удовлетворять? 27.1-7

Поток / можно умножить на вещественное число а, получив функцию

(af)(u,v) = а f(u,v)

Докажите, что для любой сети множество потоков выпукло. Это значит, что если fi и f2 - потоки, то сумма afi + (1 - си)/2 при О а 1 тоже является потоком. 27.1-8