В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 39
Текст из файла (страница 39)
Дл р 4.2г !Оаг !. Помечаем аершнну и пндексом б. Затем намечаем вершины, прпкадлежащне образу вершпны о, индексом 1. Инв кгество вершин с индексом 1 обозначаем рйг,(о). Полагаем 4=1. О! г 2. Если Руга(о)=ЕГ нла выполняется й=л — 1, вй( Ирйгз (и), то вершмпа в не достнжнма ав и, н рабата алгорит- 1КЧ ма на июм заканчивается, В пратнваом случае переходам к ша. у 3. Шаг 3.
Если юшРВь(и), то ыэрсходнм к шауу 4. В противном случае существует путь нэ и в аз длины й, н этот путь яв. ляется минимальным. Последовательность вершнн июзюз- Фз ю где ы,,шРВа,(и)ПО- (ы); зга-зщуфз-з(и)ПО 'фщ — з); (4.11) юнщРЮ (и)ПО '(ги ), н есть искомый ынннмальпый путь нз и в ш. На этом ращпа алгарнтма эаквичнваегся. Шаг 4. Помечаем индекса» й+1 асс непомеченные верша. кы, поторые принадлежат образу множества вершнв с индексом й. Множество вершин с индексам й+1 обозначаем РВ'зы (и), Прпсванвэем й: =й-1-1 н переходны к шагу 2. Замечание 4.13.
Маожеспю РВ'з(о] в алгоритме 4.3 обычно называют фронтон волны й-го уровня Замечание 4.!У. Вершнны гиь ..., юз-з яз (4.11), вообизе говора, могут быть еылелены неоднозначно. Эта иеаднозначщзсгь сщлвсштвует случаям, когда сущесгвуег песколько разлнчнык мннималгшых путей на и в ю.
Нетрудно описать алгоритм, позволяющнй наховмть все минимальные пути яэ и в ю в орграфе О [опнзнпте этот алгоритм самостоятельно). Припер 4.18. Используя алгоритм 4.3. определим маникальной путь пз и в из в аргрвфе О, заданном матрнпей смежности, прелсгавлеяяой в табл. 4.4. Действуя согласно алгоритму 4.3, последовательно апределвем ряз (и )=(и„иП; рйгз(у)=О(рйг(из))з(иь оь аз)= =(оз, гь); Рйзз(оз)=О(РВГК(и))з(из, из, из, из. гз)=(из).
Таким образом, изщупгз(из), а значит (см. шаг 3), существует путь нз из в из длины 3, п этот путь является мвннмзльным. Надаем теперь мнннмальный путь нз из в из. Определим мно. РВз(из)ПОы(из) =(из, из)П(оз, оз) (из, из). Выберем любую вершину нз пайленаого миожсства, напри. мер вершину иь Определяя далее множество Рйзз(гзз)ПО-'(из) =(и . из)П(оь из, из)=(иь из).
Выберем мобуза вершнну нз найденного множества, наприыер вершнну из. Тогда и,ищзиз — «скомый чннвмальный путь аэ и, в из (планы 3) в арграфе О. 1ае Таблмяа 44 оэ е, о Обое«оаоиие илгоритпи 4.8. Введем для»аждого йщ(1, ... п — !» множество Вь(о), состоящее пя всех вершим ищу. достплгммых нв и, в таки», что длина минимального пут» лв и в и равна й. Кроме того, полагаем йга(и) = (о). Докажем, что справедлива рекуррепт»ап формула В'ьт-,[и) =Ю (йгь[и))'т [) В'4(и), 2=0. 1, ..., и — 2. (4.(2) Пу ть й ш (О, 1,, л — 2).
Паквкем сначала, чта м аш ство нэ шаай частп рааепсп э (4.12) с дери» с» а мнопсспп «а правой ша часта. Пусть ш У н(и]. Рэссмогрпм ннпимээжмй угь П «э э и аргр бе О П шределеп»в маомесгаа Ю ь [а) такой уть суапстеует, к па»л»~ш раапл 4+ 1. Пусть и' — яершппе а атом путн, «епасрештапяю а(машестауюша аршине и. тагда е'шгг (е) (ам ут срмдс «е 421), откуда алу «шО(а') ааЛУЧасс «ШР(ГУ ( )).
ИСК ЛЬаУЯ тЕШРЬ О, Чта ив йт„т,(а), а СЛЕШ»м. тель»о.«щ)у(а),1 д. 4,» семешО(Ш«(э))ч О йг,(а). Пак хшм теяера, чт вп«еспв на пр*еой чаатн раамшт а (4.12) са- лар нтся е маапшше э левай его чшт«. Пусть «шО(в' ( Нч О й ("). Т гла салу ив О(вг (а)) верши»а и шютшкамэ»э э п аря эш» аушест. ауе у ь даням а+1 вэ в и пакагкем, что ио пут.
«еэаетс» нна- аа ( скула буде следовать чт*»шм,( )). Дейшшпотьно, пред«овика чта мннпмэ ямй путь «э т в и в арграфе О амэе ллппу г. гае гж(ща, получаем ишшг(а), лата пр т»варечат тану, та щ Р вг,( ) Тэк» образам, ф рнула (4.12) пал»астма дока«а«э. Оба«пачки даню шгш бр( ) н апа та сех шршнн ргр фа О. гв и ° «пгник аэ а.
И падшуя ут ер~кденш 4Ю (а ашке тат с»шеншшй факт, ч, !2-(игр гбй давка анаоа еро ое чш» а- р а воч ор рафе О е шчвы з г — !!. ыштчзеи, зе сареевмиез ф р Гве ы(1 О У (г)- (4ЛЗ) ПереГшем теперь непосредственно к обоснованию алгоритма 4.3. Прежде всею заметим, что ГВ, (о)= В', (о) (см. швг 1) н посаедовательное нахождение множеств Рута(о) при 2;шу по алгоритму 43 (см, шаг 4) производятся аналопшно носледова. тельномУ постРоснию множеств руе(е) па РекУРРешпоб фор. муле (4.12), т. е. выделяемые в алгоритме 4.3 ииожесгва Рбтг,(о) совпадают с введенными выше множествами Ва(о), Но то~да из опрепеленин множеств Юа(о) следует, что миин- МаЛЫЮЕ ЧНСЗЮ а, ПРИ КстОРОМ МШВГа(О), И бУДЕт ДЛИИОй ЫНЮЬ мальишо пути из о в ш в орграфе О, 'по соответствует шагу 3 (очевидно, что мажет существовать лншь единственное число Д, ври котором мщВа(и)).
Если же шщща(о], 2=1, 2, ..., л — 1, то в силу (елб) вершина м вс достижима иэ о. что также шютветствует логике алгорятма (см. шаг 2). Осталось обосновшь существование вершин ыь ..., ма и уловлетворяющик (4.11). Этн вершины набдутси, твк квк в салу (4.12) выполняетсв Ууг(и)щО(щш (о)), г=!, 2., л — 1. а следовательно, Чгш(1„ 2...„л — !), Унщб)г(о) найдется вершин» йщВ'г (о) такаа, что (иТ и)шХ, т.
е. и'щВ'г (о)ПО-"(и), откуда У!щ(1, 2... л — 1), УищВг(о) Вг г(о)йбг'(н)чьИ. Замечание 426. Если выражения О( ). О'( ) заменить нэ 6(.), то при соответствующем изменении терминологии алгоритм 4.3 и его сбосш>ванне переносятся и нв поиск минимального маршрута в неориентирозанном графе 6. 4,2.3. Расспшнин в граФе Пусть 6 (у, Х) — грзф (и общем случае — псевдограф). Заметим, па если вершины о, м щ У, где и те ы, можно соедингпь маршрутом в С, то обязашльна существует минимальныд маршрут, соедиаяющиб вершин» о, м. Действительно, если некоторыя маригрут И Лпины д не является ниинмальнйм, то сущесг аует иаршрут бг длины а ( а . Если и ыаршрут т!з не «вляеыл минимальным, то имеетсЯ маРшРУт бз длины а ( а, и т.
д Оче. видно. что такое уменьшение длины маршрута можно понторить пе !юлее Ь вЂ” 1 раэ (тэк как минимальная длина маршрута раева !). Поэтому в С обяаатеаьно найдется минимальный маршрут, соединяющий вершины ш ы. Обозначим длину этого ыарш. рута через б(о. ге). Положим также б(». о) =б вля любоб вершным ощу. Кроме иго, пусть ъ'о, мщу б(ош) =-1- ю (далее для краткости вместо + о пулем писать г), если иглы и в 6 не существует маршрута, соелнняюшего о, ш. Тен самим мш гав опРеделплп вслнчннУ Н(о, в) дла любых веРшнн а, в ш У, Пе.
лнчнпу 6(ю, ею) (нонечную алн бесконечную) будем называть рассгазиыеа лежду вершинами ю, в. Расстояние Н(а, в) удавлетворяет аксномам метрики: 1) д(»,в) м О, причем Н(ю,в) =- О чогпа н голыш тогда, когда а ее; 2) Л(ю, в) = 6(щ о); 3) 6(о, в) ж б(ю„и) + Н(и, в), гле ю, и. в — произвольные всршнны графа О. Кроме того, в связном графе С для любых его вершнн и, в вмаолняетсн 4) 6(о, в)( Свойшва 1, 2 н 4 очевидны.
Докажем справедливость свойства 3. В случае 6(и, и) = ялв б(и, в) юе свойство 3, очевидно, выпопняется. Пусть теперь б(ю, и] ( ю, 6(ы, в) ( а следовательно, е О существует мшуимааьный маршрут ш, соединяющий о, и, п минимальный маршрут цз, соедяняющнй и, в. Рассмотрнм маршрут ШОПь соедпнягощый ю, в. Его Лпнпв равна б(ю, ы) +Н (и, в), откуда я следует справеплнвссгь свойства 3. Зомгчаиие 4.2!. Используя понятно рассгояяня, можно теперь рассмотренные ранее множества В'е(о) ввести для неорнентираванного графа О = (У, Х) следующим образоме Я'е(ю) = (в щ ео У(б(ю, в) 1), тле у=О, 1, ..., п(С) — 1, и щ К 4.2.4. Диаметр, рюгнус н центр графа Пу ъ 6 (У, Х) -«в зеыа граф (ыы з юзшеы у ае — вседа.
граФ). у пм ез е а(6) и а(, ы) а заема ыиваюв зевы. ы ышу зв д в рю графе о Пу е — пр иоаьюя еры аз з У В в«з ( ) пыз П . ы) ив и (оызза а. ы с «) зе аепя е апиыы уд (ш иыщиюпеаы) з рафеоа ер выю. Рыыр граф 6 з з е гез е ечевз (6) - ыы ( ). му' Лиаз вр е а ва екез, и* ( 1 г(6). зевы и Ч ре гр»- Ф 6. Пример 4.19.
Для графа С, нзображенного на рнс. 433, имеем: Н(С) 3, г(а,) = 3, г(из) = 2, г(из) 2, г(а ) 2, г(оз) 3, г(С)=2; юь юз, щ — нентры графа О. р . ув е 12' гау 4.2.2. й[ивималыпие пути (маршруты) в иагруткеиных ерграфах (графах) Назовем орграф Р (У, Х) яазрушеллмл, если на множестве дуг Х определена некоторая функция 1:Х В, которую часто называют аесоаой функцией Тем самым в нагруженном орграфе Р каждой дуге х ен Х поставлено п соответствие некоторое действительное число Цк), Значение !(х) будем называть длиной дуги х. Для любого пути и нагруженного орграфа Р обоаначим через 1(я) сумму длин входящих в я дуг, при этом каждая дуга учитывается столько раз, снолько она вкодит в путь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
