Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 178
Текст из файла (страница 178)
а Покажите, что пропускная способность минимального разреза остаточной сети Сс не превышает 2К ~Е~ при каждом выполнении строки 4. д. Докажите, что внутренний цикл зчйй!е в строках 5 и 6 выполняется 0(Е) раз для каждого значения К. к Сделайте вывод о том, что процедуру МАХ-Г1лзчг-Ву-Зсмл1чо можно реализовать таким образом, что она будет выполняться за время 0(Ез 18 С). Жб. Алгорнпан Хопкрофта — Карпа пояска паросочетання в двудольном графе В данной задаче представлен более быстрый алгоритм поиска максимального паросочетання в двудольном графе, предложенный Хопкрофтом (Норсгой) и Карпом (Катр).
Этот алгоритм выполняется за время О(кФЕ). Задан неориентированный двудольный граф С = (г', Е), где Ъ' = Е 1З К и у всех ребер ровно одна конечная точка находится в Е. Пусть М вЂ” паросочегание в С. Мы говорим, что простой путь Р в С является увелнчнвающнм путем (апйшеп1!пй рагЬ) по отношению к М, если он начинается в некоторой свободной вершине множества Е, заканчивается в некоторой свободной вершине В, а его ребра попеременно принадлежат М и Š— М.
(Это определение увеличивающего пути связано с определением увеличивающего пути в транспортной сети, но несколыю отличается от него.) В данной задаче путь трактуется как последовательность ребер, а не последовательность вершин. Кратчайший увеличивающий путь по отношению к паросочеганию М вЂ” это увеличивающий путь с минимальным числом ребер.
Для заданных двух множесгв А и В снмметрнческая разность (зугпше1пс ййегепсе) А ® В определяется как (А — В) 1З ( — А), т.е. это элементы, которые Часть Рб алгоритмы дла работы с графами ж Покажите, что если М представляет собой некоторое паросочетание, а Р— увеличивающий путь по отношению к М, то симметрическая разность множеств М Ю Р является паросочетанием, и )М Ю Р~ = (М( + 1. Покажите, что если Ры Рз,..., Рь — увеличивающие пути по отношению к М, не имеющие общих вершин, то симметрическая разность М З (Р1 0 Рз О ° О Рь) является паросочетанием с мощностью ~М~ + к. Обшая структура алгоритма имеет следующий вид. НОРСкОрт-КАКР (С) 1 М= И 2 гереаг 3 Пусть Р = (Ры Рз,..., Рь) — максимальное множество кратчайших увеличивающих путей по отношению к М, не имеюших общих вершин 4 М = М Ю (Р1 О Рз 0 ° О Рь) 5 нный 'Р == 6 6 ге$пгп М Далее в этой задаче вам предлагается проанализировать число итераций данного алгоритма (т.е.
число итераций цикла гереат) и предложить реализацию строки 3. б. Для двух заданных паросочетаний М и М* в С покажите, что каждая вершина графа С' = ((г, М 9 М*) имеет степень не больше 2. Сделайте вывод, что С' является несвязным объединением простых путей нли циклов. Докажите, что ребра каждого такого простого пути или цикла по очереди принадлежат М и М". Докажите, что если (М~ < )М'(, то М йд М' содержит как минимум (М*! — )М) увеличивающих путей по отношению к М, не имеющих обших вершин. Пусть 1 обозначает длину кратчайшего увеличивающего пути по отношению к паросочетанию М и пусть Ры Рз,..., Рь представляет собой максимальное множество не имеюших общих вершин увеличивающих путей длиной 1 по отношению к М. Пусть М' = М ® (Р1 0 0 Рь), и предположим, что Р— кратчайший увеличивающий путь по отношению к М'.
в. Покажите, что если Р не имеет общих вершин с Ры Рз,..., Рь, то Р содержит более 1 ребер. * Теперь предположим, что Р может иметь обшие вершины с РыРз,...,Ры Пусть А — множество ребер (М®М')®Р. Покажите, что А = (Р1 ОРзО 0 Рь) 9 Р и что ~А~ > (к + 1)1. Сделайте вывод о том, что Р содержит более 1 ребер. д. Докажите, что если кратчайший увеличивающий путь для М содержит 1 ребер, то размер максимального паросочетания составляет не более )М)+ )(г ~,/(1+1). 005 Глава ЗК Задача о максимальном аотоке е. Покажите, что число повторений цикла гереа! в данном алгоритме не превышает 2чеЩ. (Указаниее насколько сможет вырасти М после итерации но- мер ч'!Ц?) ж. Предложите алгоритм для поиска максимального множества не имеющих общих вершин кратчайших увеличивающих путей Ры Рз,..., Рь для заданного паросочетания М, время работы которого составляет 0(Е). Заключите отсюда, что суммарное время выполнения процедуры Ногскогт-Кхкв составля- ет 0(ъГУЕ).
Заключительные замечания Транспортные сети и связанные с ними алгоритмы рассматриваются в работах Ахуя (АЬп]а), Магнанти (Майпапй) и Орлина (Ог!(п) [7], Ивена (Ечеп) [!02], Лоулера (Еачч!ег) [223], Пападимнтриу (Рарагйпшпои) и Стейглица (Бзе(81!зг) [269], Таржана (Таг]ап) [328]. Широкий обзор алгоритмов для задач поиска потоков в транспортных сетях можно найти также в книге Голдберга (Оо!бЬегй), Тардоса (Тап)оз) и Таржана [!38]. В работе Шрайвера (8сЬг]'чег) [302] предлагается интересный исторический обзор исследований в сфере транспортных сетей. Метод Форда-Фалкерсона представлен в работе Форда (Реп!) и Фалкерсона (Ри!Ьегзоп) [108], которые являются основоположниками формальных исследований ряда задач в области транспортных сетей, включая задачи поиска максимального потока и паросочетаний.
Во многих ранних реализациях метода ФордаФалкерсона поиск увеличивающих путей осуществляется с помощью поиска в ширину; Эдмонде (Ебшопбз) и Карп (Кагр) [101] (и независимо от них Диниц (П!и!с) [88]) доказали, что такая стратегия дает полиномиальный по времени алгоритм. Диницу [88] также принадлежит идея использования "тупиковых потоков" (Ыос81п8 Лоччз); предпотоки впервые предложил Карзанов (Каггапоч) [201]. Метод протаякивания предпотока описан в работах Голдберга [135] и Голдберга и Таржана [139]. Голдберг и Таржан приводят алгоритм со временем работы 0(Уз), в котором для хранения множества переполненных вершин используется очередь, а также алгоритм на основе использования динамических деревьев, время работы которого достигает 0(УЕ !8(Ъ'з(Е + 2)).
Некоторые другие исследователи разработали алгоритмы проталкивания предпотока для поиска максимального потока. В работах Ахуя и Орлина [9] и Ахуя, Орлина и Таржана [10] приводятся алгоритмы, использующие масштабирование. Черняв (СЬепуап) и Махешвари (МаЬезЬчап) [61] предложили проталкивать поток из переполненной вершины с максимальной высотой. В работе Чернява н Хейджерапа (Найегпр) [60] предлагается использовать случайные перестановки списков соседей; другие исследователи [14,203,274] развили данную идею, предложив искусные методы дерандомизации, что позволило получить ряд более быстрых алгоритмов. Алгоритм, предложенный Кингом (К!пй), Рао (йао) и Таржаном [203], является самым быстрым из них — время его работы составляет 0(УЕ 1обедч ! ч) У).
Вбб Часть г7. Алгоритмы длл работы с графами Асимптотически самый быстрый из известных в настоящее время алгоритмов для задачи максимального потока разработан Голдбергом и Рао 1137), время его Работы Равно О(ш1п(Ъ'з~з, Е'~з) Е )8((гз(Е+ 2) 18 С), где С = шах(и и)бн с(и, О). Этот алгоритм не использует метод проталкивания предпотока, он основан на нахождении тупиковых потоков. Все предыдущие алгоритмы, включая рассмотренные в данной главе, используют некоторое понятие расстояния (в алгоритмах проталкивания предпотока используется аналогичное понятие высоты), где каждому ребру неявно присвоена длина 1.
В этом же алгоритме используется другой подход; ребрам с высокой пропускной способностью присваивается длина О, а ребрам с низкой пропускной способностью — длина 1. Неформально при таюм выборе длин кратчайшие пути от истока к стоку будут иметь высокую пропускную способность, следовательно, потребуется меньше итераций. На практике на сегодняшний день при решении задач поиска максимального потока алгоритмы проталкивания предпотока превосходят алгоритмы, основанные на увеличивающих путях и линейном программировании. В исследованиях Черкасски (СЬегказвку) и Голдберга 162] подчеркивается важность использования при реализации алгоритма проталкивания предпотока двух звристик. Первая состоит в том, что в остаточной сети периодически выполняется поиск в ширину, чтобы получить более точные значения высот. Вторая эвристика — зто "звристика промежутка" (бар Ьеопзбс), описанная в упр.
26.5.5. Авторы пришли к заключению, что наилучшим вариантом метода проталкивания предпотока является вариант, в котором для разгрузки выбирается переполненная вершина с максимальной высотой. Наилучший известный к настоящему времени алгоритм поиска максимального паросочетання (описанный в задаче 26.6) был предложен Хопкрофтом (Норсгой) и Карпом (Кшр) [175); время его работы составляет 0(ига'Е). Задачи поиска паросочетаний подробно рассматриваются в книге Ловаса (1,оиазх) и Пламмера (Р!шшпег) (238).
Введение В этой части содержатся избранные темы теории алгоритмов, расширяющие и дополняющие материал, изложенный в данной книге ранее. В одних главах вводятся новые вычислительные модели, такие как комбинационные схемы или параллельные вычислительные машины. Другие главы охватывают специализированные области знаний, такие как вычислительная геометрия или теория чисел. В двух последних главах обсуждаются некоторые известные ограничения, возникающие при разработке эффективных алгоритмов, а также излагаются основы методов, позволяющих справиться с этими ограничениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
