![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
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. Алгоритмы на графах
Мы поддерживаем вектор 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. Алгоритмы на графах
Свойство 22.27. Если даны поток и допустимое остовное дерево, в котором нет подходящих ребер, поток представляет собой поток минимальной стоимости. Доказательство: Если подходящие ребра отсутствуют, то в остаточной сети отсутствуют также циклы с отрицательной стоимостью, так что из условия оптимальности, определяемого свойством 22.23, следует, что поток является потоком минимальной стоимости. ■ Эквивалентная формулировка утверждает, что если задан поток и множество потенциалов вершин, таких, что все приведенные стоимости древесных ребер равны нулю, все полные недревесные ребра неотрицательны, а пустые недревесные ребра неположительны, то поток есть поток минимальной стоимости. Если мы имеем подходящие ребра, мы можем выбрать одно из них и наращивать дерево вдоль цикла, которое оно образует с древесными деревьями с целью получения потока более низкой стоимости. Аналогично реализации из раздела 22.5, в которой мы применили метод отбрасывания циклов, выполняем обход соответствующего цикла с тем, чтобы определить величину потока, который мы можем протолкнуть, затем пройти еще раз по циклу, чтобы протолкнуть такую величину потока, которая обеспечивает заполнение или опорожнение, по меньшей мере, одного ребра. РИСУНОК 22.46. ПОТЕНЦИАЛЫ ВЕРШИН Потенциалы вершин определяются структурой остовного дерева и исходными значениями потенциалов вершин, присваиваемых каждой вершине. В таблице -слева показано множество ребер, образующих остовное дерево, состоящее из десяти вершин от 0 до 9. На диаграмме в центре изображено представление этого дерева, в котором в качестве корня выбрана вершина 5, вершины, соединенные с вершиной 5 находятся на уровень ниже и т.д. Когда мы присваиваем корню значение потенциала, равное нулю, существует уникальное сочетание потенциалов, назначаемых другим узлам, при котором разность потенциалов вершин каждого ребра равна его стоимости. На диаграмме справа дано представление того же дерева, в котором в качестве корня выбрана вершина 0. Потенциалы, которые мы получим, присваивая вершине 0 значение 0, отличаются от потенциалов, показанных на диаграмме в центре, на некоторое постоянное значение. Эта разность потенциалов используется во всех наших вычислениях: упомянутая разность остается одной и той же для любой пары потенциалов независимо от того, с какой вершины мы начнем вычисления (и независимо от того, какое значение мы присвоим вершине), следовательно, выбор исходной вершины и начального значения не играет роли.
|