Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 37
Текст из файла (страница 37)
Рассмотрим упорядоченный граф, изображенный на рпс. 7.18. Первый обход по глубине из начальной вершины о< определяется следующим образом: о<~ пз, щ. пВ, пб, пь «3~ пь У 5,3. Обход по шприяе. Пусть С = ((о„..., о«), (5,,, ... ..., Х,„)) — упорядоченный граф. Выберет< начальную вершину и, и предположим, что Ь«,= ((о.< ю<), (о.< <з«) ° ° ° ~(п<~ пА)).
Первые й-<-1 члепов г определяются следующим образом: и««, = з„п,<ю = <а<, ", о.<«+«и<м а уз<вы+о 239 является 1-й вершипой иа Е„, ие входящей в Ф. Это $ исчерпывает 5„,, и процесс пачипается иад Ь, и т.д. Обход прекращается, когда все вершины, достижимые 2 иа Рве. 7ЛВ иа и.оь содержатся в !. Замечапия иэ и. 5.2 о едипствепности, свяапостп и числе возможиых обходов также применимы к етому обходу. Обход графа по швриие можпо найти с помощью следующей ороцедуры: ! играет ту же роль, что и прежде, а д — оставшаяся часть в процедурах сложеипя и удалепия (аббд и йе!е!ео соответствеиио) ргосебоге Ь|! (о) г(и) - ! ргосевв тег!ех и !пй!аПхе д тг!!Ь и тгЬ!!е д'Ф'О бо Ьеа!и Йе1е!е с(е, р) !огюш5, ио Ьей!и !! г(ю) 0 !Ьеп й Ьей!и абб д(ю, е) !(ю) - ! ргосезв тег!ех ю еш! епй епо епбргос Пример 5.2.
Первый обход по ширине графа в примере 5 ! с пачальпой вершииы о~ вадается следующим 240 образом: ви оз, оз, и„ о„ ом и„ оз, У 5.4. Остовыые леса обходов по глубкые ы шпрпые. Пусть С ((оь ..., о„), Е) — граф, а г о„|„..., ои„>— обход С. Тогда Г определяет подмножество Е' из Е следующим обравом: [о, ш)жЕ' тогда и только тогда, когда [о, ш[ используется прп построеыпи обхода. Так как для упорядочевыых графов обход г определяет аналогичным путем подсписок Ь, каждого списка Т„то Ь, получают Ф из Ь, удалеыыем всех пар (о, и), которые ие использо.
вавы в сечении. Предложепие. Пусть С ((о„...,о„),[Е„, ч ° ° 5ю„~) — упорядоченный связный ераф, а з — обход по елубине или ширине ерафа С. Тоеда "* ((оы ° ° ° 1 от) (Тт ~ ° ° ° т 5ю )) есть упорядоченное остоеное дерево для С. Доказательство. Так как С вЂ” связыый граф, то подграф С' также связеы и является остоввым для С. Если С' содержит замкыутый маршрут, тогда некоторые вершиыы появляются более одного раза в г, по так как г — обход, то ото ыезозможво, и С' является ацикличыым графом. Следовательно, С' — дерево. е Следствие.
Каждый связный граф имеет остоеное дереза. е* Рлс. 7Л9 Пример 5.3. Для графа пз примера 5Л остовыыми деревьями, определеыыыми первпчпыми обходами по глубиые и шарипе с начальной вершиной ои будут деревья, изображевыые соответствеыпо ва рыс. 7.19,а и 7.19,5.
$6 д ктк, г, веаэ Для графов, не являющихся свяэнымп, полные обходы по глубине влп ширине определяют остовный лес. Упражнение 75, 1. Пусть С ((о„...,од), [Е,,, ..., Е, )) — упорядоченный граф, определяемып следующими списками: ((о1 од)) 542 ((12 16) (12 о4) (о2' од) (д 2 1 1)) ~42 ((о21 ид))4 ~4 ((од о2)ю (о41 од))! ~4 ((одд о4)1 (дд' ОЗ))' Определить: а) обход по глубине с начальной вершиной от, б) обход по ширине с начальной вершиной о,. 2. Нарисовать останные деревья, соответствующие обходам упражнения 7.5Л. 3.
Пусть ыатрпца смежности графа С имеет блочную структуру А, О А, О А„ где каждое А6 является квадратной матрнцей с булевыми алементами, а все остальные элементы равны нулю. Что ыожно скааать о свойствах С7 4. Написать процедуры на каком-нибудь языке программярования для определения обходов по глубине и ширане. $6.
Ориентированные графы 6Л. Введение. Во многих приложениях теории графов требуется, чтобы ребра графа иыели направление. Например, поток данных проходит через программу. О и р е д е л е н и е. Ориентированный граф (орграф) С есть пара С (У, Е), где У вЂ” конечное множество вершин, а Š— произвольное подмножество УХ 'дт.
в" П р е д л о ж е п и е. а) Ориентированный ераф С *('дт, Е) определяет отношение на Г. б) Пуста дт — конечное множество. Тогда отношение на т' олредеяяет ориентированный граф, у которого множество вершин — )т, 444 Доказательство. а) Как н в т 1, определим В(Е) следующим образом: оВ(Е) ие тогда п только тогда, когда (и, ие) ж Е. Очевидно, что Л(Е) — отношение. б) Если  — отношение на )л, то ориентированный граф С (е', Е), определяемыб Н, имеет множество ребер Е, где (о, й)ж Е, тогда и только тогда, когда оВю.
е Направленяе ребра обозначают порядком в е' Х У; например, если (о, и)ие Е, то говорят, что ребро выходит из и и входит в и. На диаграмме в атом случае для указания направления используют стролки. Пример бЛ. Пусть ее (о1, из, ов), а Е1 ° ((оь оз), '(оз, оз), (иь о~)). Тогда матраца смежности и изображение орграфа 6~ (е', Е1) будут такими, как на рис.
7.20. О 1 0 001 1 0 0 ие из Иееддажение матиииа емежнести Ряс. 7.20 Аналогично на рис. 7.2) приведена матрица смежности и иаображенне графа бз (У, Ее), где ЕЗ ((и1> О~)е (Н1~ ОЗ)е (ОЬ ОЗ)~ (ОМ ОЗ)е (Ое "~)) Поскольку реберное отношение для орграфа пе обязательно симметрично или нерефлекспзпо, то, вообще 11 1 О 0 1 0 0 яа ~зина смененесми Леедрижение Рвс. 7.21 говоря, не обязательно, чтобы А Ае плп Аи О. Ребра типа (и, и) называют петлей.
Степень 6(и) вершины ож У может быть записана в виде суммы 6(и)-6-(о)+ -1 6+(и), где 6 (о) — число ребер, входящих в о, а 6+ (и1 — число ребер, выходящих из о. Ыножества 1зе 2И (ин (и, и)жЕ> и (ин (щ ю)юЕ> вазьтвают соответствеиво входящим узлам и выходящим узлом вершины иж >т. Понятия зквпвалевткостп и пометки обобщаются па орграфы естественным образом. 6.2. Маршруты и связность в орграфах, Оп редел ев не. Маршрутом длины >с пз и в ю в орграфе С (>т, Е) пазывается последовательность ребер вида (Р, Ш1), (юь юг), (юм газ), °" (шс-г и'а-~) (юз-ь ю) т. е.
вторая вершива каждого ребра совпадает с первой вершпиой следующего ребра. тт Часто удобно представлять маршрут последовательвостью вершин и, и'ь юз, °, иъ а юз-ь ю которые его определяют. Если а-ш, то маршрут иазывают замкнутым маршрутом или циклом. Орграф беа циклов называется ацикличныл. Теоремы 2 2 также справедливы с аиалогпчкымп доказательствами для орграфов. Определим связность плп матрицу достижимости тем же самым способом. Заметим, однако, что для орграфов отвошевке >>е ве является отвошевпем эквпвалевтвостп ва >т п, следовательво, пе осуществляет раабиевпя >т. Пусть Ж обозначает миогкество всех орграфов, а У— множество всех графов.
Мы можем определить отображение У: >У> — У следующим обрааом. Определение. Пусть С (>т, Е)ю>й>. Тогда мяожество вершки Г(С) ы У совпадает с >т, а множество реоер Р(С) определяется врпмевеппем следующих операций ка Е: з) удаляются все петли из Е; б) (щ ш) заменяются па [о, ш) для всех (щ и)юЕ. Тогда Р(С) является графом, связанным с орграфом С. Р Для орграфов иовятпе связиости является более содержательным, чем для графов, и имеет отпошевке к проблеме обхода. Сейчас мы определим три важных типа связности орграфа.
Определевпе. Если С (>т, Е)-орграф, то будем говорить, что: а) С слаба заленый, еслк граф Р(С) связный; б) С односторонна ссязный, если для каждой пары различвых вершин о, юю >т существует маршрут из и в га или обратно, 244 в) С сильно свлзныб, еслн для каждой пары разлпчных вершпн о, ш ш У существует маршрут нз о в ш и обратно. Х Очевидно, что С сильно связный «С односторонне связньш ~6 слабо связный. Пример 6.2. Иа рпс. 7.22 мы видны, что орграф: а) толыш слабо связный (рпс. 7.22,а); б) односторонне связный, но не спльно связный (рпс. 7.22, Ь); в) сильно связный (рпс.
7.22,с). Рас. 7.22 В термпнах свяаностп матрицы С А (Яз) орграф б сильно связный тогда и только тогда, когда Сэ ! для всех 1 < 1, ! и; б односторонне свяаный тогда и только тогда, когда Се ~l Ср, 1 для всех 1 < 1, у < я. П р н и е р 6.3. Рассмотрим орграф, представленный днаграммой на рпс. 7,23. Для этого орграфа А (!7) А (г)з)— поэтому для С !~ А (!!') = 7 )~ А (Л) )!' А (П-') ~/ А (77з) Ч А (Л') а-о 2!э О 1 О 1 О О 1 ! О О 110 01, А(В')- О О 1 О 1 1 О О О О 1 1 1 О 1 1 1 1 1 А (В') 1 1 1 1 О О 1 1 О 1 О 1 1 О 1 ! 1 1 О 1 ! 1 1 1 О 1 1 О О 1 О 1 О 1 О ! 1 1 1 ! 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 О 1 имеем С»,= 1 для всех 1 < 1, 1< 5 и, следовательно, граф является сильно связным. Для более аффективного вычисления С можно использовать алгоритм Уоршолла, »» Если С (Р, Е) — орграф, то можно разбить (т путем определения отношения зквпвалептяости р следующим Рас.
7,24 Рас. 7.23 1111 0110 0010) 0011 А(Ее) А(р) Таким обрааом, С» ((и»), 21) (1<1<4) являются сильно связными компонентамн графа. д Пусть С (У, Е)-ациклвческий орграф. Вершину и»я т' называют листом, если б+(и) О. Если (и, и»)»и Е, то и является непосредственным предком »и, а ю — непосредственным потомком и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
