Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 162
Текст из файла (страница 162)
Кроме того, в упражнении 26.4-2 устанавливается граница О (У Е) для суммарного времени, затраченного на выполнение подъемов, а лемма 26.23 устанавливает границу О (У Е) для суммарного числа операций насыщающих проталкиваний. Часть Ч1 Алгоритмы для работы с графами 784 у (~ з т х к, т х х х "у~~ ' 20~ Теорема 26.31. Времявыполненияпроцедуры КньАвнь То Рномтдлялюбойсе- ти С = (1', Е) составляет О (1'з). Доказатвельсвтво. Будем считать "фазой" алгоритма "поднять-в-начало" время между двумя последовательными операциями подъема.
Поскольку всего выполняется О (Ъ'з) подъемов, в алгоритме насчитывается О (Ъ'з) фаз. Каждая фаза сдержит не более Щ обращений к процедуре ПшснАксн, что можно показать следующим образом. Если процедура Рыснлксн не выполняет подъем, то следующий ее вызов происходит ниже по списку Ь, а длина Ь меньше ~Ц. Если процедура 1нзснАкпн выполняет подъем, то следующий ее вызов происходит уже в другой фазе алгоритма. Поскольку каждая фаза содержит не более ~Ц обращений к процедуре П~зснлксн и в алгоритме насчитывается О (Ъ'~) фаз, число вызовов данной процедуры строкой 8 процедуры Килвн. То Рком' составляет О (Ъ'~).Таким образом, цикл ип11е процедуры Кньлвн.
То Ркслчт выполняет работу (не учитывая работу, выполняемую внутри процедуры П1вснлксп), не превышающую О (Ъ'з). Теперь необходимо оценить работу, выполняемую внутри процедуры П~зснАкпп в ходе выполнения данного алгоритма. Каждое выполнение цикла тчЬ!1е в процедуре П[зснАкпн заключается в выполнении одного из трех действий. Проанализируем объем работы при выполнении каждого из них. Начнем с подъемов (строки 4-5). В упражнении 26.4-2 время для выполнения всех О (Ъ'з) подъемов ограничивается пределом О (У Е). Глава 26. Задача о максимальном потоке 785 Теперь предположим, что действие заключается в обновлении указателя ситтепг [и) в строке 8.
Это действие выполняется 0 (дебгее(и)) в том случае, когда вершина и подвергается подъему, что для всех вершин составляет 0(Ъ" !1ейгее(и)) раз. Следовательно, для всех вершин общий объем работы по перемещению указателей в списке соседей составляет 0((ГЕ) согласно лемме о рукопожатиях (упражнение Б.4-1). Третий тип действий, выполняемых процедурой Р!зснАкОе, — операция проталкивания (строка 7). Как уже отмечалось, суммарное число насьпцающих операций проталкивания составляет 0 (Ъ' Е). Если выполняется ненасышающее проталкивание, процедура ь1!ЕснАкОе немедленно выполняет возврат, поскольку такое проталкивание уменьшает избыток до О.
Поэтому при каждом обращении к процедуре Р!зснАеое может выполняться не более одного ненасыщающего проталкивания. Процедура Р!зснАкОе вызывается 0 (!'з) раз, следовательно, общее время, затраченное на ненасыщающие проталкивания, составляет О (!'з). Таким образом, время выполнения процедуры КВЕАВеь ТО РеОнт составляет 0 (1~2 + Ъ'Е), что эквивалентно 0 (Ъ'з). Упражнения 26.5-1. Проиллюстрируйте (используя в качестве образца рис.
26.10) выполнение процедуры КВЕАвеь ТО РЕОнт для сети, представленной на рис. 26.1а. Предполагается, что начальный порядок следования вершин в списке Š— (с1, с2, сз, с4), а списки соседей имеют следующий внд: Ж[и1) = (а,сз)сз), Ф [52) = (3) 01 э сз, с4), )1Г [сз) (с1 ~ с2 ~ е4 ~ 2) 1 1!( [с4) (с21 пз з !) ° *26.5-2.
Мы хотим реализовать алгоритм проталкивания предпотока, в котором поддерживается порядок обслуживания переполненных вершин "первым вошел, первым вышел'". Данный алгоритм разгружает первую вершину в очереди и удаляет ее оттуда, а все вершины, которые перед этой разгрузкой не были переполнены, но после нее стали таковыми, помещаются в конец очереди. Когда очередь становится пустой, алгоритм завершается. Покажите, что можно построить реализацию данного алгоритма, которая вычисляет максимальный поток за время О (Ъ'з).
26.5-3. Покажите, что обобщенный алгоритм будет работать, даже если процедура КеьАвеь при обновлении 11 [и) просто использует выражение 11 [и) — Ь [и] + 1. Как это повлияет на оценку времени выполнения процедуры КеьАВеь ТО РкОхт? Часть Ч!. Алгоритмы для работы с графами 786 * 26.5-4. Покажите, что если разгрузке всегда подвергается наивысшая переполненная вершина, метод проталкивания предпотока можно реализовать так, чтобы он выполнялся за время О (Уз). 26.5-5.
Предположим, что в некоторой точке в процессе выполнения алгоритма проталкивания предпотока, существует некоторое целое число б < к < < [Ц вЂ” 1, лля которого нет ни одной вершины с данной высотой, т.е. такой, что Л [с] = /с. Покажите, что все вершины с Л [с] > Л находятся в минимальном разрезе на стороне источника. Если такое значение !с существует, эеристика промежутка (8ар !зеипзйс) обновляет каждую вершину о е $' — е, для которой Л [с] > Й, устанавливая Л [е] — шах(Л [с], [Ц + 1). Покажите, что полученный таким образом атрибут Л является функцией высоты.
(Эвристика промежутка позволяет получить эффективные реализации метода проталкивания предпотока на практике.) Задачи 26-1. Задача о выходе Решетка (йпд) размером и х и — это неориентированный граф, состоящий из и строк и и столбцов вершин, как показано на рис. 26.! 1. Обозначим вершину, находящуюся в 1-й строке и з'-м столбце как (г, з). Каждая вершина решетки имеет ровно по четыре соседа, за исключением граничных вершин, представляющих собой точки (г, з'), для которых 1 = 1, г = и, з' = 1 или з = и. Пусть в решетке задано ги < из стартовых точек (хы у1), (хз, уз), ..., (х,у ).
Задача о выходе (езсаре ргоЫеш) заключается в том, чтобы определить, существует ли ги путей, не имеющих общих вершин, из стартовых точек к любым ги различным точкам границы. Например, решетка на рис. 26.11а имеет выход, а решетка на рис. 26.11б — не имеет. а) Рассмотрим транспортную сеть, в которой вершины, равно как и ребра, имеют пропускные способности, т.е. суммарный положительный поток, входящий в каждую заданную вершину, должен удовлетворять ограничению пропускной способности.
Покажите, что задача определения максимального потока в такой сети, где вершины и ребра имеют пропускные способности, может быть сведена к стандартной задаче о максимальном потоке для транспортной сети сопоставимого размера. б) разработайте эффективный алгоритм решения задачи о выходе и проанализируйте время его выполнения. Глава 26. Задача о максимальном потоке 787 0- — -ч †. -о- †.
? — -»-- .."' ~ --ф — --с- — ф — + — Ф ф- — ~~--- с" — — ф - — ф. --лв О---ф — -С~- -ф- -?--ф --.-. — -~-"-.»» — --с ь- — ° »" - ' — - -с- - —.~." — — - » Рис. 26.11. Решетки для задачи о выходе. Стартовые точки отмечены черным цветом, остальные вершины решетки белые. а) Решетка с выходом, пути указаны цветом.
б) Решетка без выхода 26-2. Задача о минимальном покрытии путями Покрытие путями (рабз сочег) ориентированного графа С = (У, Е)— это множество Р не имеющих общих вершин путей, таких что каждая вершина из множества У принадлежит ровно одному пути из Р. Пути могут начинаться и заканчиваться где угодно, а также иметь произвольную длину, включая О. Минимальным покрытием путями (пйшпплп ра1)з сочег) графа С называется покрытие, содержащее наименьшее возможное юличество путей. а) Предложите эффективный алгоритм поиска минимального покрытия путями ориентированного ациклического графа С = (У,Е).
(Указание: предположив, что У = (1,2,...,п), постройте граф С' = (У',Е'), где / У = (хо,хы...,х„) О(уо,уы...,у„), Е' = ((хо,х;): (б У) 0 ((умуо): з б У) 0((х» уу): (в', у) ЕЕ), и примените алгоритм поиска максимального потока.) б) Будет ли ваш алгоритм работать для ориентированного графа, содержащего циклы? Объясните ваш ответ. 26-3. Эксперименты на кораблях многоразового использования Профессор консультирует НАСА при планировании серии полетов кораблей многоразового использования.
Он должен решить, какие юммерческие эксперименты следует провести и какие инструменты будут на борту во время каждого полета. Для каждого полета рассматривается множество экспериментов Е = (Еы Ез,..., Ет), и коммерческий Часть Ч1 Алгоритмы для работы с графами 788 спонсор эксперимента Е согласен заплатить НАСА р долларов за его результат. В экспериментах используется множество инструментов 1 = = (1п 1з,..., 1„); каждый эксперимент Е требует наличия всех инструментов из некого подмножества В С.1. Затраты перевозки в космическом корабле инструмента 1ь составляют сь долларов. Задача профессора— найти эффективный алгоритм, позволяющий определить, какие эксперименты проводить и какие инструменты размещать на борту корабля при каждом полете, чтобы максимизировать чистый доход, который вычисляется как суммарный доход от выполненных экспериментов минус суммарные затраты на перевозку всех используемых инструментов.
Рассмотрим следующую сеть С. Данная сеть содержит источник а„вершины 1ы 1з,..., 1„, вершины Ез, Ез,..., Е,„и сток г. Для каждого й = = 1, 2,..., и имеется ребро (в, 1ь) с пропускной способностью сы а для каждого з' = 1,2,...,т имеется ребро (Ез,1) с пропускной способностью ру. Если для к = 1, 2,..., и и 1 = 1, 2,..., т выполняется условие 1ь Е В1, то существует ребро (1ь, Е ) неограниченной пропускной способности.
а) Покажите, что если для разреза конечной пропускной способности (Я, Т) сети С Е е Т, то 1ь е Т для всех 1ь е В . б) Покажите, как определить максимальный чистый доход на основании пропускной способности минимального разреза С и заданных значений р . в) Предложите эффективный алгоритм, позволяющий определить, какие эксперименты проводить и какие инструменты брать в каждый полет. Проанализируйте время выполнения вашего алгоритма, выРазив его чеРез т, и и г = 1 ~~йз~.
26-4. Обновление максимального потока Пусть С = (К Е) — транспортная сеть с источниюм а, стоюм 1 и целочисленными пропускными способностями. Предположим, что известен максимальный поток в С. а) Предположим, что пропускная способность некоторого одного ребра (и,е) б Е увеличена на 1. Предложите алгоритм обновления максимального потока с временем выполнения 0 (Ъ'+ Е). б) Предположим, что пропускная способность некоторого одного ребра (и,и) Е Е уменьшена на 1. Предложите алгоритм обновления максимального потока с временем выполнения О (Ъ'+ Е). Глава 26. Задача о максимальном потоке 789 26-5.
Масштабирование Пусть С = (У, Е) — транспортная сеть с источником а, стоком г и целочисленными пропускными способностями с (и, и) всех ребер (и, и) Е Е. Пусть С = тах(„„)енс(и,и). а) Докажите, что минимальный разрез С имеет пропускную способность не более С 1Е). б) Для заданного числа К покажите, что за время О (Е) можно найти увеличивающий путь с пропускной способностью не менее К, если такой путь существует. Для вычисления максимального потока в С можно использовать следующую модификацию процедуры РОКО Р~Л.КНК8ОМ МЕтНОО: МАх Рьотг ВУ БсАыхо(С, а, Ф) 1 С вЂ” щах(„„)ен с(и, и) 2 Инициализация потока Г' значением О З К--2Ряс1 4 зчп11е К > 1 5 до тгЫ1е (пока) существует некоторый увеличивающий путь р с пропускной способностью не менее К 6 йо увеличить г' вдоль р 7 К -К/2 8 геГигп,Г в) Докажите, что процедура Млх Р~ о® Ву Бслымо возвращает максимальный поток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
