В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 37
Текст из файла (страница 37)
4.13, являютшс вершины ос. ос, ос, ос. Следующее утверждение очевидно. Утверждеяие 4.14, Если О' — орграф, полученный з рсзульпие удаюиил иесколькил вершин из орграфа О, го А(О') лолу- чается из А(Р) е рслульгитс удаления строк и столбцов, соог. зсггтзующш удаленным вершимом Замечание 4.12. Аналогичное утверждение справедливо и для провзвольпык псевдографов (ориеитировавнык н иеорнентирозаиных). 43.8. Матрицы свюиосси Пусть Р (У, Х) — орграф, где У (оь ..., о ). Магрипей досгизсимости орграфа О нззываетшс кзадратнаи матрииа у(Р) =(гсс) порядка л, у которой й1=1, если вершина ос достижима НЗ ос, н !с!=Π— в противном случае. Матрицей силища связности орграфа О называется квадратная матрица 3(О)=(ги) порядка л, у которой за=1, если вершина о, достижима нз ос а одновременно ос достижима из иь и за=Π— в противном случае (т.
е. гсс 1 тогда и только тогда, когда вершины оь о. принадлежат одной компоненте сильной связности орграфа Бг сы. Ушержденне 4.13. п. 3). 1ГЗ Пусть С (У, К) — граф, где У=(иь ..., ь,). Матрицей сюм. насти графа б нааываегся кввдратна» матраца 5(б)=[зп) порядка л, у которой за=!, еслн 1=) нля существует маршрут, сседнняюпщй о„еь к го=о — в нрогнвном случае (т. е. го= ! тогда н толью тогда, когда юрнгнны ш, «г прннадлежат адней компоненте связносгн графа б; сн. утверждение 4.12, о. 2). Воспользовавшись утверждением 4.5, рзвенсгвамн (49), а также тем фактом, что в силу утвержден»» 4.4 пз любого не- замкнушго маршрута нлн пути можно выделать простую цель с теми же начальной н юнечяой вершинами, получим спрзвед.
леность следующих утверждений. Утверагденне 4.15. Пуст 0=(К Х), где У=(»ь ..., о ),— сраф с ьшгрицей сащачосги А=А (б). Тогда 5(б) ыйп (Е+Л+Л'+...+А г)=Е(ТАь )Аь.ту., ь (А где Š— единичное матрица»орьдкь л. Утверашеане 4.16, Пусть О= (У, Х), где У= (ь ь, о ),— орграф с митрицей слвююсти Л=Л (Р!. Ттдаг 1) Т(О) а!гп[Е+Л+Азф... РЛ"-')= шЕ)/А~/Лт,~... 'ЧГЛ"-г . 2) Б(О)=Т(Р)й[Т(О)]', где г — обозна ение операции трангпоннроеанин .»атриды Утвержпення 4.15 н 4йб дают простые. легко реализуемые на ЭВЩ методы вычяслення матриц Я (0), Т(О). 5(Р). Сущест- вуют н более экономичные методы вмчнслеиня этнх натрия.
Опншем, например, метод Уоршелла, осиованный на следую. щем утверждении. Утаерждеине 4.! 7. Пусть А — лгатрица смеэгшмги графа б= =(У, Х) (оргра4ю О=(У, Х)), гое !'=(оь ..., а ). Рассмотрим юсмдоюгельнссть бущюмл кзадратныз матриц Вг" порядка л. где 1=0, 1, ..., н, Вгьг=й'ч(Е, элементы Ьгьгг когорьм ем юсл»- «лся ло смдующей итерационной форму»аз Ш ч М 'ггг()(ог н.бЬ" 'г), где 1 1. 2, ..., л. Тогда 5(С)=Всю (и ссотеьтсгееню Т(О) =Вг"Ц 5(О) =Т(О)й[Т(О)]'). Доказательство будем проводить лл» С (пля О ою *»ало- гично).
Покажем ннлУкпней по 1, что Щ'го 1 тогда н толыю тогда, ногд» лабо 1=1, лнбо существует маршрут, соелнняющнй аг, ег, внутренние аергизны которого принадлежат множеству (о, ..., ог). Йз этого утвержленяя прн !=н следует справеллн- носгь утвержден»» 4.!7. Пре 1=0 элементм Ьг'го матрацы Вгьг= =А'ь1Е очевидным образом удовлетворяют требуемому усль вню. Предположим, что прн некотором 1. где !щ1<:л, знемен- ты Ьгг-гггг также УдовлетноРЯют тРебУемомУ Условны.
Покажюь выполнение этого условия и для элементов Ь!Огг. Пусть !чь! (случай г=г очевилен) и существует маршрут, соединяющий иь оь внутренние вершины которого ггринадлежат множеству (оь .... о,). Докажем, что тогда Ьйгг! — — !. Пусть ц — одни из ташы маршрутов. Будем считать, что г! — простая цепь (иааче. следуя утзерждению 4.4, выделим пз ч простую цепь, соедшгяюшую иг, ог). Если ог не является внутренней вершиной цепи ц, то в салу индуктивного ирсдположения Ьгг-'гц=-1, откуда Ьигь=1тг'(Ьг ц«йбгг-ггг,) =!. Пусть теперь ог является внутренней вершиной цепи тг, т. е.
цепь т! имеет вид ц=цгОць где Чь цг — простые цепи, соединяющие вершины о„ог и иг, иг соответственно, впутренпие вершины которых принадлежат множеству (иь ..., о, Д. Но тогда в силу индуктивного предположения Ьг' иа Ьи-'гц=!, откуда Ьгагг=Ьи 'ггтг'(16!)=1. Пусть теперь Ьигц=1, !чь)! Покажем, что существует маршрут, соединяющий оь оь внутренние вершины котооого поинццлежат множеству (оь ..., о,). В силу того, что Ьгггг= — Ьг цгг!г' 'тl (зггг-иггдгдг' оц) =1, выполняется либо Ьг' — йц=1, либо Ьг'-иг,= =О, Ьг' ца=ы) ггг =1. Если М' — пц=1.
то в силу индуктивного нретположеипя существует маршрут, соединяющий оь оз внутреиане вершины которого принадлежат множеству (о,, ..., ш,). Если Ьгыиц=й, Мьцггг=йг' '>ц= 1, то в силу инлуктивного предположения существуют маршруты ць цг, соединяющие оь иг н иг, с, соатветствспио. внутренние вергпииы которых приналлежат множеству (и,, ..., о,,). Но тогда маршрут шОцг и будетискомыы. Замечание 4.72. Если в утверждении 4.17 заменить Егьг= =А'тг'Е на Вга Етгз!йпА, то оно останется справчливым и для произвольнык псевдографов (ориентированных и неориентпроваииых).
4.! .9. Выделение компонент свизностн Опишем алгоритм вахах<кения числа компонент сильной связности орграфа, а также выделения этих комиоггент. Аналогичным образом решается задача нахожлеиия количества компонент свяаиосгн, а также выделения компонент связности неориентированного графа. Одкзко для определенности приводим рассуждения для орграфа. Воспользуемся слелуюшими утверждениями. Утеергкдение 4.19. Пусть Р— орграф с р~й комзоненгааи «ильнод гзкзносгаг Оь ...,Ог.
Тогда е Рездльтате Удагениз из О агзишн, содеижли(ггхс» з Ро иозрчаем оРгРаф с Р— ! компонента юг сгыьыгг! сзлзносгиг Ое. - Ор. Воспользуемся тем очевидным фактом, что если О' — яомпоиента сильной связности орграфа О. то О' является компонентой сильной связности и любого подграфа орграфа О, содержатцего все вершины и дуги орграфа 09 Используя утверждение 777 4.11, п. 2, заключаем, что после удаления нз Р вершин.
сохержюцнкся в О» имеем орграф В, подграфами которого я»чяютшв Вэ. Ое, а следовательгю. О„..., Р, являются компонеитамч снльйой свяавости орграфа В. Кроме того, в силу утверждения 4.11, пп. 1, 2, получаем, что обьединение множеств першин ор- 8, г афон 0» ..., Р, лает множеспю вершин орграфа О, а значит„ ь, .-, Π— все компоненты сильной связности орграфа Р.
Утверждение 4.19. Пусть О' — камлаиелга синькой сеяэиос. ги орграфа О. Пусть также р(0)ин2 и В" — орграф, логучаьмый е результате удаления иэ О еерииш, содержащиеся е Р'. Тогда матрицами А(В"), 3(0") являются ладмагрицы магрьщ А(Р), Б(О), получаемые е результате удаления из киг строк и столбцов, пюгэетсгзующих еершинал орграфа О'. Утверждение 429 является следствием утверждений 4.18 в 4.14.
Из определения матрицы сильной связности вмтекает, что справедливо утверждение 4.20. Едшащы ь-й строки ьши ь-го столбца матрица сильной связности орграфа О= (У, Х), где У=(оь . и ), соогеегсгеукгг еершшшм комэоненгм сильной сальности оргрофа О, содержащей еериигку оь Из утверждений 4.18 — 4.20 слелует справедливость алгоритма определения числа компонент сильной связности орграфа В.
в танже матриц смежности этих компонент. Алгоритм 4.1г Шаг 1. Полагаем р=1,Ям=2(О). Шаг 2. Включаем в множество верпшн Уг очередной номпоиепты сильной связности Ор орграфа Р вершины, соответствующие единицам первой строки матрицы бм В качестве А(Рг) берем подматрицу матрицы А(В), иаходяигупюя на пересечении строя и столбцов, соответствующих вершинам нз У. Шаг 3. Вычеркиваем из Юь строки и столбцы, соответствующие вершинам из У„Если в результате такого вычеркиваншь не остается нь одной строки (и соответственно ни одного столбца), то р — количество компонент сильной связности и А (Рь), ...
..., А(Р ) — матрицы смежности компонент сильной свяэпостп О,..., О, орграфа О. В противном случае обозначаем оставшуюся после вычернивания из др соотвшствуюгцих строк и столбцов матрицу через бе+а врисваиваем р; р+! и переходим к шагу 2. Замечание 4.И. После изменений в обозначениях и терминологии алгоритм 4.! можно применять для определения числе компонент связности графа С, а также матриц смежности этих компонент. Для обоснования етого достаточно воспользоватьсЯ утверждениями, аиааогичныии утверждениям 4.18 — 4.20, но сформулированными для неориентированного графа С. Более того, алгоритм 4.! остаегся справедливым и для произвольных пссвдаграфов (ориентированных и неориентированиык). Дока- зательство аналогично.
Задачи и упражнения 1. Показать, по в любом графе количество вершин нечетной степени четые. 2. Понаэать, что из есяного замкнутого маршрута нечетной длины можно выделить простую цепь. 3. Показать, что ребро, входящее в шгкл графа, входит в некоторый ею просюй цикл. . 4. Показатг, чса любая вершина, входящая в цикл. ие является висячей.
б. Доказать по в связяом графе, содержащем, по ирайнсй мере. две вершины, найдется верппша, ие являнхцаися точкой сочленения. б. Доказать, по если в орграфе Р отсутствуют верюниы с нулевой полустепенью исхода (захода), то в О имеется простой контур. 7. Докааать, что удаление нз орграфа вершины о с бг(о) (1 (б-(о) щ)) приводит к орграфу, нонтуры коюрого совпадают с коитураын нсходнопг орграфю 8. Определить, именя лн контуры орграфы с матрацами смежности: 000 0) ОООО ) ОООО . ) 0001 ) 00!1 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
