Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 33
Текст из файла (страница 33)
На рис. 8.4, а ебро х„хз расположено на внешней области, а цикл указан стрелками. Связный граф, не имеющий циклов, называется деревом. Начальная вершина дерева называется корнем, выходящие из него цепи— ветвями. Дерево, имеющее и вершин, содержит т = и — 1 ребер. На одних и тех же вершинах можно построить различные деревья. Пример таких деревьев для пяти вершин дан на рис. 8.5, а — д. Число различных деревьев, которые можно построить на и вершинах (см. (15)): Г„=- пл-з, (8.6) С реди различных деревьев отметим звездное (корень смежен со всеми остальными вершинами) и последовательное (корнем является один нз концов), показанные на рис. 8.5, в, г.
Дерево называется покрывающим граф, если оно содержит все его вершины. Для графа, изображенного на рис. 8.4, в, покрывающим будет, например, звездное дерево ) Ж „, в) г) с коРнем в веРшине х4. 4, «4 У1) называется частью графа 6 =- = (Х, У) (рис. 8.6, а), если он Ъ~ «1 находится в отношении включения рис. Эд. Граф н его часта к немУ 61 4: — 6, т. е. Х14: — Х и У1: — У. Если 1 Е 1 = (1, 2, ..., 1), то граф можно определить как объединение 61, т. е.
6== () 6ь если Х =- () Х1, У = () У1. 1Е1 1Е1 1Е1 Часть графа 61 -= (Хь У1) называется куском (рис. 8.6, б), если Х, с: Х, У1 с= У, причем в У1 входят все ребра, инцидентные Х1. Множество ребер куска таково, что 01= У1 1 () 61п где У1,1— 1Е1 множество ребер, оба конца которых инцидентны Х1, а () У1 э — мноЬЕ1 жество ребер, один конец которых инцндентен Х1, а второй — Х Х1 (напомним, что Х Х14-4 х Ь Х Э х 6$ Х1). Часть графа 61 = (Хь У1) называется псдграфом (рис.
8.6, в), если Х1 ~ Х, У1 с: — У, т. е. подграф образуется удалением из графа части вершин и инцидентных им ребер. Часть графа 61 = (Хь 61) называется суграфом (рис. 8.6, г), если Х1 = Х„а У1 с: У, т. е. суграф получается удалением из графа части ребер. Матричный способ задания графов. Графы могут быть заданы матрицами инциденций и смежности. Матрица инциденций задает связь между вершинами х1 ~ Х и ребрами и~ Е У. Таким образом, матрица инциденций — это прямоугольная матрица.
Я=)!д1,1~~„„; (Х(=п; (У~=т, строки которой соответствуют вершинам, а столбцы — ребрам. Элементы матрицы инциденций для смешанного графа могут получать одно из пяти различных значений, например: а, если вершина х1 является началом дуги и;; Ь, если вершина х; является концом дуги и,:, с, если и1 — звено, инцндентное вершине х;; й, если и1 — петля при вершине х,.; О, если вершина х; и ребро и4 не инцидентны. 4ЗЗ Матрица инциденций графа (см. рис. 8.3) будет иметь вид с с с 0 0 0 0 О Ь а с с с д-а ас 0 0 О о о о о ь ь о ь о о 0 О 0 0 0 0 с а а Ь Матрица смежности задает связь между вершинами х1, хэ Е Х. Таким образом, матрица смежности смешанного графа — это квадратная матрица размером и Х п„элементы которой определяются по правилу: о и (х1) с(, если 1 = 1; '1, 1= и (х1, хв) а+ п((х1, х,) ь+ и (х„х1) с, если 4 ~ 1, где й(«1) — число петель при вершине «1, и (хь хг) — число дуг, идущих из х1 в «1, .и (х1, х;) — число дуг, идущих из х~ в х1', и (хь Х1) — ЧИСЛО ЗВЕНЬЕВ, СОЕДИНЯЮЩИХ ВЕРШИНЫ Х1 И Х1.
Матрица смежности графа (см. рнс. 8.3) будет 0 Зс 0 а+Ь Зс Й 2а с 0 2Ь 0 Ь а+Ь с а 0 Элементы матрицы смежности ориентированного и неориентированного графов без петель могут соответственно определяться по правилам: п (х„х;), если существуют дуги, идущие из х1 в х1; 0 — в противном случае; и (х,, х1) если существуют звенья, соединяющие х- и х; Г1, 1= 1 0 — в противном случае. Матрица смежности неориентированного графа без кратных ребер совпадает с матрицей двуместного предиката связности, определенного на множестве Х.
Аналитический способ задания графов. Этот способ основан иа использовании понятия отображения. В соответствии с определением граф будет задан, если задано множество Х и его в общем случае многоэначное отображение в себя. Для смешанных графов образ каждой вершины х1 разобьем на два непересекающихся подмножества: Р+'«1 ы Х вЂ” подмножество тех вершин х1 Е Х, в которые заходят дуги из вершийы х1 — прямое отображение; Гх ~ Х вЂ” подмножество тех вершин хв Е Х, с которыми вершину х1 связывают звенья или петли. При таком задании граф обозначается 6 = (Х, Р), Например, граф, показанный на рис. 8.6, а, этим способом будет задан множествами: Х = (х„х„х„х«, х,); Р+ хз — (хз1 хз)1 1 хз — (хз~ хз) Р ха= (хз) 1 хз — (хз хз) Р хз (ха)1 Гхз Я1 Р хв (хм хв) Гх4 Я1 Р+'х,=- (х,), Гх, =- (х,). Прн аналитическом задании н) х, х л) х, х, х, х, х, х, х, МуЛЬтИГрафОВ НЕОбХОдИМО уЧнтЫ- о н ' вать кратность ребер. Мульвнграф "з будет задаваться множеством Х и его отображением в множество коре " и, и, н, и, тежей над Х.
Тогда для смешанно- хв го мультиграфа: Р+зх; — кортеж„ рве 8.7. гннерграф (а) н его иеннго- состоащий из тех веРшин хт с Х, во представлевне (о) . в которые заходят дуги из верши- ны х; (х, могут повторяться в соответствии с кратностью дуг); Гх« — кортеж, состоящий из тех х, Е Х, с которыми вершину х, связывают звенья (х; в кортеже повторяются в соответствии с кратностью звеньев).
Мультиграф (см. рис. 8.3) этим способом будет задан множествами: Х =- (х» х.„хз, хз); Р+ хз = (х«); Гхь= (хз, хз, хз); Р+ хз — (ха~ хз)' Гхз — (хз хз хо хз~ х4) Р+'х,= Я; Гх,=- Я; Р+ хе = (хд, хз); Гха = (хз). Используется также понятие обратного отображения Р-'х, — это подмножество тех вершин х, Е Х, из которых исходят дуги, заходящие в х;. Например, множество вершин, смежных вершине хо определяется как Х' = Р+'х, 1) Р-'х; 1) Гхо Гнперграфы и ультраграфы.' Гиперграф можно определить как множество Х, на элементах которого определен некоторый набор п-местных отношений.
Тогда каждое ребро и; Е У гиперграфа — это некоторое подмножество Х; Е Х, на котором соответствующий,предикат набора имеет значение «истинам Гиперграф Н = (Х, У) будет задан, если задано множество вершин Х и определено множество его ребер У. При геометрическом представлении гиперграфа вершины изображаются кружками (точками), а ребра — в виде контуров, охватывающих входящие в них вершины. На рис.
8.7, а показан гиперграф, множество вершин которого Х =- (х„х„х„х„хз, х„х,), множество ребер У = (и„из, и„иа), причем каждое ребро представляет собой следующее подмножество: и = (х, х, хн); из = (хь, хз), из = (хз хе)' и« = (хз х« хз). 460 Гиперграф может быть представлен в виде двудольного графа (графа Коняга) 6„= (1', У), где г" = Уз И )х„'г', = Х, )лз = У, Уз Д У з = Я; )х — отношение инцидентности (обладающее свойством симметричности) между множествами Х и У. Для гиперграфа (рис. 8.7, а) кенигово представление дано на рис. 8.7, б, Гиперграф в форме Он = (1', 1Х) будет задан, если заданы множест- ва Х, У и многозначное отображение множества Х в У или У в Х. Ана- литическое задание гиперграфа (рис. 8.7, а, б) будет представлено множествами: Х = (х,, хз х„ха, х, х, х,), У = (и„и„и„и ) и одним из отображений: — Х в У; Г х,=(и„из); Гх, = (из); Гх,=(и„ив); Гха=-(и«); Г х,= (и,); Г хе = (и„и,); Г х, =- (и,) или — Ув Х: Г и, = (х„ х„ х,); Г и,= (х„ х,); Г' и,= (х„ х,); Г ив= (х„ х«, хз).
Матрица инциденций гиперграфа А„= ~!а, ~~|„н (~Х~ = и, ~У| = л«) задает инцидентность каждого элемента хз Е Х (1 = 1, и) соответствующему элементу из Е У (1 = 1, л«). Элементы этой матри- цы определяются по правилу: 1, если х,~==Г и,.; а; ~= О, если х;б~( и, Матрица инциденций гиперграфа (рис. 8.7) будет иметь вид 1 1 О О О 1 О О О О 1 1 О О О 1 О О О 1 1 О 1 О 1 О О О нредставленве уль- траграфа Если между элементами х; Р Х и и; Р У задать бинарные отношения инцидентности, придем к понятию ультраграфа. Пример кенигова представления ультраграфа дан на рис.
8.8. Аналитическое задание ультраграфа представляет собой множества Х, У и многозначные (прямые) отображения Х в У и У в Х (образы вершин и ребер по бинарному отношению инцидентности). Ультраграф (рис. 8.8) этим способом будет описан следующими массивами: Х = (х„х„х„х,); У = (ио и„из); Р+'х, = (и,); Р+'х, = Я; Р+'х, = (и,); Р+'х, = (из, из); Р+'и, = (хз, хз); Р+'из = (хз); Р+'и, = Я.
Ультраграф можно задать также в виде множеств Х, У и прямого и обратного отображения множества Х в У или У в Х. Обратным А. и, Савельев, В. А. Овевнннвев «64 отображением вершины Р 1 х» будем называть множество ребер с»': — (», для которых в кениговом представлении ультраграфа справедливо (и;, х;) Е Я, » =- 1, т, где К вЂ” бинарное отношение инцндентиости. Под обратным отображением ребра Р-зи» будем понимать множество вершин Х' с= Х, для которых справедливо (хьи»)ЕЯ,( 1,п, где К вЂ” то же, что и выше. Ультраграф (рис. 8.8) этими двумя способами будет задан через отображения Х в (»: Р+'х, =- (и,); Р+ х, = Я; Р+ х, = (и,); Р+зхз = (им из); Р-зх, = Я . Р-зхз = (и„ из); Р-'х, = (из); Р-'х, = Я или через отображения (» в Х: Р+'и, =- (х„хз); Р+'из = (хз); Р+'из = З' Р-'и, =- (х»); Р-'из — — (хз); Р-' из = (хз хз).
Матричным способом ультраграф задается двумя матрицами: А; = = ]]а],»]]„х, — матрица инциденции вершины — ребра и А„" = = ]]а»»]]„„, — матрица инциденции ребра — вершины, элементы которых определяются по правилам: ( 1, если и» ~= Р+' хб ., ) 1, если х»1== Р+ ' иб а,' = » 1 О, если и» ~ Р+' х», '» ( О, если х» ф Р+' иь Для ультраграфа (рис.
8.8) матрицы будут иметь вид 0 1 1 0 0 1 0 0 0 0 0 0 ; А„"= Ультраграф может быть задан одной матрицей А„= ]]а,,»]]„„,, если ее элементы определить по правилу »» ь 1, если и» е= Р+' х,; а», »= — 1, если и» ~ Р-' х», О, если и» ф Р+' х, А и»ЯР-' хь Для ультраграфа (рис. 8.8) матрица 162 1 0 0 о о о ]]О 1 1 0 0 — 1 — 1 0 — 1 0 1 0 1 1 В прикладных задачах широко используется понятие взвешенного графа. Множеству вершин и ребер графа или одному из них ставятся во взаимно однозначное соответствие некоторые множества, элементы которых содержательно являются какими-либо характеристиками соответственно вершин и ребер н называются весами. й В.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
