U-V, И V-U.

Определение 22.10. Пусть дан максимальный поток без циклов частично заполненных ре­бер, тогда допустимое остовное дерево (feasible spanning tree) этого максимального по­тока представляет собой любое остовное дерево сети, которое содержит все частично за­полненные ребра.

Глава 22, Потоки в сетях

В этом контексте мы игнорируем направление ребра в остовном дереве. Иначе говоря, любое множество V- 1 ориентированных ребер, кото­рые соединяют V вершин между собой (при этом направление ребер игнорируется), составляет ос­товное дерево, а остовное дерево допустимо, если все ребра, не содержащиеся в дереве, являются полными или пустыми.

Первый шаг сетевого симплексного алгоритма заключается в построении остовного дерева. Один способ его построения предусматривает вычисле­ние максимального потока, разбиение циклов ча­стично заполненных ребер за счет наращивания потока, чтобы заполнить или опорожнить одно из его ребер, и последующее добавление пустых или полных ребер к остальным частично заполненным ребрам с целью построения остовного дерева. Пример такого процесса представлен на рис. 22.44. В другом варианте первый шаг предусматри­вает вычисление максимального потока в фиктив­ном ребре, соединяющем исток в сток. Далее, это ребро является единственным возможным частич­но заполненным ребром, и мы можем построить остовное дерево для данного потока в процессе любого просмотра графа. Пример такого остовно­го дерева приводится на рис. 22.45.

На данном этапе добавление в остовное дере­во ребра, не принадлежащего ему, приводит к об­разованию цикла. Механизмом, составляющим основу сетевого симплексного алгоритма, являет­ся множество весов вершин, которое обеспечива­ет немедленную идентификацию тех ребер, кото-

РИСУНОК 22.43. КЛАССИФИКАЦИЯ РЕБЕР

По отношению к любому потоку ребро может быть пустым, полным или частично заполненным (ни пустое, ни заполненное). В этом потоке ребро 1-4 пустое; ребра 0-2, 2-3, 2-4, 3-5 и 4-5 заполнены, ребра 0-1 и 1-3 частично заполнены. Наши соглашения дают два способа идентификации состояний ребер: в столбце потока вхождения 0 означают пустые ребра; вхождения, обозначенные звездочками, суть заполненные ребра; ребра, которые не обозначены ни 0, ни звездочками — это частично заполненные ребра. В остаточной сети (внизу) пустые ребра появляются только в правом столбце, а частично заполненные ребра -в обоих столбцах.

Часть 5. Алгоритмы на графах

Иначе говоря, приведенная стоимость каждого ребра есть разность между фактической стоимостью ребра и разностью потенциалов вершин этого ребра. В реализации, связанной с распределением товаров, за потенциалом узла можно разглядеть конкретный смысл: если интерпретировать потенциал ф(и) как затраты на приобретение единицы товара в узле и, то полная стоимость c(u, v) + ф(и) - ф(v) суть затраты на закупку товара в узле и, доставка товара в v и реали­зация товара в v.

Мы поддерживаем вектор phi, индексированный именами вершин, для хранения потенциалов вершин и вычисления приведенной стоимости ребра v-w, вы­читая из стоимости ребра значения (phi[v] - phi[w]). To есть, нет необходимости где-то хранить приведенную стоимость ребра, поскольку ее очень легко вычис­лить.

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

Свойство 22.25. Мы говорим, что потенциалы вер-шин имеют силу, или допустимы (valid), в отноше­нии остовного дерева, если все древесные ребра име­ют приведенную стоимость, равную нулю. Для всех имеющих силу потенциалов вершин любого остовного дерева величина приведенной стоимости каждого реб­ра сети является одной и той же.

Доказательство: Пусть даны две различные потен­циальные функции ф и ф, которые имеют силу в отношении заданного остовного дерева, покажем, что они различается на аддитивную постоянную: т.е., что ф(и) = ф'(и) + А для всех и и некоторой постоянной А. Таким образом, ф(и) — ф(v) = ф'(и) - ф'(v) для всех и и v. Отсюда следует, что все приведенные стоимости одинаковы для двух потенциальных функций.

РИСУНОК 22.44. ОСТОВНОЕ ДЕРЕВО МАКСИМАЛЬНОГО ПОТОКА

