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