Алгоритмы - построение и анализ (1021735), страница 162
Текст из файла (страница 162)
Данный алгоритм разгружает первую вершину в очереди и удаляет ее оттуда, а все вершины, которые перед этой разгрузкой не были переполнены, но после нее стали таковыми, помещаются в конец очереди. Когда очередь становится пустой, алгоритм завершается. Покажите, что можно построить реализацию данного алгоритма, которая вычисляет максимальный поток за время О (Ъ'з). 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 геГигп,Г в) Докажите, что процедура Млх Р~ о® Ву Бслымо возвращает максимальный поток.
г) Покажите, что каждый раз, когда выполняется строка 4, пропускная способность минимального разреза остаточного графа Су составляет не более 2К1Е). д) Докажите, что внутренний цикл тгп11е в строках 5-6 при каждом значении К выполняется О (Е) раз. е) Покажите, что процедуру МАХ Рьов Ву БсАымо можно реализовать так, что она будет выполняться за время О (Ез 18 С).
26-6. Отрицательная пропускная способность Предположим, что в транспортной сети ребра могут иметь как положительную, так и отрицательную пропускную способность. В такой сети не обязательно существует допустимый поток. а) Рассмотрим некоторое ребро (и,и) сети С = (К, Е), пропускная способность которого с (и, и) < О. Кратко поясните, что такая отрицательная пропускная способность означает в плане потока между и и и, каков ее "физический смысл". Часть Ч!. Алгоритмы для работы с графами 790 Пусть С = (У,Е) — некоторая транспортная сеть с отрицательными пропускными способностями, и пусть з и г — источник и сток данной сети.
Построим обычную транспортную сеть С' = (Г, Е') с функцией пропускной способности с', источником з' и стоком г', где Е' =.ЕО((и,е): (и,и) ЕЕ) О ((з 1е): е Е У) 0 ( (и, т'): и Е У~ О ((з, т), (г, з) ) . Присвоим ребрам пропускные способности следующим образом. Для каждого ребра (и, е) е Е присвоим с' (и, п) = с' (е, и) = (с (и, е) + с (п, и) ) /2. Для каждой вершины и е У' присвоим с' (з', и) = шах (О, (с (У, и) — с (и, У)) /2) с' (и, Ф') = шах (О, (с (и, У) — с (У и) )/2) . Присвоим также с'(з,т) = с'(т,з) = оо.
б) Докажите, что если в С существует допустимый поток, то все пропускные способности в С' неотрицательны и в ней существует максимальный поток, такой что все входящие в сток г' ребра являются насыщенными. в) Докажите утверждение, обратное утверждению пункта б). Доказательство должно быть конструктивным, т.е.
если задан поток в С', насыщающий все ребра, входящие в г', вам нужно показать, как получить допустимый поток в С. г) Разработайте алгоритм, который находит максимальный допустимый поток в С. Обозначим через МГ(Щ, ~Е0 наихудшее время выполнения стандартного алгоритма поиска максимального потока в графе с Щ вершинами и ~Е~ ребрами.
Проанализируйте время выполнения вашего алгоритма вычисления максимального потока в транспортной сети с отрицательными пропускными способностями, выразив его через МЕ. Глава 26. Задача о максимальном потоке 791 26-7. Алгоритм Хопкрофта-Карпа поиска паросочетания в двудольном графе В данной задаче представлен более быстрый алгоритм поиска максимального паросочетания в двудольном графе, предложенный Хопкрофтом (Норстой) и Карпом (Катр).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
