Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 19
Текст из файла (страница 19)
Следовательно, р(о~) = в, . Элементы же бп матрицы смежности — это коли- Ц. 1=1 честна ребер, инцидентных вершинам ш и ен Отсюда л р(сч) = ~'бсь 1=1 При подсчете степеней вершин по этим формулам каждая петля дает в степень инцидентной ей вершины вклад 1. Однако при изображении петли на рисунке к этой вершине примыкают два конца петли, т. е. петля дает в эту степень вклад 2.
Чтобы таким образом учитывать вклад петель в степень, нужно несколько усложнить формулы для ее вычисления. Через коэффициенты матрицы инцидентности ее можно вычислить, например, о формуле р'(о,) ч)'еы Х с=з и в х (6 — ~~,)Кол О р Лр а --,~~=2 в=1 э=1 ветствующее слагаемое внешней суммы равноеп, т. е, 1для 96 ребер, ннцидентных вершине оь и Одля остальных, Если же оно является петлей, то ~~'е!ь =- 1, а слагаемое внешней сум!!=! мы равно 2еп, т. е. 2 для петель, и!щидентных вершине оь и О для остальных. Это же значение степени выражается через коэффициенты 69 матрицы смежности графа 6 формулой !! л р' (о,) = ~~~ 6;, + бм — — '~' 6зь + 6;;, !=! ь=-! В зависимости от рассматриваемой задачи может потребоваться тот или иной способ определения степени вершины. Поэтому в каждом случае должно быть указано, является ли петля однажды или дважды инцндентной своей вершине.
Так как каждое ребро имеет два конца, в сумме р'(и) ребра учитываются по 2 раза. Таким образом, !! —— э эта сумма равна удвоенному числу ребер графа, т. е. четна. Следовательно, четно и количество нечетных слагаемых этой суммы, т. е. число вершин нечетной степени. Граф называется однородным степени й, если степени всех его вершин равны й и'тем самым равны между собой. Если однородный граф степени й имеет и вершин и т ребер, то т= — ~Р р'(и) = лп(2, п=2т/И, Граф без крат- 2 с!вп ных ребер называется полным, если каждая пара вершин соединена ребром.
Локальные степени ориентированных графов. Для вершин ориентированного графа определяются две локальные степени: р, (о) — число ребер с началом в вершине э, или, иначе, количество выходящих из о ребер, и р,(о) — количество входящих в о ребер, для которых эта вершина является концом.
Петля дает вклад 1 в обе эти степени. Локальные степени вершин ориентированного графа просто выражаются через коэффициенты 6п его матрицы смежно- 1! !! сти; р, (о!) = ~~Р 6!ьь р, (и!) =- ~~~ ~бы. /=! ь=! Выраженяе их через коэффициенты матрицы инцидент- ности значительно сложнее. 96 Так как каждое ребро ориентированного графа б имеет одно начало и один конец, суммы ~~)' р,(о) и ~~)' р,(о) О~в е~вв равны количеству ребер этого графа, а значит, н равны между собой.
Отсюда следует, что в однородном ориенти- рованном графе степени й с и вершинами и пь ребрами гп= ~~~~ р,(в) = ~~)' р,(о) == йп, и = и!й, ч~в ~я в Части, суграфы и подграфы. Граф Н называется частью графа б, Нс:.б, если множество его вершин Г(Н) содер- жится в множестве )'(6), а множество Е(Н) ребер— в Е(6). Если Р(Н) = Р(6), часть графа называется сугра- фом. Например, имеется нулевой суграф, множество ребер которого пусто. Суграф Н покрывает вершины неориенти- рованного графа 6 (или является покрываюи(им), если лю- бая вершина последнего инцидснтпа хотя бы одному ребру из Н. Таким образом, если в графе 6 есть изолированная вершина о, не ннцидентная ни одному ребру, покрыва1ощие суграфы этого графа не существуют. Любое множество В ребер графа 6 можно считать мно- жеством ребер некоторой части Н. Множество вершин этой части состоит из вершин, инцидентных элементам множест- ва В.
Если В является множеством ребер другой части Н', то Нс:Н', причем вершины Н', не принадлежащие Н, в гра- фе Н' изолированы. Подграфом 6(У) графа 6 с множеством вершин У~)т называется часть, которой принадлежат все ребра с обоими концами из К Звездный граф для вершины о~б состоит из всех ребер с началом или концом в вершине в. Множест- во вершин звездного графа состоит из в и других, ивцидент- ных его ребрам вершин. Операции с частями графа.
Дополнение Й части Н оп- ределяется множеством всех ребер графа 6, не принадле- жащих Н. Сумма Н,()Н, и пересечение Н~ПНз частей Н~ и Н, гра- фа 6 определяются естественно: )т(Н,(~Н,) = У (Н,И)т (Н,); Е(Н,Ц)Нз) = Е(Нг)()Е(Н,); )'(НДН,,) =) (Н,) Г) Р(Н,); Е (НЯ Не) = Е (Н,) ( ) Е (Н,). Две части Н1 и Нг не пересекаются по вершинам, если 7 — 750 97 они не имеют общих вершин, а значит, и общих ребер, Сум- ма Н,()Нз не пересекающихся по вершинам частей называ- ется прямой суммой. Аналогично определяется прямая сум- ма любого числа частей.
Части Н, и Н, пе пересекаются по ребрам, если Е(Н,)ПЕ(Н,) =Я. Например, для любой части Н и ее дополнения Й сумма 6=П()Н вЂ” прямая по ребрам, Графы и бинарные отношения. Между ориентированными графами без кратных ребер с множеством вершин У=(оь..,,о ) и бинарными отношениями на множестве У существует взаимно ощзозпачное соот- ветствие: отношению Гт соответствует ориентированный граф 6(й), в котором ребро (о', о") существует, если и только если выполнено о')го". Аналогичное взаимно однозначное соответствие существует меж- ду симметрическими бинарными отношениями и неориентнрованными графами. Рассмотрим теперь соответствие между операциями над отноше- ниями и операциями над графами.
Каждое отношение и имеет отрица- ние ) и, истинное тогда н только тогда, когда Я ложно. Например, для отношения равенства о'=о" отрицанием является отношение нера- вевства о'Фо", для отношения ортогональиости о'.).о", определенного для элементов векторного пространства, отрицанием является отноше- ние отличия скалярного произведения от О: (о', оя)чьо. Граф 6( ~Гг) является дополнением графа 6(Гг) по отношению к полному ориентиро- ванному графу К(У) с множеством вершин У, иа котором задано рас- сматриваемое бинарное отношение Л, и множеством дуг Е(К(У)) = У)сУ, Граф 6(й '), где Л-' — отношение, обратное )г, отличается от графа 6 (Я) тем, что направления всех дуг заменены на обратные.
Отношение Я' содержит отношение Гг, если они определены иа од- ном и том же множестве У и из о'кои следует о'и'о". В этом случае говорят также, что отношение и' следует из отношения Гс, и пишут К'=>Я. Соответствующие графы 6(К) и 6(й') имеют одно и то же мвожество вершин У, а множество Е(й) ребер первого является под. множеством множества ЕЯ) ребер второго. Таким образом, 6()г) яв- ляется суграфом графа 6(К'), т. е.
6()г')=>6(И). Для любых бинарных отношений й, и Яз, заданных на одном н том же множестве У, можно определить сумму (объединение) й~())гт и пе- ресечение КДкз: о' Ж () и,) о" = =о' Л, гу"туо' и, й'; о' (йт()йз) о" = =о' йт о" Ь о' Ггзо", Соответствующие графы также являются суммой и пересечением 6(й,()й,) =6(й,)()6(й,); 6(й,()й,) =6(й,)66(й,). Некоторые типы графов хорошо описываются на языке бинарных отношений. Например, нуль-граф 8(У), не имеющий ребер, соответствует нулевому отношению о'оо", не содержащему ни одной пары (о', о")гиУ)сУ; полному ориентированному графу К(У) соответствует универсальное отношение о'Со", всегда истинное.
Если й рефлексивно, то С(й) имеет петли во всех вершинах; если )г аитнрефлексивно, то С()т) не имеет петель. Если )с траизитивно, то в графе С()т) для каждой пары ребер (о', о") н (о", о"') имеется замыкающее ребро (о', о"'), 4.2. МАРШРУТЫ, ЦЕПИ И ЦИКЛЫ Определения. Пусть 0 — неориентированный граф. Маршрутом в О называется такая конечная или бесконечная последовательность ребер (...ео, еь ..., е„...), что каждые два соседние ребра ег=г и е; имеют общую инцидентную вершину.
Одно и то же ребро может встречаться в маршруте несколько раз. В дальнейшем будут рассматриваться в основном конечные маршруты, т. е. конечные последовательности ребер (е„еш .„, е„), В таких маршрутах имеется первое ребро е, и последнее ребро е„, Вершина оо, инцидентная ребру е, и не инцидентная е„называется началом маршрута.
Если же ребра е, и ех — кратные, необходимо специальное указание, какую из двух инцидентных им вершин считать началом маршрута Аналогично определяется конец маршрута. Вершины, инцидентные ребрам маршрута, кроме начальной и конечной, называются внутренними или промежуточными. Так как различные ребра маршрута могут быть инцидентными одной и той же вершине, начало и конец маршута может одновременно оказаться н внутренней вершиной см. маршрут (еь е„е,, еь ез) на рис. 4,6). Пусть маршрут М (е„ез,, е„) имеет начало оо и конец в,. Тогда его называют соединяющим вершины оо и и„,.
Число ребер маршрута называется его длиной. Если па=о„, маршрут называют циклическим. Отрезок (еь еььг, ..., е)) конечного или бесконечного маршрута М сам является маршрутом. Он называется участком маршрута М, Маршрут М называется цепью, если каждое ребро встречается в нем не более одного раза, и простой цепью, если любая вершина графа 6 инцидентна не более чем двум его ребрам. Циклический маршрут называют циклом, если он является цепью, и простым циклом, когда это простая цепь'. Однако фактическим циклом (соответственно простым цик- лом) считают циклически упорядоченное множество ребер, в котором два соседних ребра имеют общую инцидентную вершину.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
