Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 157

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 157)

Н + ю(и, е). Доказательство. Если непосредственно перед ослаблением ребра (и,е) мы имеем е.а' > и.а' + ю(и,е), то после ослабления е.а = и.й + ю(и,е). Если же перед ослаблением е. о < и. а + ю(и, е), то ни и. а, ни е. а не изменяются, так что после ослабления е.а' < и.а+ю(и,е). Доказательство. Согласно свойству верхней границы, если в некоторый момент до ослабления ребра (и, е) выполняется равенство и. И = б(в,и), то оно остается справедливым и впоследствии. В частности, после ослабления ребра (и,е) мы имеем е.а' < и.а+ ю(и,е) = б(в, и) + ю(и, е) = б(в, е) (согласно лемме 24.13) (согласно лемме 24.1) .

Согласно свойству верхней границы е. Н > б(в, е), откуда мы делаем вывод о том, что е. 4 = б(в, е), и зто равенство впоследствии сохраняется. Ламма 24.15 (Свойство ослабления пути) Пусть С = ($7, Е) представляет собой взвешенный ориентированный граф с ве- совой функцией ю: Š— ! Ж, а в е 17 — исток. Рассмотрим произвольный кратчай- Лемма 24.14 (Свойство скодимоети) Пусть С = (1Г,Е) — взвешенный ориентированный граф с весовой функцией ю: Е -+ К, в Е 1' — исток, а в и — ! е — кратчайший путь в графе С для некоторых его вершин и, е е 17.

Предположим, что граф С инициализирован процедурой 11ч1т1ле1ее-б11чсее-бопксе(С, в), после чего выполнена последовательность шагов ослабления, включающая вызов процедуры Кеелх(и, е, ю). Если в некоторый момент времени до вызова выполняется равенство и. а' = б(в, и), то в любой момент времени после вызова справедливо равенство е. а = б(в, е). Часть 11 Алгоритмы длл роботы с грифами 71г ший путь р = (ео, еп..., ьь) из истока в = ио в вершину оы Если граф С инициализирован процедурой 1гг1т1лшхе-бпчсье-бопкси(С, л), а затем выполнена последовательность ослаблений ребер (ио, гч), (иы из),..., (иь м ц,) в указанном порядке, то после этих ослаблений и в любой момент времени впоследствии выполняется равенство иь.с1 = б(л,оь). Это свойство справедливо независимо от того, производятся ли ослабления на других ребрах, включая ослабления, которые чередуются с ослаблениями ребер пути р.

Докаэаягельства По индукции покажем, что после ослабления л'-го ребра пути р выполняется равенство о,. с) = б(л, и,). В качестве базиса примем 1 = О; перед тем как будет ослаблено хотя бы одно ребро, входящее в путь р, после процедуры инициализации очевидно, что ео. Н = л. Ы = О = б(л, э). Согласно свойству верхней границы значение в. Н после инициализации больше не изменяется. На каждом шаге индукции предполагается, что выполняется равенство гг, пЫ = д(л,о; 1), и рассматривается ослабление ребра (о, ми,). Сопгасно свойству сходимости после этого ослабления выполняется равенство го Н = б(л, о,), которое впоследствии сохраняется.

Ослабление и деревья кратчайших путей Теперь покажем, что после того, как в результате последовательности ослаблений оценки кратчайших путей сойдутся к весам кратчайших путей, подграф предшествовання С„образованный полученными значениями к, будет деревом кратчайших путей для графа С. Начнем с приведенной ниже леммы, в которой показано, что подграф предшествования всегда образует корневое дерево с корнем в истоке. Лемма 34.1б Пусть С = (17, Е) представляет собой взвешенный ориентированный граф с весовой функцией ю: Е -+ К, а в е Ъ' — исток. Предполагается также, что граф С не содержит циклов с отрицательным весом, достижимых из истока ж Тогда после инициализации графа с помощью процедуры 1ьпт~лшхп-б1кпье-боцкся(С, э) подграф предшествования С, образует корневое дерево с корнем в, а любая последовательность шагов ослабления ребер графа С поддерживает это свойство в качестве инварианта.