Пусть задан максимальный поток (диаграмма вверху), мы можем построить некоторый максимальный поток, обладающий остовным деревом, таким, что ни одно из ребер, не включенных в остовное дерево, не является частично заполненным ребром, с помощью двухэтапного процесса, представленного в данном примере. Сначала мы разрушаем цикл частично заполненных ребер - мы разрушаем цикл 0-2-4-1-0, проталки­вая через него поток величиной в одну единицу. Мы всегда можем заполнить или опорожнить таким способом, по меньшей мере, одно ребро; в рассмат­риваемом случае мы опорожняем ребро 1-4 и заполняем ребра 0-2 и 2-4 (диаграмма в центре). Затем мы включаем пустые и полные ребра во множество частично заполненных ребер, образующих остовное дерево; в рассматриваемом случае мы добавля­ем ребра 0-2, 1-4 и 3-5 (диаграмма внизу).

Глава 22, Потоки в сетях

Для любых двух вершин u и v, которые связа­ны между собой древесным ребром, должно иметь место равенство ф(v) = ф(и) — c(w, v), исходя из следующих соображений. Если u-v есть древесное дерево, то ф(v) должна быть равно ф(и) — c(u, v), чтобы приведенная сто­имость c(u, v) - ф(и) + ф(v) была равна нулю; если v-u есть древесное ребро, то ф(v) должна быть равна ф(и) — c(v, u), чтобы приведенная стоимость c(v, u) — ф(v) + ф(и) была равна нулю. Те же рассуждения справедливы и для ф', так что мы имеем ф'(v) = ф'(и) - c(u, v).

Выполняя вычитание, находим, что ф(v) - ф'(v) = ф(и) - ф'{и) для любых и и v, соединенных древесным ребром. Обозначив эту разность для любой вершины через А, и применив это равенство к ребрам любого де­рева поиска, получаем ф(и) = ф'(и) + А для всех u. Другой способ представления процесса опре­деления некоторого множества имеющих силу потенциалов вершин заключается в том, что мы

РИСУНОК 22.45. ОСТОВНОЕ ДЕРЕВО ДЛЯ ФИКТИВНОГО МАКСИМАЛЬНОГО ПОТОКА

Если мы начинаем с потока фальшивого ребра из истока в сток, то это един­ственное возможное частично заполнен­ное ребро, благодаря чему мы можем использовать любое остовное дерево из остальных ребер для построения остовно­го дерева для потока. В рассматриваемом примере ребра 0-5, 0-1, 0-2, 1-3 и 1-4 составляют остовное дерево для исходного максимального потока. Все недревесные ребра остаются пустыми.

Часть 5. Алгоритмы на графах

Сумма левых частей этих уравнений дает итоговую сумму цикла, а сумма в правой ча­сти сводится к c*(u, v). Другими словами, приведенная стоимость ребра дает стоимость цикла, таким образом, только описанные ребра могут дать циклы с отрицательной стоимостью. ■

Свойство 22.27. Если даны поток и допустимое остовное дерево, в котором нет подхо­дящих ребер, поток представляет собой поток минимальной стоимости.

Доказательство: Если подходящие ребра отсутствуют, то в остаточной сети отсутству­ют также циклы с отрицательной стоимостью, так что из условия оптимальности, оп­ределяемого свойством 22.23, следует, что поток является потоком минимальной стоимости. ■

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

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

РИСУНОК 22.46. ПОТЕНЦИАЛЫ ВЕРШИН

Потенциалы вершин определяются структурой остовного дерева и исходными значениями потенциа­лов вершин, присваиваемых каждой вершине. В таблице -слева показано множество ребер, образующих остовное дерево, состоящее из десяти вершин от 0 до 9. На диаграмме в центре изображено пред­ставление этого дерева, в котором в качестве корня выбрана вершина 5, вершины, соединенные с вершиной 5 находятся на уровень ниже и т.д. Когда мы присваиваем корню значение потенциала, равное нулю, существует уникальное сочетание потенциалов, назначаемых другим узлам, при котором разность потенциалов вершин каждого ребра равна его стоимости. На диаграмме справа дано представление того же дерева, в котором в качестве корня выбрана вершина 0. Потенциалы, которые мы получим, присваивая вершине 0 значение 0, отличаются от потенциалов, показанных на диаграмме в центре, на некоторое постоянное значение. Эта разность потенциалов используется во всех наших вычислениях: упомянутая разность остается одной и той же для любой пары потенциалов независимо от того, с какой вершины мы начнем вычисления (и независимо от того, какое значение мы присвоим вершине), следовательно, выбор исходной вершины и начального значения не играет роли.