Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 164
Текст из файла (страница 164)
Задачи 25.1. Транзитивное замыкание динамического графа Предположим, что нужно поддерживать транзитивное замыкание ориентированного графа С = (У, Е) по мере добавления ребер в множество Е. Другими словами, после добавления каждого ребра нужно обновить транзитивное замыкание добавленных до этого времени ребер. Предположим, что граф С изначально не содержит ребер и что траизитивное замыкание должно быть представлено в виде булевой матрицы.
а. Покажите, каким образом транзитивное замыкание С' = (У, Е*) графа С = (У, Е) можно обновить в течение времени 0(Уз) после добавления нового ребра в граф С. б. Приведите пример графа С и ребра е, такой, что обновление транзитивного замыкания после добавления ребра е в граф С будет выполняться в течение времени П(Уз) независимо от используемого алгоритма. в. Разработайте эффективный алгоритм обновления транзитивного замыкания по мере добавления ребер в граф. Для любой последовательности и добавлений общее время работы этого алгоритма должно быль равно 2,", ~, = О(Уз), где ~, — время, необходимое для обновления транзнтивного замыкания при добавлении 1-го ребра.
Докажите, что в вашем алгоритме достигается указанная граница времени работы. 25.2. Кратчайшие пути в е-плотнам графе Граф С = (У,Е) называется е-плотным (с-белье), если ~Е~ = 6(У~'ь') для некоторой константы с в диапазоне О < с < 1. Если в алгоритмах, предназначенных для поиска кратчайших путей в с-плотных графах, воспользоваться дарными неубывающими пирамидами (см. задачу 6.2), то время их выполнения может быть сопоставимо со временем работы алгоритмов, основанных на применении пирамиды Фибоначчи. При этом удается обойтись без сложных структур данных.
а Чему равно асимптотическое время работы процедур 1ызккт, ЕхткАст-М~н и Вкскелзв-Кеу как функции от кратности о и количества п элементов г)- арной неубывающей пирамиды? Чему равно время работы этих алгоритмов, если выбрать о' = 6(но), где О < сз < 1 — некоторая константа? Сравните эти времена работы с амортизированными стоимостями этих операций для пирамиды Фибоначчи. 745 Даава 75. Крашчайшие пути между всеми парами вершин 6. Покажите, как за время О(Е) вычислить кратчайшие пути из единого истока в е-плотном ориентированном графе С = (Ъ; Е), в котором отсутствуют ребра с отрицательным весом. (Указание: выберите величину Ы как функцию от е.) в. Покажите, как за время 0(Ъ'Е) решить задачу поиска кратчайших путей между всеми парами вершин в е-плотном ориентированном графе С = (Ъ; Е), в котором отсутствуют ребра с отрицательным весом.
* Покажите, как за время 0(Ъ'Е) решить задачу поиска кратчайших путей между всеми парами вершин в е-плотном ориентированном графе С = (Ъс, Е), в котором допускается наличие ребер с отрицательным весом, но отсутствуют циклы с отрицательным весом. Заключительные замечания Неплохое обсуждение задачи о поиске кратчайших путей между всеми парами вершин содержится в книге Лоулера (1.аш!ег) [223], хотя в ней н не анализируются решения для разреженных графов. Алгоритм перемножения матриц он считает результатом народного творчества.
Алгоритм Флойда-Уоршелла был предложен Флойдом (Р!оуб) [104], который основывался на теореме Уоршелла (%агапа!1) [347], в которой описывается, как найти транзитивное замыкание булевых матриц. Алгоритм Джонсона (УоЬпзоп) взят из статьи [191]. Ряд исследователей предложили улучшенные алгоритмы, предназначенные для поиска кратчайших путей с помощью умножения матриц. Фридман (Ггес)- шап) [110] показал, что задачу о поиске кратчайшего пути между всеми парами вершин можно решить, выполнив 0(Уз7з) операций сравнения суммарных весов ребер; в результате получится алгоритм, время работы которого равно 0(Ъз(1б !к Ъ/!я У)'7з), что несколько лучше соответствующей величины для алгоритма Флойда-Уоршелла.
Хан (Нап) [158] сумел сократить время работы до 0(Уз(!а!к Ъ"/1к У)574). Еще одно направление исследований показывает, что к задаче о поиске кратчайших путей между всеми парами вершин можно применить алгоритмы быстрого умножения матриц (см. заключительные замечания к главе 4). Пусть 0(п ) — время работы самого производительного алгоритма, предназначенного для перемножения матриц размером и х и; в настоящее время и7 ( 2.376 [77]. Галия (бай!) и Маргалит (Магйа!й) [122, 123], а также Зайдель (БеЫе!) [306] разработали алгоритмы, решающие задачу о поиске кратчайших путей между всеми парами вершин в неорнентированных невзвешенных графах за время (Ъ""р(Ъ')), где р(п) обозначает функцию, полилогарифмически ограниченную по и.
В плотных графах время работы этих алгоритмов меньше величины 0(Ъ'Е), необходимой для Щ поисков в ширину. Некоторые исследователи расширили эти результаты и разработали алгоритмы, предназначенные для поиска кратчайших путей между всеми парами вершин в неориентированных графах с целочисленными весами ребер в диапазоне (1,2,..., ЪУ).
Среди таких алго- 74б Часть КС Алгоритмы дла работы с графами ритмов быстрее всего в асимптотическом пределе ведет себя алгоритм Шошана (ЯЬозпап) и Цвика (2ди!с)4) [314], время работы которого равно 0(Ы717 р(ЪгИ7)). Каргер (Кагйег), Коллер (Ко!!ег) и Филлнпс (Р]йй[рз) [195], а также независимо Мак-Геч (Мсйеос!4) [245] дали временную границу, зависящую от Е*, подмножества ребер из множества Е, входящих в некоторый кратчайший путь. Для заданного графа с неотрицательными весами ребер эти алгоритмы выполняются за время 0(Ъ'Е*+ !7з 18 Ъ').
Это лучший показатель, чем ~)7!-кратное выполнение алгоритма Дейкстры, если !Е" ~ = о(Е). Басвана (Вляпала), Харихаран (Наппагап) и Сен (Зеп) [32] исследовали декрементные алгоритмы для поддержки кратчайших путей между всеми парами вершин и информации о транзитивном замыкании. Декрементные алгоритмы позволяют выполнять последовательность чередующихся удалений ребер и запросов; задаче же 25.1, в которой ребра вставляются, напротив, требуется инкрементный алгоритм. Эти алгоритмы Басваны, Харихана и Сена рандомизированные, и, когда путь существует, их алгоритм для транзитивного замыкания может ошибаться с вероятностью 1/и' для произвольного с > О.
Время выполнения запросов с высокой вероятностью равно 0(1). Что касается транзитивного замыкания, то амортизированное время для каждого обновления составляет 0(Ъ 47з 18~7з Ъ'). Для кратчайших путей между всеми парами вершин время обновления зависит от запросов. Для запросов, которые должны выдавать только веса кратчайших путей, амортизированное время одного обновления составляет 0(Ъ'з[Е18з Ъ'). При поиске фактического кратчайшего пути амортизированное время обновления Равно ш1п(0(Ъ~7зьг!8 Ъ'), 0(Ъ~(Е 1бд Ъ')). ДеметРескУ (!Зешезгезси) и ИтальЯно (!4а!!ало) [83] показали, как работать с операциями обновления и запросами, когда ребра и вставляются, и удаляются, и при этом каждое ребро имеет ограниченный диапазон возможных действительных значений. Ахо (Апо), Хопкрофт (Норсгой) и Ульмаи (1Л!шап) [5] дали определение алгебраической структуры, известной как "замкнутое полукольцо".
Эта структура служит общим каркасом для решения задач о поиске путей в ориентированных графах. Алгоритм Флойда-Уоршелла и описанный в разделе 25.2 алгоритм поиска транзитивного замыкания — примеры алгоритмов поиска путей между всеми парами вершин, основанных на замкнутых полукольцах. Маггс (Маййз) и Плоткин (Р!о!(пп) [239] показали, как искать минимальные остовные деревья с помощью замкнутых полуколец. Глава 26.
Задача о максимальном потоке Так же, как дорожную карту можно смоделировать ориентированным графом, чтобы найти кратчайший путь из одной точки в другую, так и ориентированный граф можно интерпретировать как некоторую транспортную сеть и использовать для решения задач о потоках вещества в системе трубопроводов.
Представим, что некоторый продукт передается по системе от истока, где данный продукт производится, к стоку, где он потребляется. Исток производит продукт с некоторой постоянной скоростью, а сток с той же скоростью его потребляет. Интуитивно потоком продукта в любой точке системы является скорость его движения. С помощью транспортных сетей можно моделировать течение жидкостей по трубопроводам, движение деталей на сборочных линиях, передачу тока по электрическим сетям, информации — по информационным сетям и т.д. Каждое ориентированное ребро сети можно рассматривать как канал, по которому движется продукт.
Каждый канал имеет заданную пропускную способность, которая характеризует максимальную скорость перемещения продукта по каналу, например 200 литров жидкости в минуту для трубопровода или 20 ампер — для провода электрической цепи. Вершины являются точками пересечения каналов; через вершины, отличные от истока и стока, продукт проходит, не накапливаясь. Иными словами, скорость поступления продукта в вершину должна быть равна скорости его удаления из вершины. Это свойство называется свойством сохранения потока; в случае передачи тока по электрическим цепям ему соответствует закон Кирхгофа. В задаче о максимальном потоке мы хотим найти максимальную скорость пересылки продукта от истока к стоку, при которой не будут нарушаться ограничения пропускной способности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
