Новиков Ф.А. Дискретная математика для программистов (860615), страница 46
Текст из файла (страница 46)
Поэтому можно считать,чтоЕ С V х V, Е = Е~хи трактовать ребро не только как множество {vi,v2}, но и как пару (ui, иг).Число вершин графа G обозначим р, а число рёбер — q\Если хотят явно упомянуть числовые характеристики графа, то говорят, (р, q)граф.2437.1.
Определения графов7.1.3. СмежностьПусть V\,V2 — вершины, е = (v\,v2) — соединяющее их ребро. Тогда вершина viи ребро е инцидентны, ребро е и вершинатакже инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентныеодному ребру, также называются смежными. Множество вершин, смежных с вершиной v, называется множеством смежности (или окрестностью) вершины v иобозначается Г+(г>):Г + (v) = f {и е V I (и, v) е Е] ,Г* {у) = f Г+ {v) + v.ЗАМЕЧАНИЕЕсли не оговорено противное, то символ Г без индекса подразумевает Г + , то есть самувершину в окрестность не включают.Очевидно, что и е T(v)v е Т(и).
Если А с V — множество вершин, тоГ(Л) — множество всех вершин, смежных с вершинами из А:г {A) D={ueV\3veA{ueT(v))}=| J r{v).v(EA7.1.4. ДиаграммыОбычно граф изображают диаграммой: вершины — точками (или кружками),рёбра — линиями.Пример На рис. 7.4 приведен пример диаграммы графа, имеющего четыре вершины и пять рёбер. В этом графе вершины v\ и v2, v2 и V3, и v^, v^ и v\, v2 иV4 смежны, а вершиныи v3 не смежны. Смежные рёбра: е\ и е2, е2 н ез, ез ие4, в4 и ei, е\ и ее, е2 и б5, ез ие4 и е5.
Несмежные рёбра: е\ и ез, е2 и в4.Рис. 7.4. Диаграмма графа244Глава 7. Графы7.1.5. Орграфы, псевдографы, мультиграфыи гиперграфыЧасто рассматриваются следующие родственные графам объекты:1. Если элементами множества Е являются упорядоченные пары (т. е. Е с Vx V),то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.2.
Если элементом множества Е может быть пара одинаковых (не различных)элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).3. Если Е является не множеством, а мультимножеством, содержащим некоторые элементы по несколько раз, то эти элементы называются кратнымирёбрами, а граф называется мультиграфом.4. Если элементами множества Е являются не обязательно двухэлементные, а любые (непустые) подмножества множества V, то такие элементы множества Еназываются гипердугами, а граф называется гиперграфом.5.
Если задана функция F : V —» М и/или F : Е —> М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным).В качестве множества пометок обычно используются буквы или целые числа.Если функция F инъективна, то есть разные вершины (рёбра) имеют разныепометки, то граф называют нумерованным.ЗАМЕЧАНИЕОтношение смежности является в некотором смысле определяющим для графов и подобных им объектов (см. разделы 7.4 и 7.5).
При этом следует учитывать особенностикаждого типа объектов. В орграфе вершина v смежна с вершиной и, если существует дуга(и, v). При этом вершина и может быть несмежна с вершиной v. Отношение смежности вграфе симметрично, а в орграфе оно вовсе не обязано быть симметричным. В графе обычно считают отношение смежности рефлексивным, то есть полагают, что вершина смежнасама с собой. В псевдографе, напротив, вершину пе считают смежной с собой, если унеё нет петли.
В гиперграфе две вершины считаются смежными, если они принадлежатодному гиперребру. В гиперорграфе гипердуга обычно проводится из одного узла в множество узлов (возможно, пустое). В таком случае отношение смежности оказывается ужене бинарным отношением на V, а отношением из У в 2 V . Эти и подобные естественныевариации определений обычно считают ясными из контекста.Далее выражение «граф G(V, Е)» означает неориентированный непомеченныйграф без петель и кратных рёбер с множеством вершин V и множеством рёбер Е.7.1.6.
Изоморфизм графовГоворят, что два графа, Gi(Vi,Ei) и G2{V2,E2), изоморфны (обозначается Gi ~~ G2, ИЛИ G\ = G2), если существует биекция h: V\ —• V2, сохраняющая смежность (см. 2.1.6):ei = (u,v) е Eiе2 = (h(u),h(v))G E2.2457.1. Определения графовТЕОРЕМАИзоморфизм графов есть отношение эквивалентности.ДОКАЗАТЕЛЬСТВОДействительно, изоморфизм обладает всеми необходимыми свой-ствами:[Рефлексивность] G ~ G, где требуемая биекция есть тождественная функция.[Симметричность] если G\ ~ G2 с биекцией h, то G2 ~ G\ с биекцией /г - 1 .[Транзитивность] если G\ ~ G2 с биекцией h и G2 ~ G3 с биекциейс биекцией <7 о h.то Gi ~ G3•Графы рассматриваются с точностью до изоморфизма, то есть рассматриваютсяклассы эквивалентности по отношению изоморфизма (см.
2.1.5).Пример Три внешне различные диаграммы, приведённые па рис. 7.5, являютсядиаграммами одного и того же графа Кз,з-Рис. 7.5. Диаграммы изоморфных графовЧисловая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, p(G) и q(G) — инварианты графа G. Неизвестно никакого простого набора инвариантов, определяющих граф с точностью доизоморфизма.Пример Количество вершин, рёбер и количество смежных вершин для каждойвершины не определяют граф даже в простейших случаях! На рис. 7.6 представлены диаграммы графов, у которых указанные инварианты совпадают, по графыпри этом не изоморфны.246Глава 7. Графы7.2.
Элементы графовПосле рассмотрения определений, относящихся к графам как к цельным объектам, естественно дать определения различным элементам графов.7.2.1. ПодграфыГраф G'(V',E') называется подграфом (или частью) графа G(V,E) (обозначается G' с G), если V' с V к Е' с Е. Если V' = V, то G' называется остовнымподграфом G. Если V' С V к Е' С Е & (V' ф V V Е' ф Е), то граф G' называется собственным подграфом графа G. Подграф G'(V',Ef) называется правильнымподграфом графа G(V, Е), если G' содержит все возможные рёбра G:\/u,veV'((u,v) е Е(u,v) е Е').Правильный подграф G'(V', Е') графа G(V, Е) определяется подмножеством вершин V .ЗАМЕЧАНИЕИногда подграфами называют только правильные подграфы, а неправильные подграфыназывают изграфами.7.2.2. ВалентностьКоличество рёбер, инцидентных вершине v, называется степенью (или валентностью) вершины v и обозначается d(v):Vv е V (0 ^ d{v) ^ р - 1),d(v) = |Г + (и)|.Таким образом, степень d{v) вершины v совпадает с количеством смежных с нейвершин.
Количество вершин, не смежных с v, обозначают d(v). Ясно, чтоVueV(d{v)+ d{v) = р - 1).Обозначим минимальную степень вершины графа G через 8(G), а максимальную — через A(G):8(G(V,E)) = f min d(v),v£VA(G(V,E)) = ma xd(v).vEVЯсно, чтои Д(G) являются инвариантами. Если степени всех вершин равнык, то граф называется регулярным степени к:8(G) =Д(<7) = к, Vu е V (d(v) = к).Степень регулярности обозначается r(G). Для нерегулярных графов r(G) не определено.ПримерыНа рис.
7.7 приведена диаграмма регулярного графа степени 3. На рис. 7.6 приведены диаграммы двух регулярных, но неизоморфных графов степени 3.2477.2. Элементы графовЕсли степень вершины равна нулю (то есть d(v) = 0), то вершина называется изолированной. Если степень вершины равна единице (то есть d(v) = 1), товершина называется концевой, или висячей.
Для орграфа число дуг, исходящихиз узла v, называется полустепенью исхода, а число входящих — полустепеньюзахода. Обозначаются эти числа, соответственно, d~(v) и d+(v).ТЕОРЕМА(Лемма о рукопожатиях)Сумма степеней вершин графа (мультиграфа)равна удвоенному количеству рёбер:£vev=При подсчёте суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого.•ДОКАЗАТЕЛЬСТВОСЛЕДСТВИЕ 1Число вершин нечётной степени чётно.П О теореме сумма степеней всех вершин — чётное число.
Суммастепеней вершин чётной степени чётна, значит, сумма степеней вершин нечётнойстепени также чётна, следовательно, их чётное число.•ДОКАЗАТЕЛЬСТВОСЛЕДСТВИЕ 2Сумма полустепеней узлов орграфа равна удвоенному количествудуг:Yd~(v)vev+ Y,d+(v)vev= 2q.Сумма полустепеней узлов орграфа равна сумме степеней вершин графа (мультиграфа), полученного из орграфа забыванием ориентацииДОКАЗАТЕЛЬСТВОДУГ.•7.2.3. Маршруты, цепи, циклыМаршрутом в графе называется чередующаяся последовательность вершин ирёбер, начинающаяся и кончающаяся вершиной, vo,e\,v\, е2, v2,..., ejt, Vk, в которой любые два соседних элемента инцидентны, причём однородные элементы(вершины, рёбра) через один смежны или совпадают.248Глава 7.
ГрафыЗАМЕЧАНИЕЭто определение подходит также для псевдо-, мульти- и орграфов. При этом в графе(орграфе) достаточно указать только последовательность вершин (узлов) или только последовательность рёбер (дуг).Если vq — Vk, то маршрут замкнут, иначе — открыт. Если все рёбра различны,то маршрут называется цепью. Если все вершины (а значит, и рёбра) различны,то маршрут называется простой цепыо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
