В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 40
Текст из файла (страница 40)
Величину ![я) будем называть длииой луги я а нагруженном орграфе Р. Ранее так называлось «олнчество дуг в пути п. В связи с этим заметим, что если длины дуг выбраны равными 1, то !(я) выражает введенную ранее длину пути и в ненагруженном орграфс Слсковательно, любой ненагруженный орграф можно считать нагруженяым с длинами дуг, равными 1. Лпалагично определяется и нагруженный граф, а также длина маршрута в нем. Путь в нагруженном арграфе Р ич вершины и в вершину и, где очи за, называется минимальным, клн он имеет мииималь. ную ллину среди всех путей орграфа Р из о в ы.
Аналогично определяется н минимальный марпгрут в нагруженном графе 6. Если в нагруженном арграфе Р имеются аамшгутые пути отрицательной длины, то длн заданных вершшг с, ю орграфа Р, где о чь ю, минимального пути из о в ю может не быть. Действительны если в Р имеется замкнутый путь о отрицательной длины и существует путь нз о в ю, прохолящий хотя бы через одну вершину, содержащуюся в о, то очевидно, что а Р найдется путь я из о в ы вила я = п,ОоОяг, где яь и, — пути в Р (аозможио также, чю лмбо ль либо яз является пустой последовательна. стью; при этом предполагаем, что ИОо = оОИ = и).
Но тогда я~ОоОсОпь я,ОоОсОаОкг, ... танже дутя в Р из и е ы, и ллина каждого следующего пути в этой последовательности отличается от длины предыдущего на !(а)(0, а значит, длины путей из о в ы могут принимать сколь угодна малые отрвцательные значения. Аналогичная ситуация имеет место в случае, когда в нагруженном графе 6 вершины е, ю находятся в одной компоненте связности, содержащей хотя бы одно ребро отрицательной длины. В таких случаях имеют смысл лишь задачи певека нинимальных пуши (маршрутов) среди путей (маршру.
тов), число дуг (ребер) в которых ограничено сверху. Приведем некоторые свойства минимальных путей [маршрутов) в нагруженном орграфе Р (У, Х) (графе 6 = (У, Х)): !) если УхшХ ![к))0, то любой минимальный путь (маршрут) является простой цепью; 2) Есля о,пз...оь — минимальный путь (маршрут), то для лю бых номеров ь !! таких, что !щ!()(й, нуть (маршрут) игоыы.пг также являешя мннимальяым; гзп 3) если и...ию — минимальный путь (маршрут) срелн путей нз и в ю (среди маршрутов, соединяющих и, ге), содержащих нс более 5+1 дуг (ребер), то и...и — миннмальйь>й путь (маршрут) среди путей из и в и (среди маршрутов, сиединяквпих и, и), со. держащих не более Ф дуг (ребер).
Свойства 1 — 3 доказываются аналогично утверждениям 4.21 и 4.22. Рассмотрим теперь задачу поиска минимальных путей (мар- шрутов) в нагруженном арграфе (графе). При этом тля опреде- ленности рассуждения будем проводить дли орграфа (для графа они аналогичны). Зииечаиие 422 При решении некоторых практи >ескнх зада'г ваэнниает необходимость поисиз максимальных путей а нагру- женном орграфе.
Такая задача легко сводится и нсследуемой ниже задаче поиска минимальных путей заменой знаков прн длинах дуг на противоположные Пусть О (1', Х) — аагруженный орграф, У = (иь ..., и ), в>2 Введем величины Х>гэ>, где ! 1... и, 2=1,2 ... Для каж- дых фиксированных ! и й величина Х,>"> равна дание минималь- ного нуги среди путей нз а, в и>, содержащих не более й дуг; сслп жс таких путей нет, то 4>з>= >. Кроме того, сети произ- вольную всрп>нну ишр считать путем вз и в и нулевой длины, то величины Л>1"> можно ввести также н для й=б, при этом Х !л> О Х.>э> — 1 2 л (4.14) Ваекеи также в рассмотрение ивадратную матрипу С((>) =[за) яоряака в с элементами /1(иь ад, силн (и>, и>) шХ; >, если (иь и!)~Х, которую булем называть могуицсй длин дуг нагруженного ор- графа В.
Слеяуюшее утеерждепис дает простые формулы для вычисле- ния величии Х>>и. итыэа>зшш 4.22. пр ! -2,, и, ею о лю лн л р еи р Х,а > ю>з !Л>>м ! л>,), (4. Рй) 1Ш!Шл э р ! 1. Э ж О и>рилэалилэ рил лгээ ХУ '> ю1п(а; м>п (Л>>*'->-л,11. (4.1б). !Ш!лжя Пусть !ш (2, ..., л), й~й. Докажем справеллнвость (4.15) (хо- казательстно (4.15) проводится аналогично с учетом того, что Хби О). С>бозначии правую часть (4.15) через Х>1"л". Покажем сначала, что Л>>л+ > В, 1,11>э (4.17) 1ЗВ В случае л,»»О нэрээевстьс (417), ьчевнгвь, эизь еэетск пгса тгВЭЭЬ Л,» О< и Г Э,...Э».Э вЂ” ПУТЬ НЭ Э, В Ээ»эдььиэшаа НЕ Ы Щ а+ 1 дуг, такой, пь цн) = лщэ'!.
Тьглэ (сн. свез»тес 31» ' ннвэнэгигиэ путь среди путей ш э, в э ', с месмьмэк ве алле а нгг, э ггь гьвьтэгьгь. ли э'! ця)=цн)+цэь, э,) ш !».+с н> м1п (л» »+с»й л»»ль ! ! <гейл с. э иэраэантвь (4.17) ипьгвяегсэ г в этом случае. Покажем палее, что 7, ьь»> < 1»ььч (4.18) В случае Лшэ'1 - вэрьэс»э вь (4ДЗ]. Очэьвгио. эивогвяеня Пгсгь еперь Л»ьэ'»< н Гш(1, Х, ..., О) — венгр аеьа, что Л»и», + с», пвп (Л»"11 + сн) 1»»"+»!. 1 <1<в Тогда в салу 74»Ь+»!<со имеем Л»Э!э<с, ею<со. в следоватшп но, (шч о!)шХ, с»,»=й(о»н о») и существует путь и', содержа. .щвй не более д дуг, такой, что 1(п') лгьг»ч но тогда для пуш »п=нОоьоь содержащего не более Д+1 дуг, выполняется 7.,!ЬЬО < 1(п) Л(эгр + с»О ЛР+О, т.
е, (4.!8) справелливо я в этом случае Используя утверждение 4.23, нетрудно описать алгоритм на- хождения таблицы значений величин Л»аг (будем записывать ее в ш!де матрицы, где 1 — номер с~роки, Д+ ! — номер столбца). .Действительно, используя рекуррентиые соотногпения (4.18), (4.!8) н исходя нз (4.14), последовательно определяем набор величин Л»!41, ..., Л !ы ((й+1)-й столбец матрнды), начиная с Д=О, а затем шаг зв шагом увеличивая значевие й до любой необходимой величины.
будем теперь предполагать, чш в 0 отсутствуют простые контуры отрицательной длины (ниже н утверждении 4.27 приво. лптся простой метод проверки этого условия). Для дальнейших рассуждений нам понадобятся дополнительные утверждении. Утверждение 4.24. Нв всякого гимннугого айги отрицатель- .ной длины можно выделить пр»ютой контур отрицательной дм»ны. Утверждение 4.24 доназыввется аналогично утверждению 4Л. Иэ утвержлепия 4.24 следует, что справедливо Утверждение 4.28. Если в нагруженном орграфс отсутствуют .простые контуры отрицательной длиньь го в нем нет и замкну тых путей отрицательной длины.
Утверждение 4.2Ц В нагруженном орграфе, в котором агсзт сгниют простые контуры отрицательной длины. можно ез всыш .го незамкнутого пути выделить простую цегю с теми же начагэ. ноа и конечной вершинами, длина которой нс прении»ает длшиг' исходного лутц !ЭО Доказательство будем проводить нмдунцией по А — колвчвству луг в пути. Прк А 1 утверждение 4.Ы выполняется, поскольку всякий незамкнутый путь с одной дугой является простой цепью.
Предположим, ыо прн всюпорам Амй утверждение 4.26 выполняетсз дая всяксгс незамкнутого мути, содержащего ие более А — 1 луг. Покажем его справедлвжхчь н для каждого незамкнутого пути я, солержащего ровно А луг. Пусть и к~и ... я,м.
Рассмотрим любые две вершины и. иь где 1(!( (!!жй+1, такие, что иг и„Если таких вершин йег, то ч— простая цепь, и тогда даказйваемое утаержденке справедливо. Вели же уназалиме вершины нашлггсм то рассмэтриаэем «уть я' = и, ... ш,и! ... пю (т. е. предполагаем, что гж2! случай =1 разберкте самостоятельно), а также путь и" и,иг„, и!. Очевидво, что Ц я ) ! [ я ) + 1 ( п ) (4.19) По условиям доказываемого утверждения (см. также утверждение 4.2!) зыполнястса Ця") ЖО, отнула н силу (429) Ця')( сЦя).
Заметим, шо я' — путь, солсржаш~й не более А — 1 дуг„ а следовательно, по индуктивному предположению из исто вюжис выделать йрсстую цепь и из п, и пю, такую, что Цс) ( (Ця') ч: Ця). Всспокьэоваешпсь тем, что числа дуг в простой цепи не превосходит л — 1, из утверждения 4.26 получаем, ео-перши, что Дэгэ! Ъгг 'г, ! 2, —. и, при всех А~п-). (4.2)) Во.вторых, если Агмюз ю (где !а(2, ..., л)), тс еергвнна о не постижима пз оь а есля дгГ г(ю, тс ог дссгкжпма из ог и прн этом Х,!"-С вЂ” ллпна минпмалького пути нз о, в оь Таням образом, по Эгг"-'! можно судить о дссгижимсстн вергпвн оь! 2.:..
л, пз эь а также апрепелять длины минимальных путей нз с в достижимые першины. Учитывая (4.20), огрэннчимся рассмотрением величин 4мг нрп А=О, 1, ..., я — 1. Заметим, что Эти!=О, А=1, 2. Раеенства (4.21) являютсэ следствкем (4.16), а также тато„ что а В отсутствуют замикутыс путя отрацатсльной длины (см. утверждение 4.26). Зплсчпипе 4.26. При овределенпн нагруженною орграфэ ыы предполагали, что велкчииы Цх), хшд, конечны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
