Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 163
Текст из файла (страница 163)
г) Покажите, что каждый раз, когда выполняется строка 4, пропускная способность минимального разреза остаточного графа Су составляет не более 2К1Е). д) Докажите, что внутренний цикл тгп11е в строках 5-6 при каждом значении К выполняется О (Е) раз. е) Покажите, что процедуру МАХ Рьов Ву БсАымо можно реализовать так, что она будет выполняться за время О (Ез 18 С). 26-6. Отрицательная пропускная способность Предположим, что в транспортной сети ребра могут иметь как положительную, так и отрицательную пропускную способность.
В такой сети не обязательно существует допустимый поток. а) Рассмотрим некоторое ребро (и,и) сети С = (К, Е), пропускная способность которого с (и, и) < О. Кратко поясните, что такая отрицательная пропускная способность означает в плане потока между и и и, каков ее "физический смысл". Часть Ч!. Алгоритмы для работы с графами 790 Пусть С = (У,Е) — некоторая транспортная сеть с отрицательными пропускными способностями, и пусть з и г — источник и сток данной сети.
Построим обычную транспортную сеть С' = (Г, Е') с функцией пропускной способности с', источником з' и стоком г', где Е' =.ЕО((и,е): (и,и) ЕЕ) О ((з 1е): е Е У) 0 ( (и, т'): и Е У~ О ((з, т), (г, з) ) . Присвоим ребрам пропускные способности следующим образом.
Для каждого ребра (и, е) е Е присвоим с' (и, п) = с' (е, и) = (с (и, е) + с (п, и) ) /2. Для каждой вершины и е У' присвоим с' (з', и) = шах (О, (с (У, и) — с (и, У)) /2) с' (и, Ф') = шах (О, (с (и, У) — с (У и) )/2) . Присвоим также с'(з,т) = с'(т,з) = оо. б) Докажите, что если в С существует допустимый поток, то все пропускные способности в С' неотрицательны и в ней существует максимальный поток, такой что все входящие в сток г' ребра являются насыщенными. в) Докажите утверждение, обратное утверждению пункта б).
Доказательство должно быть конструктивным, т.е. если задан поток в С', насыщающий все ребра, входящие в г', вам нужно показать, как получить допустимый поток в С. г) Разработайте алгоритм, который находит максимальный допустимый поток в С. Обозначим через МГ(Щ, ~Е0 наихудшее время выполнения стандартного алгоритма поиска максимального потока в графе с Щ вершинами и ~Е~ ребрами. Проанализируйте время выполнения вашего алгоритма вычисления максимального потока в транспортной сети с отрицательными пропускными способностями, выразив его через МЕ. Глава 26. Задача о максимальном потоке 791 26-7.
Алгоритм Хопкрофта-Карпа поиска паросочетания в двудольном графе В данной задаче представлен более быстрый алгоритм поиска максимального паросочетания в двудольном графе, предложенный Хопкрофтом (Норсгой) и Карпом (Катр). Этот алгоритм выполняется за время 0 (~ЯЕ). Задан неориентированный двудольный граф С = (У, Е), где Ъ' = ЕАЗА и у всех ребер ровно одна точка находится в Ь.
Пусть М вЂ” паросочетание в С. Мы говорим, что простой путь Р в С является увеличиваиниим иуизем (ап(рпеп11пя ра11з) по отношению к М, если он начинается в некоторой свободной вершине множества Ь, заканчивается в некоторой свободной вершине В, а его ребра попеременно принадлежат М и Е— — М. (Это определение увеличивающего пути связано с определением увеличивающего пути в транспортной сети, но несколько отличается от него.) В данной задаче путь трактуется как последовательность ребер, а не последовательность вершин. Кратчайший увеличивающий путь по отношению к паросочетанию М вЂ” это увеличивающий путь с минимальным числом ребер. Для заданных двух множеств А и В, симметрическая разность (зушше1йс ййегепсе) А ® В определяется как (А — В) 0 ( — А), т.е.
это элементы, которые входят ровно в одно из двух множеств. а) Покажите, что если М вЂ” некоторое паросочетание, а Р— увеличивающий путь по отношению к М, то симметрическая разность множеств М ® Р является паросочетанием, и ~М9 Р~ = ~М)+ + 1. Покажите, что если Рм Рз,..., Рь — увеличивающие пути по отношению к М, не имеющие общих вершин, то симметрическая разность М Ю (Р1 0 Рз 0. 0 Рь) является паросочетанием с мощностью ~М~ + 1с.
Общая структура алгоритма имеет следующий вид: НОРскОгт КАВР(С) 1 М+-О 2 гереа1 3 П сть Р у — (Ры Рз,..., Рь ) максимальное множество кратчайших увеличивающих путей по отношению к М, не имеющих общих вершин М вЂ” М Е (Р1 О Рз О " 1з Рь) 5 нп111 'Р = 6 б ге1пгп М 792 Часть Ч( Алгоритмы для работы с графами Далее в этой задаче вам предлагается проанализировать число итераций данного алгоритма (т.е. число итераций цикла гереат) и предложить реализацию строки 3.
б) Для двух заданных паросочетаний М и М' в С покажите, что каждая вершина графа О = (У, М ® М') имеет степень не больше 2. Сделайте вывод, что С' является обьединением непересекающихся простых путей или циклов. Докажите, что ребра каждого такого простого пути или цикла по очереди принадлежат М и М*. Докажите, что если ~М~ ( (М'), то М Щ М* содержит как минимум )М'! — )М( увеличивающих путей по отношению к М, не имеющих общих вершин.
Пусп ) — длина кратчайшего увеличивающего пути по отношению к паросочетанию М и пусть Ры Рз,..., Рь — максимальное множество увеличивающих путей длины 1 по отношению к М, не имеющих общих вершин. Пусть М' = М 9 (Рт 0 Рз О 0 Рь) и предположим, что Р— кратчайший увеличивающий путь по отношению к М'. в) Покажите, что если Р не имеет общих вершин с Ры Рз,..., Ры то Р содержит больше чем ( ребер. г) Теперь предположим, что Р имеет общие вершины с Ры Рз,..., Ры Пусть А — множество ребер (М ® М') ® Р.
Покажите, что А = = (Рт 0 Рз О . О Рь) 9 Р и что ~А~ > (й + 1) 1. Покажите, что Р содержит более ( ребер. д) Докажите, что если кратчайший увеличивающий путь для М содержит 1 ребер, то размер максимального паросочетания составляет не более (М)+ Я/() + 1). е) Покажите, что число повторений цикла гереат в данном алгоритме не превышает 2т/Г.
(Уииалие: на сколько сможет вырасти М после итерации номер т(Г?) ж) Предложите алгоритм для поиска максимального множества кратчайших увеличивающих путей Ры Рз,...,Рь для заданного паросочетания М, не имеющих общих вершин, время работы которого — О (Е). Покажите, что суммарное время выполнения процедуры Норскогт Клнв составляет О ( /7Е).
793 Глава 26. Задача о максимальном потоке Заключительные замечания Транспортные сети и связанные с ними алгоритмы рассматриваются в работах Ахуя (АЬща), Магнанти (Майпапй) и Орлина (Ог!ш) [7], Ивена (Ечеп) [87], Лоулера (1.а~ч1ег) [196], Пападимитриу (Рараг)(ш1птои) и Стейглица (Иге(8!йк) [237], Таржана (Тапап) [292]. Широкий обзор алгоритмов для задач поиска потоков в сетях можно найти также в книге Голдберга (Оо!дЬегй), Тардоса (Тап1оз) и Таржана [119]. В работе Шрайвера (БсЬг1]чег) [267] предлагается интересный исторический обзор исследований в сфере транспортных сетей.
Метод Форда-Фалкерсона представлен в работе Форда (Рогд) и Фалкерсона (РиПсегзоп) [93], которые являются основоположниками формальных исследований ряда задач в области транспортных сетей, включая задачи поиска максимального потока и паросочетаний. Во многих ранних реализациях метода Форда-Фалкерсона поиск увеличивающих пугей осуществляется с помощью поиска в ширину; Эдмонде (Ейпопдз) и Карп (Кшр) [86] и, независимо от них, Диниц (Ейшс) [76] доказали, что такая стратегия дает полиномиальный по времени алгоритм.
Диницу [76] также принадлежит идея использования "тупиковых потоюв™ (Ыос1с1п8 йод з); предпотоки впервые предложил Карзанов (Кагхапоч) [176]. Метод проталкивания предпотока описан в работах Голдберга [117] и Голдберга и Таржана [121]. Голдберг и Таржан приводят алгоритм со временем работы О (Уз), в котором для хранения множества переполненных вершин используется очередь, а также алгоритм на основе использования динамических деревьев, время работы которого достигает О (УЕ18 (Уз(Е+ 2)). Неюторые другие исследователи разработали алгоритмы проталкивания предпотока для поиска максимального потока.
В работах Ахуя и Орлина [9] и Ахуя, Орлина и Таржана [10] приводятся алгоритмы, использующие масштабирование. Чериян (СЬепуап) и Махешвари (МаЬезЬчаг)) [55] предложили проталкивать поток из переполненной вершины с максимальной высотой. В работе Черияна и Хейджерапа (Найегпр) [54] предлагается использовать случайные перестановки списков соседей; другие исследователи [14, 178, 241] развили данную идею, предложив искусные методы дерандомизации, что позволило получить ряд более быстрых алгоритмов.
Алгоритм, предложенный Кингом (Кшй), Рао (Као) и Таржаном [178], является самым быстрым из них — время его работы составляет О(УЕ 1обе (~,,я,~) У). Асимптотически самый быстрый из известных в настоящее время алгоритмов для задачи максимального потока разработан Голдбергом и Рао [120], время его работы равно О(ш)п(уз7з, Е ч ~) Е 18(у~/Е+ 2) 18 С), где С = шах(„„)ее с (и, и). Этот алгоритм не использует метод проталкивания предпотока, он основан на нахождении тупиковых потоков.
Все предыдущие алгоритмы, включая рассмотренные в данной главе, используют некоторое понятие расстояния (в алгоритмах проталкивания предпотока используется аналогичное понятие высоты), где каждому ребру неявно присвоена длина 1. В этом же алгоритме используется другой под- Часть Ч1. Алгоритмы для работы с графами ход: ребрам с высокой пропускной способностью присваивается длина О, а ребрам с низкой пропускной способностью — длина 1. Неформально при таком выборе длин кратчайшие пути от источника к стоку будут иметь высокую пропускную способность, следовательно, потребуется меньшее количество итераций.
На практике на сегодняшний день при решении задач поиска максимального потока алгоритмы проталкивания предпотока превосходят алгоритмы, основанные на увеличивающих путях и линейном программировании. В исследованиях Черкасски (СЬег1сазз1су) и Голдберга 156] подчеркивается важность использования при реализации алгоритма проталкивания предпотока двух эвристик. Первая состоит в том, что в остаточном графе периодически производится поиск в ширину, чтобы получить более точные значения высот.
Вторая эвристика — это"эвристика промежутка" (яар леппзг1с), описанная в упражнении 26.5-5. Авторы пришли к заключению, что наилучшим вариантом метода проталкивания предпотока является вариант, в котором для разгрузки выбирается переполненная вершина с максимальной высотой. Наилучший известный к настоящему времени алгоритм поиска максимального паросочетания (описанный в задаче 26-7) был предложен Хопкрофтом (Норстой) и Карпом (Кар) 1152]; время его работы составляет О (т/ГЕ). Задачи поиска паросочетаний подробно рассматриваются в книге Ловаса (1.отазг) и Пламмера (Р!шшпег) 1207]. Введение Эта часть содержит избранные темы теории алгоритмов, расширяющие и дополняющие материал, ранее изложенный в данной книге. В некоторых главах вводятся новые вычислительные модели, такие как комбинационные схемы или параллельные вычислительные машины.
Другие главы охватывают специализированные области знаний, такие как вычислительная геометрия или теория чисел. В двух последних главах обсуждаются некоторые известные ограничения, возникающие при разработке эффективных алгоритмов, а также излагаются основы методов, позволяющих справиться с этими ограничениями.
В главе 27 представлена параллельная модель вычислений: сравнивающие сети. Грубо говоря, сравнивающая сеть — это алгоритм, основанный на одновременном выполнении большого количества сравнений. В этой главе показано, как построить сравнивающую сеть, позволяющую сортировать п чисел за время 0()8' ). В главе 28 изучаются эффективные алгоритмы, предназначенные для работы с матрицами. После изучения некоторых основных свойств матриц исследуется алгоритм Штрассена (81газзеп), позволяющий перемножить две матрицы и х и за время 0 (пз а|). Затем представлены два общие метода 1.()-разложения и )Л)Р- разложения, предназначенные для решения системы линейных уравнений по методу Гаусса (методу исключений) за время 0 (пз).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
