В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 38
Текст из файла (страница 38)
Опрепелить матрицы доспоквмости и сильной связности дан орграфов с матрицами смежности ив задачи 8. 1О. Пусть орграф О задан матрицей смежности. Определить матрицу сильной связности 5 (О). Исполшуя алгоритм 4.1, кайте количество номпонеит сильной связности арграфа О и опре.лелить матрицы смежности этих компонент. Построить изображения орграфа О и его компонент сальной связности.
Рассмотреть случаиг Ого ы е) ОООООО ) 100000 4.2. ЗАДАЧИ ПОИСКА МАРШРУТОВ (ПУТЕЙ) В ГРАФЕ (ОРГРАФЕ) 4.2.1. Поиск маршрута в графе При решеннв некаюрых прикладных залач дередко возиикаег необходимость найти маршрут, соединяющий заданные вершияы в графе 6. Приведем алгоритм решеивя этой задачи. Алгоритм 4.2 (алгоритм Тэрри) поиска маршрута в ашэюм графе 6 (У, Х), соединяющего заданные вер!пины с, ющу, где с~И. Если, исходя из вершины о и осуществляя последовательный переход от каждой достигнутой вершины к смежной ей вершине, руковолствоваться следующими правилами; !) идя по произвольному ребру, всвкий раа отмечать направление, в котором оно было пройдено; 2) исходя нз некоторой вершвны о', всегда следовать талька по тоыу ребру, которсс не было пройдено илн было пройдена в противоположном направлении; 3) для всвкой вершины о', отличной от з, отмечать первое заходящее в о' ребро, если вершина с' встречается в первый раз; 4) нсхоля нз некоторой вершины с', отличной от а, по первому заходящему в э' ребру идти лишь тогда, когда нет других вазможностей, то всегда можно найти маршрут в связном графе 6, соединяющий двс заданные вершины о, ю.
Пример 4.!7. Используя алюрнтм Тэрри, найти маршрут, соединяющий сь сг, е графе 6, изображенном нз рис. 4.!4. Поиск вер!пвнм сг в 6 будем осуществлять так, как будть мы ничего ие знаем об этом графе (можно себе представать. что граф 6 — это схема лэбнранта, где сг — выход нз нега, а с,— развилка, нз которой мы начинаем попон выхода).
На рис. 4 15 показан ох:и: сз возможных вариантов движения по графу 6 согласно алгоритму Тэрри. Пронумерованными пунктирными э '5 мгг" Ч г, б б~ и 3г г Рнс. 4.гв Рас. 4.!4 дугами помазана схема движения па графу 6. Знакамн )( поьгечены первые заходящие в вершины ребра (пометка делзвгся ближе к той вершине, в которую ребро заходит). Указанная на рис. 4.15 схема движения соответствует маршруту с,сга,ото,ггсг. !за Отметим, что после того, как иа вершины о, зашли в вершину о, (см.
дугу 3), в силу ираэила 4 мы не можем вернуться в оь так каи имеются другие возможности, а (оь с,) является первым заходищнм в о, ребром. Далее, после того, как нэ вершины о«зашли в вершину о» (см. дугу ог, в силу правила 2 мы не можем аернуться а вершину оь а и силу правила 4 не можем идти к вершине оь н тел~ самым остается единственная воэлюм. ность — идти к вершине о,. Обо«исааки« я»гори»ма Терра Допустим, что, руководствуясь этим алгоритмом, мы остановимся з некоторой вершние и (ие достигнув вершины ы), и эсе ребра, ннцидентные и, уже пройдены в направлении из и (тогда в силу правила 2 мы уже не сможем выйти нз и).
Покажем, что в этом случае: а) вершина и соепадаст с о; б) все вершины графа б являются пройденными. Докажем сначала спрзаедливоси утверждения «а». Есан и пс совпадает с о, то пусть в вершние и мы побывали й раз (включая последний). Тогда ребра, инпидентиые и, были иройдепы й раэ ио направлению к и и 6 †раз н направлении нэ и (так как число заходов э и, за исключением последнего. сшмаегствует числу исходов нз втой вершины). Таким образом, ис. пользуя то. что по предположению были пройдены зсе ребра, инпидентные и, э направлении из и, а также то, что в силу прааила 2 по кажлому ребру, ницидентному и, разрешается идти не более одного раза в напраеленнн иэ и, имеем 6(и) =6 †, а это противоречит тому, что по направлению к и было пройдено й различных (см.
сноаа правило 2) ребер, а следовательно, 6(и)ри ~й. Полученное прстиеорсчие подтверждает, что и=о. Доиаже»г теперь справедливость утверждения «6». Пусть (см. утзержление «а») о,оь..оь где о,=о„=о, (4.10) есть последовательность першин, расположенных в том же порядке, а каком мы пх проходилн, действуя согласно алгоритму. Очевидно, что (4.10) является маршрутом в графе О (точнее, сокращенной записью ьгаршрута).
Покажем, что маршрут (420) содержит все аершины графа О. Предварительно докажем, что каждое ребро, инпидентное любой вершине о» где 1щ)(й, было пройдено по одному разу в обоих направлениях. Доказательство проведем иидукцней по ). Базис индукции. Поскольку в замкнуто» маршруте для каж. дой содержащейся в нем вершины число всходов из эюй пер. шины равно числу заходов и нее, то в силу того, что согласно Утверждению «а» и правилу 2 асс ребра, н~шндентпые аершинс оь были пройдены по разу в направлении из и (т.
е. мм 6(о) рва исходили иэ и), получаем, что ровно 6(о) раэ мы захадилн в и, а поскольку з силу правила 2 каждый раз мы ааходили а о по попому ребру, то э результате все ребра, инцидент- 161 пые вершине о,=о, были пройдены ио разу в обоих паправле. пнях. Икдукгкенмй шаг. Допустим, что прн некотором 1, где 2(1(л, доказываемое утверждение верна для всех вершин оь ., ог ь Докажем его для вершимы ог.
Если при некотором 1<( выполняется ог=ол то справедливость доказываемого утверж. денна для вершины о, вытекает вз того, что по ицдуктнвноцу прехположепмю она верно для вершины ог. Пусть теперь у1ш еп(1, 2, ..., ) — 1) о,~от, т. е, вершина ог встретилась в первмд раэ. Тогда (ог ч ог) — первое ааходяшее в вергпнну ог ребро, п по нггдуктнвйому предположению оно будет пройдено в обоих направлениях, что в салу правила 4 всоможно лишь в случае, когда есе остальные ребра. инцкдентнме оь будут пройдены в папранлении из оь Далее, поскольку в замкнутом маршруте, кап уже отмечалось ранее, для каждой вершины, содержащейся в этом маршруте, число исходов из зтоб вершины равно числу заходов в нее, то, используя правило 2, ггоэучаем, что все ребра, инцндентные ои будут пройдены по разу в обоих направлениях.
Итак, каждую вершину в маршруте (ЯЗО) мы прахолим вместе со всеми смежиымн сй вершинами. откуда в силу связности графа 6 следует, что маршрут (4.10) проходит через все вер. шины графа 6, а это противоречит нсигдному предооложенню, что вершина ю не была достигнута. Замечание 4.14. Ллгоритм 4.2 н его обоснование остагстга в силе н для случая, когда 6 — связный псевдограф. Замечание 4.16. Если псевдограф 6=(У, К) не является связным. то с иомошью алгоритма 4.2, исходя нз произвольной нержины эшУ и помечая ирайденные вершины н ребра, можно выделить компоненту связности псевдографа 6, содержащую вершину о. Ллгорнтм закончит свою работу в тот момент, когда в первый раз невозможно будет уловлетворвть правилу 2 (т. е мы пришли в аергпггну и, в все ребра, ннцидентиые зюя вершине, пройдены в направлении нэ и; при этом, как похавав чри обосновзинп алгоритма 42, в=о).
Залечлкиэ 4.17. Из полученного с помощью алгоритма 4.2 маршрута всегда можно выделить простую цепь, соепиниюшугю о, - (см. утперждсние 4.4). 4.2.2. Пояс» цутей (маршругоа) с манимальныы числом дуг (Ребер) Путь в оргрзфе О нз вершины о в вершину и, где о~ы, пазы. застоя ликилалэкыл. если ои имеет мнннмельную длину орехи всех путей орграфз 0 пз о в ю. Лналогичио определяется и минимальзыд мзрвгрут в графе 6.
Расснотра» некоторые свойства минимальных путей (марш. ругов). 1ЭГ Утаервшв(нс 4.21. Любой миллмогьимй лргь ( аригруг) ле- ллетсл простое целью. Доказательство проведем длп пути (для маршрута ана ана логично). Предположим, что в некотором арграфе О пашелсп манпмальный путь я=шик..ол, где о,чьоз.
не являющийся про. стой цепью. Тогда найлутся гюмера !. ! такне, что 1щ!((~д я иг «!. Пусть !>1, )(й. Рассмотрим путь оь,.огаты..мь. Сго длина равна (! — 1)+(й — О=а+! — ! — 1<а--1, шо противоре- чат мннамальнасгн и. Случаи г=! пл» 1=2 доказываются ан»- логнчно (случая 1 1, 1=2 быть не мажет а снлу ШФиз). Утаержденне 4.22. (о минимальности подлуги минимально- го луги). Оусчз я и,аг. см где шчвам — минимальный луге (мершруг) е орграфе О (е графе О). Тогда длл любмк камерон 1, ) такиг, «то 1(!(!м.й. путь ( аршруг) пе агиыг...и! также яаляегсл лгияималькмм. Доказательство проведем для орграфа О (для графа О апо аналогично).
Заметим, чю е силу !Оь! выполняется Шчьа! (см. утверждение 421). Еудем считать, чта !)1, ((й (случал, ког- да 1 1 штл 1=-2, рассмотрите самостоятельно). Тогда и= =ягОяеОяз, где пг=игш.,аг, «с=а!с!+и..иь — оугн в О. Прелпо- лагая. что путь не пе являетсн минимальным, получаем, что в О существует путь не пз ег в и! меньшей длины. Но тогда денна пути «=пгОшОпь равняя сумме длин путей пь щ, пг, меньше длнны путя и, рашюй сумме длин путей аь «е, мь ччо противоре- чат минимальности и, поскольку я, тзк же как л н, является пу- тем в О яз и, в им Р «ар и теперь *зшчу пикк .амишз«емо пега (изрмргы!.
Вш. аш еиюерме мм зги~к». Птст О (у. Х) — серей, му, у,шг'. Овшш еи О(е) (и У)(, )мП вЂ” Ер з герм М (ишП(, е) Х) — ерсечрв грези е: О(уд О Ь( ! — с- мУ, РЕЗ МШМЕ З ЕРМ УЕ О-'(Уд = О О-'(Ю вЂ” ЕРМЕО М»М З* щ мршм у,. Огшь с (у. 2) — взр. му, у,ш Р. Омееач ш ! (имр((к в)мХ) — ссре зер и; С(У) О С( ! — Р еву, и окасге згрммг У,. Пусть О=(У, К) — орграф с лрл2 вершянамя н о. в — за- данные всршнны аз У, где отав. Опишем алгоритм поясна мн. нвмальпого ну ш кз и в в в орграфс О (аггоритлг фронта возим).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