Доипаягельсягво. Изначально единственной вершиной графа С, является исток, и лемма тривиальным образом выполняется. Рассмотрим подграф предшествования С, возникающий в результате последовательности шагов ослабления. Сначала докажем, что этот граф ациклический. Чтобы получить противоречие„ предположим, что после некоторого шага ослабления в графе С, создается цикл.

Пусть это цикл с = (оо,иы ..,,иь), где иь = ио. Тогда для) = 1,2,...,л выполняется равенство по гг = о, и и без потери общности можно считать, что цикл был создан в результате ослабления ребра (гь ы еь) графа Сл. Утверждается, что все вершины цикла с достижимы из истока л. Почему? Для каждой вершины цикла с существует предшественник (т.е. значение соответ- Глава л4. Кратчайшие аута из одиой вершииы ствуюшего атрибута отлично от значения м1ь), поэтому каждой нз этих вершин сопоставляется конечная оценка кратчайшего пути, когда ее атрибуту я присваивается значение, отличное от значения ып.. Согласно свойству верхней границы, каждой вершине цикла с соответствует вес кратчайшего пути, из чего следует, что она достижима из истока з. Рассмотрим оценки кратчайших путей, которые относятся к циклу с, непосредственно перед вызовом процедуры йн.лх(оь 1, иы ла) и покажем, что с — цикл с отрицательным весом, а это противоречит предположению о том, что в графе С не содержится циклов с отрицательным весом, достижимых из истока.

Непосредственно перед вызовом для 1 = 1, 2,..., й — 1 выполняется равенство ть 11 = и1 1. Таким образом, для 1 = 1, 2,..., к — 1 последним обновлением величины еп Н является присвоение и;.Ы = и1 1. 11+ ли(и1 1,ил). Если после этого значение Ш 1.Ы изменяется, то оно может только уменьшаться. Поэтому непосредственно перед вызовом пРоцедУРы йн.лх(иь 1, иы чо) выполнЯетсЯ неРавенство и1.л' > ол 1.Н+ш(и1 1,и1) для всехл= 1,2,...,)с — 1. (24.12) Поскольку величина иь.

я в результате вызова изменяется, непосредственно перед этим выполняется строгое неравенство иь.е) > гь 1.1) +ли(иь 1,иь) . Суммируя это строгое неравенство с й — 1 неравенствами 124.12), получим сумму оценок кратчайшего пути вдоль цикла гл ь ь и1. д > ~~~ (ил 1. 11 + ш(и1 1, и1)) 1=1 1=1 ь ь аа,~ и*-1 «+~~ Ми1-1,и1) Однако поскольку каждая вершина цикла с входит в каждую сумму ровно по одному разу.

Из этого равенства следует 0 > ~ ло(и1 1, и,) . Таким образом, суммарный вес цикла с — величина отрицательная, что н приводит к желаемому противоречию. Итак, доказано, что С вЂ” ориентированный ациклический граф. Чтобы показать, по он образует корневое дерево с корнем а„осталось доказать Часть И. Алгоритмы длл раьоты с нгафами ;=чы у, Рис. 24дя Иллккчрапиа того, что простой путь в графе С ит истока л в вершину о — единственный. Если иыеютсв дав пути, рг (л и к -+ л ~ с) и рт (а и у -+ л о), где к Ф р, то л. л = к и а.

к = р, что приводит к противоречию. (см. упр. Б.5.2), что для каждой вершины и Е 'г7 в графе С имеется единственный простой путь из истока в в вершину и. Сначала необходимо показать, что из истока в существует путь в каждую вершину множества И . В это множество входят вершины, значение атрибута и которых отлично от значения )ч)е, а также вершина в.

