В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 36
Текст из файла (страница 36)
(4.7) г г Заметим, что по правилу произведения (П(О. оь иг, иь А+1)(=)П(О, оь оь А))(П(О, ог. оь!)('а =)П(О, о;, иь А)(ан, 1=1, 2, ..., л (аб) 1тб Из (4.7), (4.8), исоользуя то, что в силу индуктивного предиоложения выполняется равенство (П (О, оь ш, й) ( =а)» !. (=1, 2, ... и, ' »отучаем (Н(О, ь„сг, Ь + !)] = Х а( ) оц а( + ] . 3 Утзсрждчи»е Яб и»сст»»ага»»слшш»е следсть»» Пр»асье, на»рикер, утэерждс»ш, юж»»юшсе ьа з !»»ьтр»шг»» юю апреле» пь нада»»с ка»тура» а арграфс Р.
Утверждение 4.0. Для того чтобы л.аергишгный оргреф Ю с лагрицей смежности Л=Л(Р) имел хоти бш один контур, необходимо и достаточно, чтобы »шурина К=Аз+А»+...+А имела ненулееые диагональные элементы. Достаточность. Пусть К= (йц) и для неноторого камера ! выаолняется Ягг>0. В этом случае для некоторого гчд(2, ..., л) сараведливо аагц)0, а слеаовательно.
в силу утверждения Я.б найдется путь в О из о. в оь Но тогда в силу утверждения 4.3 в орграфе Р найдется простой контур. Необходимость. Пусть в орграфс О имеется некоторый но»- тур. В утверждении 4,3 было доказано, что из всякого контура можно выделить врастай контур. Нетрудно видеть, что длина простого контура не ирсаышает числа вершин л. Но тогда н силу утверждения 4.3 для любой вершины оь ирииьдлежащей некоторому простому контуру длины (, где 2»Б!<л, элемент а<ел матрица А' отличен от нуля, а слеловательно, в элемент Ьг матрицы К отличен от нуля.
Замечание 4.Р. В случае ориентированного л-вершинного исевдографа О лля существования в Р контура необходимо и достазочно, чтобы матрица К=А+Аз+...+А" имела ненулевые да»тональные элементы. Доказательство аналогично. 4АА. Буаевы матрицы. Операции вчд булевыми матрнцамм ВУлем (шХл)-матР»цУ С=(сг!), У котоРой с!гид(0, 1), ! 1, 2, ...
..., ги, ! 1, 2, ..., и, иааывать булевой матрицей. Заметим, что в случае, когда 6 — лсевдограф без кратных ребер, матрица смежности А(6) состоит из нулей н ел»ниц, т. е. пал»ется булевой (то же имеет место и для ориентированного нсеадографа О без кратных дуг). У исевдографа 6, кроме того, булевой является и матрица д (6). ньд булсьм»» иатр»аа»и од»»зксзсз раь»се»асти буде» »р »»год»п »был»ив лаг»час»»с ааьрац»а.
Нь»э»»ср, сел» С ]г д. О ]Лц) — булс»и (чх»)-»ьчу»аи, та у (]й=суО сеь булсаа (мха).»»гриса. у»а- ЧЧЮВ Ра гцт(Л» ! 1, 2,..., щ ( (, 2,, л. Крь»с тспь »геле» П»эаю~ю гр лашчсшош уиаьжч»»» буьсаих»атр»» Пуп» С-]сц] булеза (» х з)-»»три»з и О (шй — буза»а ш х»)-»а р»ш. таглч (!" (71 и Уч! с ей Π— бУееее (ьн х в)-негРнээ. У мнепеа (еь Ч (ее,йка) е г-ЦЦ .,Г-Г.К..., .Ц О-сгйсфлфсенс,=се- -С,-С, гн. С вЂ” ееенрепмн буееее метрике, ее буден енееть О=С" Введем теперь операцию шйп перехода от пронэнольной (шХл)-натРицы 0 ]йи] с неотРицательными энементами к булевой (ш)(п)-матрице С=(си]=з!йпО, у нагорай си= =э(йпйеь е 1, 2, ..., гл, 1=1, 2, ..., л.
где для любого числа уний э!йпу ] 1. н (~О( (О, если (=б, Нетрудно поназать, что для любых матриц Рь О, (подходя- Ших размерностей) с неотрицательными элементами выполня. ются равенства нейп (Р,-!0) =э(бп О ~/а!йп Оь э16п (Рыбе) =зыби Реь(с ейз( йп Ое. (4.9) Отметпм. что булевы матрицы более экономичны в вычисли- тельном отношении, чем целочисленные.
Действительно, вано. минанне булевой матрицы требует меньшего объема оператнв. иой памяти ЗВМ, чем целочисленной матрицы той же размер- ности. Кроме того, выполнение на ЭВМ логических операций над булевыми матрицами требует меньшего объема вычислений, чен над целочисленными матрицами тех же размерностей. В свана с этны представляют интерес методы решения задач теории гра- фов, основанные на веыполнении логических операций над матрнцей смежности как над булевой матрицей. Вернемся к рассмотренной ранее задаче о выяснении наличия коптуроа в орграфе.
Иэ утверждеешя 4.6, используя (4.9), получаем, что справедливо Утверждение 4.7. Дгя гого чтобы и-вершинный орграф О г геатрицгй смежности А=А (О) имен хотя бы один контур, неабходило и достаточно, чтобы латрица Ае,т(де,(!.,ЧА" илаха генуггвые диаганаленме элемеигьь 4.1.6. Объединение, пересечение графов. Подграфы Объединением графов 6, (Уь Хе). Се (Уь Не) наэынаетсн граф 6,()Се=(У ()Уь Хе1)Хе). Пересечением графов Се (Уь Хе), Се=(уе, Хе), где Уе() ПУеФИ.
называется граф Се()бе= (Уе()У», Хе()Хе). Оодграфом графа 6 называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа с. подграф нааыааагсн собственным, если он отличен от самого графа. Пад. графом графа 6= (У, Х), порожденным подмножеством УеецУ, где УеФИ, называется граф Се=(рь Хе), множество Х, ребеР 1тя которого состоит нз тех и только тех ребер графа б, оба конца которых лежат в Уз. Все приведенные определении распространяются на орграфы. Для дальнейших рассуждений понадобится следующее простое утверждение. Утнеригдеиие 4.8. Пусть б= (У, Х) — игкогорый граф, Уиш зЫУ. Узчьмь Ог — подграф графа О, лораясдеяиый мяожесгеом Уь Тогда А(бз) является яодмагрш~ей матрицы А(б), иаходящгйся яа пересечении строк и столбцов, ссюгвегсгаующих еер. шилам иэ Уь Замечаиие 4.10. Аналогичное утверждение справедливо и для орграфов.
Более того, оно остштся справедливым и для произвольных псевдографов (ориентированных и неорпевтированных). 4,1.7. Связность. Компоненты сввэнастм Говорят, что верпшиа ю орграфа Р (графа б) досгажима из вершины о, если либо ю=о, либо существует путь нэ о е ю (маршрут, ыюдквяющий а, ю). Граф (орграф) называется сэитиым (силька связным), если для любых двух его вершин о, ю существует маршрут (путь), соедннчюший о, ю (иэ о в ю). Орграф называется односторонне связным, если для любых двух его вершин по крг(нюй мере одна достижима нз другой.
Псевдографом, ассоциированным с ориентированным псевдо~рафом Р= (У, Х), называется псевдограф б= (1. Хг), в котором Х, получается из Х заменой всех упорядоченных пар (о, ю) на неупорядоченные (а, ю) (см. рис. 4.9, где а — ориентированный псевдограф, б — ассоциированный с ннм псевдограф). Орграф называется слабо сеязиаж есхи связным является ассоциированный с пвм псевдограф. Если граф (орграф) не является связным (слабо свэзиыы), то ои на- ~Я~~~~ аываегся игсахэимлс Коэюоигигой саяэиости (сигьиой ггзэиосги) графа б (орграфа Р) называется его связный (сильно связкыг) подграф, ве являющийся собр~и. 4В сгвсивыи подграфо» никакого друюго связного (сильно связного) волграфа графа б (орграфа Р).
Пример 4.!4. У графа, изображенного и* рис. 4.10, тря коикоиенты связности. Пример 4.1К У орграфа, изображенного на рис. 4.11, три компоненты сильной связности, показанные ва риа 4.!2,а — а Из определения компоненты связности (сильной связности) заключаем, что справедливо 173 Ужтржденне 4.9. 1. ПУсть бл=(Уь К,) — кошюнента свЯзносп гРафа б.
Тогда б,— подгроф грофа б, «орткденнмй множеством 1рь 2. Пусть Ол=(1гл, Х,) — компонента сильной связности орграфи О. Тогда Ол — подграф орграфа О, яорожденньи! мнсжествол! Ул. о ь Р П л' Рве 4.Ю Рг . 4.лт Рви 4.л! Замечание 4Л!. Утверждение 4.9 остается в силе и для произвольных псевдотрефов [орвентнрованных н неорнентированных).
Нетрудно показать. что справедливы следующие утмрждьння. Утверждение 4ЛО, Пусть 6=(У, Х) — нсевдогроф с р «омпонентама селзностн: 6~=(уь Х~), ..., Рр (У Нр). Тогда 1) 1л Ул().ббур, Х=Хл(). ПХр, т е. Р=бл0...06р; 2) У!бр! И, Хй)»л=И при !чь)! 3) п(б )+...+п(бр) =п(6), т(бл)+...+т(бр) =ш(б). Упшрждепяе 4.11, Пусть Р=(У, Х) — ориентированный псевдограф с р «омпонентоми сшюной связности: О, = (Ул, Х,), ... ..., О,=(У„Х,). Тогда 1) У=ул()мбрр, Хю»й)..Р»р! 2) У Ну!=И, «й(» =И ри 3) п(Оь)+...+п(бр]=п(Р), пл(Р,)+ +т(Рр)~т(О), Утвержденна 4.12.
Пусть р — отношение достижнмости «а множестве 1Л вершин псевдогрофа б, т. е. орта тогда и только тогда, когда либо о=ю, либо сук(есрвувт маршрут, соедипяюи(ий», .Т Уа! 1! !э — зкеиеалентность на 1; 2) орт тогда и только тогда, когда вершины о, ш принадлежат одной «омпоненте связности псеедогрофа б; 3) для любого класса зквивалентногти У,т))р лсевдограф бь коровгденнмй множеством Уь является компонентой свяькости псездограба б! 4) длл любой компоненты свЯзности бл=(Ул. Хл) псевдпгРафа 6 вьзюлкяется У ее У!р. УтвеРжденне 4.13, ПУсть Рл — отношение достшкиности на множестве У вершин ориентированного нсевдографа О, т.
Е. ор,ш тогда и толысо тогда, шида вершина ю достижима из о. !74 Пусть также р,— отношение двусторонней достижимости ил 1', ю е. пс=рсйр с. Тогдас 1) р, рефлююиено, граизитивно; 2) рс — зквивалентяост ла Ус 3) ирсю тогда и только тогда, ковда еерсиины о, ы лрииадлеясаг одной комиоиенге сильной связности ориентированного исевдографа Ос 4) для любого класса гкеилалентиости Усев)7рз ориентированный псеедограф Оь лорсскдгииый миазсесгеом Уь является комжыснтой сильной связности ориентированного псеедографа Рт .3) дгл любой компоненты сильной связности Ос=(Ус, ХД ориентированного лсевдогрифа О выполняется Усшу/рь В дальнейшем количество компонент связности графа О будем обозначать через р(0). Аналогично через р(О) будем обо.
зпачать количество компонент сильной свюности орграфа О, Под операцией удаления вершины из графа (оргрефа) будем понимать операцию, заключающуюся в удаления иеиоторой гс вершины вместе спацилеитны- с) иг ми ей ребрами (цугами). Вершина графа, удаление и „ % шторой увеличивает число с) и компонент снязностн, иазываетса раздглюощей (нли то г «ой соелгиснил). Пример 4.18. Точками сочленения графа, изображешсого на рпс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
