Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 144
Текст из файла (страница 144)
Рассмотрим оценки кратчайших путей, которые относятся к циклу с, непосредственно перед вызовом процедуры Кн Ах(оь ы оь, и) и покажем, что с — цикл с отрицательным весом, а это противоречит предположению о том, что в графе С не содержится циклов с отрицательным весом, достижимых из истока.
Непосредственно перед вызовом для г = 1, 2,..., Iс — 1 выполняется равенство я [ог] = сг ь Таким образом, при г = 1, 2,..., й — 1 последним обновлением величины 0 [та] является присвоение г1 [о;] — г1 [и; з] + и (ог ми;). Если после этого значение И [о; г] изменяется, то оно может только уменьшаться. Поэтому непосредственно перед вызовом процедуры КБ.АХ(оь г, оь, и) выполняется неравенство г1[о;] > д[ог т]+ш(сч ыо;) для всех г = 1,2,...,Й вЂ” 1. (24.12) Поскольку величина тг [пь] в результате вызова изменяется, непосредственно перед этим выполняется строгое неравенство 1[оь] > 1[оь-г]+го(оь-ыоь). Суммируя это строгое неравенство с 1с — 1 неравенствами (24.12), получим сумму оценок кратчайшего пути вдоль цикла с: ь ь ~~г г([ог] > ~~ (г([тг з]+ю(ег ыо;)) = г=1 г=1 и [ог-1] + „,~ то (ог-1, %) г=1 Однако ~~> г([сч] = ~~> И [сч з], поскольку каждая вершина цикла с входит в каждую сумму ровно по одному разу.
Из этого равенства следует 0 > ~ ы (иг ы о;). Таким образом, суммарный вес цикла с — величина отрицательная, что и приводит к желаемому противоречию. Глава 24. Кратчайшие пути нз одной вершины 699 Рис. 24.9. Иллюстрация того, что путь в графе С из истока з в вершину с — единственный Итак, доказано, что ф— ориентированный ациклический граф. Чтобы показать, что он образует корневое дерево с корнем в, осталось доказать (см. упражнение Б.5-2), что для каждой вершины с Е 'г' в графе С имеется единственный путь из истока а в вершину гг. Сначала необходимо показать, что из истока з существует путь в каждую вершину множества Ъ'„. В это множество входят вершины, значение атрибута я которых отлично от значения гчгг., а также вершина ж Идея заключается в том, чтобы доказать наличие такого пути из истока з в каждую вершину множества У„ по индукции.
Детали предлагается рассмотреть в упражнении 24.5-6. Чтобы завершить доказательство леммы, теперь нужно показать, что для любой вершины гг е У в графе С существует не более одного пути из вершины з в вершину гг. Предположим обратное. Другими словами, предположим, что из истока а существует два простых пути в некоторую вершину тл путь рг, который можно разложить как в - и - к -~ я - и, и путь рз, который можно разложить как а - и - у -~ к - с, где х ф у (рис. 24.9).
Однако в таком случае выполняются равенства к [л] = х и гг [з] = у, откуда следует противоречие х = р. Приходим к выводу, что в графе С существует единственный путь из истока а в вершину с, и, следовательно, этот граф образует корневое дерево с корнем в. П Теперь можно показать, что если после некоторой последовательности этапов ослабления всем вершинам присвоены истинные веса кратчайших путей, то подграф предшествования Ск — это дерево кратчайших путей. Лемма 24.17 (Свойство подграфа предшествования). Пусть С = (1г, Е) — взвешенный ориентированный граф с весовой функцией гс: Š— В,, а в е 1' — исток. Предположим также, что граф С не содержит циклов с отрицательным весом, достижимых из вершины ж Вызовем процедуру 1гчгтглг.гамп Бггчпье БОиксе(С, в), после чего выполним произвольную последовательность шагов ослабления ребер графа С, в результате которой для всех вершин с б У выполняется равенство г1(о] = б (а, о).
Тогда подграф предшествования С вЂ” дерево кратчайших путей с корнем в. Доказаглельстао. Необходимо доказать, что для графа С„выполняются все три свойства, сформулированные в разделе "Представление кратчайших путей" для Часть Ч1. Алгоритмы для работы с графами 700 деревьев кратчайших путей. Чтобы доказать первое свойство, необходимо показать, что К, — множество вершин, достижимых из истока а По определению вес кратчайшего пути б (в, о) выражается конечной величиной тогда и только тогда, когда вершина о достижима из истока в, поэтому из истока з достижимы только те вершины, юторым соответствуют юнечные значения Н. Однако величине И [о], соответствующей вершине о е 1' — [з), конечное значение присваивается тогда и толью тогда, когда тг [о] ф мп..
Таким образом, в множество Ъ'„входят только те вершины, юторые достижимы из истока ж Второе свойство следует непосредственно из леммы 24.16. Поэтому остается доказать справедливость последнего свойства для дерева кратчайших путей: для каждой вершины о Е У единственный простой путь з - и в графе С вЂ” это кратчайший путь в графе С из истока в в вершину о. Пусть р = (ос,оы...,оь), где ос = з и оь = о. При г = 1,2,..., к выполняются соотношения д [о;] = б (в, о;) и д [о;] > с1 [о; 1] + ю (о; ы о;), из чего следует, что ю(о; ыо,) < б(з,о;) — б(з,о, 1).
В результате суммирования весов вдоль пути р получаем ь ю(р) = ~~ ю(о; но;) < 1=1 ь < ,'~ (б (в, о;) — б (з, о; 1)) = 1=1 = б (в > оь) — б (з, оо) = = б(в,оь), где предпоследнее равенство следует из "телесюпичности*' суммы разностей, а последнее — из того, что б(з, ос) = б (в,з) = О. Таким образом, справедливо неравенство ю (р) < б (з, оь). Поскольку б(в, оь) — нижняя граница веса, которым обладает любой путь из истока з в вершину оы приходим к выводу, что ю(р) = б(з, оь), и поэтому р — кратчайший путь из истока в в вершину о = оь. И Упражнения 24.5-1. Для ориентированного графа, изображенного на рис. 24.2, приведите пример двух деревьев кратчайших путей, отличных от показанных.
24.5-2. Приведите пример взвешенного ориентированного графа С = (КЕ) с весовой функцией ю: Š— К и истоком в, для которого выполняется сформулированное ниже свойство: для каждого ребра (и, о) Е Е существует дерево кратчайших путей с корнем з, содержащее ребро (и, о), Глава 24. Кратчайшие пути из одной вершины 701 и другое дерево кратчайших путей с корнем я, в котором это ребро от- сутствует. 24.5-4. Пусть С = (У,Е) — взвешенный ориентированный граф с исходной вершиной з, инициализированный процедурой 1ы1т~лшгк Япчсье 801/псе(С, з). Докажите, что если в результате выполнения последовательности этапов ослабления атрибуту к [а[ присваивается значение, отличное от мп., то граф С содержит цикл с отрицательным весом.
24.5-5. Пусть С = (У, Е) — взвешенный ориентированный граф, не содержащий ребер с отрицательным весом, и пусть в е Ъ" — исток. Предположим, что в качестве к [о[ может выступать предшественник вершины е на любом кратчайшем пути к вершине и из истока а, если вершина е Е Ъ' — (а) достижима нз вершины в; в противном случае я [е[ принимает значение ыи.. Приведите пример такого графа С и значений, которые следует присвоить атрибутам к [е], чтобы в графе С образовался цикл. (Согласно лемме 24.1б, такое присвоение не может быть получено в результате последовательности этапов ослабления.) Пусть С = (1г, Е) — взвешенный ориентированный граф с весовой функ- 24.5-6. цией и: Š— ~ Н,, не содержащий циклов с отрицательным весом. Пусть ле Ъ" — исток, а граф С инициализируется процедурой 1ьлтышге Б лчсье Яоцксе(С, а).
Докажите, что для каждой вершины и е Ъ' в графе С существует путь из вершины в в вершину о и что это свойство поддерживается как инвариант в ходе произвольной последовательности ослаблений. Пусть С = (Ъ; Е) — взвешенный ориентированный граф, не содержащий циклов с отрицательным весом. Пусть также з е Р— исток, а граф С инициализируется процедурой 1мт1лшгп Бпчаьп Бо~жся(С, л). Докажите, что существует такая последовательность [Ц вЂ” 1 этапов ослабления, что для всех вершин е Е Ъ' выполняется равенство Н [е[ = Б (а, о).
Пусть С вЂ” произвольный взвешенный ориентированный граф, который содержит цикл с отрицательным весом, достижимый из истока л. Покажите, что всегда можно построить такую бесконечную последовательность этапов ослабления ребер графа С, что каждое ослабление будет приводить к изменению оценки кратчайшего пути. 24.5-7. 24.5-8. 24.5-3. Усовершенствуйте доказательство леммы 24.10, чтобы она охватывала случаи, когда веса кратчайших путей равны оо и — оо.
702 Часть ЧБ Алгоритмы для работы с графами Задачи 24-1. Улучшение Йена алгоритма Беллмана-Форда Предположим, что в каждом проходе алгоритма Беллмана-Форда ослабления ребер упорядочены следующим образом. Перед первым проходом вершины входного графа С = (У, Е) выстраиваются в произвольном порядке сы сз,..., ху~.
Затем множество ребер Е разбивается на множества Еу И Еь, где Еу = ((о;, иу) Е Е: 1 ( )') и Еь = ((о;, оу) б Е: г' ) Я. (Предполагается, что граф С не содержит петель, так что каждое ребро принадлежит либо множеству Еу, либо множеству Еь.) Определим графы Су = (К Еу) и Сь = (К Еь). а) Докажите, что Су — ациклический граф с топологической сортировкой (оы сз,..., оу)), а Сь — ациклический граф с топологической сортировкой (и)) ),о)ч) ы..., о1), Предположим, что каждый проход Беллмана-Форда реализуется следующим образом. Сначала вершины обходятся в порядке сыоз,..., о)ь у и при этом ослабляется каждое ребро графа Еу, исходящее из посещаемой вершины.
Затем вершины обходятся в порядке с)ь ус)ч~ ы..., ип и при этом ослабляется каждое ребро графа Еь, исходящее из этой вершины. б) Докажите, что при такой схеме, если граф С не содержит циклов с отрицательным весом, достижимых из истока в, то после ПЦ/21 проходов по ребрам И [с) = б (в, с) для всех вершин п е У. в) Улучшает ли эта схема асимптотическое поведение времени работы алгоритма Беллмана-Форда? 24-2. Вложенные ящики Говорят, что д-мерный ящик с размерами (хм хз,..., хв) вкладывается (пез1з) в другой ящик с размерами (уы уз,..., Ув), если существует такая перестановка я индексов (1, 2,..., Н), что выполняются неравенства хл(1) < Уы хл(2) < Уз» х~г(н) < Ув.
а) Докажите, что вложение обладает свойством транзитивности. б) Разработайте эффективный метод определения, вкладывается ли один Н-мерный ящик в другой. в) Предположим, что задано множество, состоящее из и д-мерных ящиков (Вы Вз,..., В„). Разработайте эффективный алгоритм, позволяющий найти самую длинную последовательность ящиков (В,„ В;„..., В;,) такую, что для у = 1, 2,..., й — 1 ящик В;з вкладывается в ящик В;з+,. Выразите время работы этого алгоритма через и и Н. Глава 24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