Идея заключается в том, чтобы доказать наличие такого пути из истока в в каждую вершину множества И по индукции. Детали предлагается рассмотреть в упр. 24.5.6. Чтобы завершить доказательство леммы, теперь нужно показать, что для любой вершины и е И в графе С существует не более одного пути из вершины в в вершину и. Предположим обратное. Другими словами, предположим, что из истока в существует два простых пути в некоторую вершину тл путь ры который можно разложить как в ь и х -+ к о, и путь рз, который можно разложить как в и - у -+ г и, где х ф у (рис.24.9). Однако в таком случае выполняются равенства л.п = х и л.тг = 11, откуда следует противоречие х = р.

Мы заключаем, что в графе С существует единственный путь из истока в в вершину и, а следовательно, этот граф образует корневое дерево с корнем ш Теперь можно показать, что если после некоторой последовательности этапов ослабления всем вершинам присвоены истинные веса кратчайших путей, то подграф предшествования С представляет собой дерево кратчайших путей. Лемма 2417 (Свойсгнво нодграфа предшесгнвовяння) Пусть С = (Ъ; Е) представляет собой взвешенный ориентированный граф с весовой функцией тл: Е -+ К, а в Е 'тг — исток. Предположим также, что граф С не содержит циклов с отрицательным весом, достижимых из вершины в.

Вызовем процедуру 11ч1т1Ае1ге-бнчаее-бо()ксе(С,в), после чего выполним произвольную последовкгельность шагов ослабления ребер графа С, в результате которой для всех вершин и Е 17 выполняется равенство и.г( = 6(л,п). Тогда подтраф предшествования С является деревом кратчайших путей с корнем в. Дояазангельснгвгк Необходимо доказкгтч что для графа С выполняются все три свойства, сформулированные на с. 685 длд деревьев кратчайших путей.

Чтобы доказать первое свойство, необходимо показать, что Ъ' — множество вершин, достижимых из истока ш По определению вес кратчайшего пути 6(в, и) выражается конечной величиной тогда и только тогда, когда вершина о достижима из истока в, поэтому из истока в достижимы только те вершины, которым соответствуют конечные значения г(. Однако атрибуту о. д вершины и е И вЂ” (в) конечное Глава 24.

Кратчайшие аута ил одиой вершины 725 о1(р) = ~ ~ш(о1 1,о;) 1кн ь < ~~ (б(в,о;) — б(в,о, 1)) = б(з,оь) -б(з,оо) = б(в, оь) (в силу "телесюпичности" суммы) (посюльку б(в,оо) = б(в,в) = О) . Таким образом, ш(р) < б(з, оь). Поскольку б(з, оь) является нижней границей веса любого пути из в в оы мы заключаем, что чо(р) = б(в, оь), и, таким образом, р является кратчайшим путем из в в о = оь. Упражнении 24.5.1 Для ориентированного графа, изображенного на рис. 24.2, приведите пример двух деревьев кратчайших путей, отличных от показанных.

24.5.2 Приведите пример взвешенного ориентированного графа С = (й, Е) с весовой функцией о1: Š— > )й и истоюм в, для которого выполняется следующее свой- ство: для каждого ребра (и, о) е Е существует дерево кратчайших путей с юр- ием з, содержащее ребро (и, о), и другое дерево кратчайших путей с юрием в, в котором это ребро отсутствует. 24.5.3 Усовершенсгвуйте доказательство леммы 24.10, чтобы она охватывала случаи, югда веса кратчайших путей равны оо и — оо. 24.5.4 Пусть С = ()л, Е) представляет собой взвешенный ориентированный 1раф с исто- юм з, инициализированный процедурой 11ч1т1лпв-Бн аьв-Бо15ксв(С, в).

До- кажите, что если в результвге выполнения последовательности шагов ослабления значение присваивается тогда и только тогда, когда о.я ф ып.. Таким образом, в множество $в входят только те вершины, которые достижимы из истока в. Второе свойство следует непосредственно из леммы 24.16. Поэтому остается доказать справедливость последнего свойства для дерева кратчайших путей: для каждой вершины о Е *еи единственный простой путь в- о в графе С вЂ” это кратчайший путь в 1рафе С из истока в в вершину о.

Характеристики

Список файлов книги