Лекции Просолупов

Определение 66.4 . Вершина и ребро называются инцидентными, если является одной из концевых вершин : ( = ( , )).

Определение 66.5 . Два ребра 1 и 2 называются смежными, если у них есть общая концевая вершина: 1 = ( , ), 2 = ( , ).

Определение 66.6 . Степенью вершины в графе назовем число deg инцидентных ей ребер.

Вершина со степенью 0 называется изолированной. Вершина со степенью 1 называется висячей.

Определение 66.7 . Степенью графа ( ) называют максимальную из степеней вершин графа. Минимальную из степеней графа обозначают ( ).

Определение 66.8 . Регулярным графом называется граф, у которого все вершины имеют одинаковую степень.

Теорема 66.9 . В обыкновенном графе число вершин нечетной степени четно.

Доказательство. Для графа с вершинами и ребрами имеет место равенство

∑ =1 deg = 2 , где deg — степень -той вершины. Поскольку нечетное число нечетных слагаемых не может давать четную сумму, число нечетных слагаемых в

∑

сумме =1 deg должно быть четно.

§67. Графы Бержа

Самым распространенным видом ориентированных графов являются графы Бержа.

161

Определение 67.1 . Граф Бержа может быть определен, как пара = ( , ), где — конечное множество элементов произвольной природы, а × — множество упорядоченных пар элементов из .

То есть граф Бержа по сути задается бинарным отношением на множестве .

Таким образом, граф Бержа — это ориентированный граф, который имеет не более одной дуги между любыми двумя вершинами в одном направлении и не более одной петли при каждой вершине. Примеры графов Бержа приведены на рисунке 34.

Не трудно видеть, что для задания графа Бержа достаточно указать отображение: → 2 , ставящее в соответствие каждой вершине графа некоторое

подмножество множества его вершин — вершины, в которые из идут дуги. То есть, определение может выглядеть и так:

Определение 67.2 . Графом Бержа будем называть пару ( , ), где — множество элементов произвольной природы, называемых вершинами, и : →

2 .

Определение 67.3 . Полустепенью исхода вершины ориентированного графа называют число odeg выходящих из ребер (включая петли), то есть

odeg = |{ | , ( , ) }|.

Полустепенью захода вершины ориентированного графа называют число ideg входящих в ребер (включая петли), то есть

ideg = |{ | , ( , ) }|.

Очевидно следующее свойство степеней в ориентированном графе: для любого орграфа с множеством вершин { 1, ..., } и дугами верно, что

Свойства смежности и инцидентности для ориентированных графов определены точно так же, как для неориентированных.

§68. Виды графов

Рассмотрим несколько примеров классов графов.

Полный граф (рис. 35 b)). Обыкновенный граф называется полным, если =(2). Другими словами, каждая вершина графа смежна с каждой другой. Такие графы обычно обозначают или . На рисунке 36 пункты a) и b) изображены полные графы 2 и 5 соответственно.

Граф Бержа называется полным, если для него ( ) = ( ) × ( ).

162

Пустой граф (рис. 35 a)). Граф называется пустым, если у него нет ни одного ребра: = ?. Пустые графы обозначают . Пример пустого графа 3 изображен на рисунке 36 c).

Двудольный граф (рис. 35 e)). Граф называется двудольным, если его

множество вершин можно разбить на два подмножества таким образом, чтобы все ребра графа начинались в одном из подмножеств и заканчиваются в другом. То есть

Граф называется полным двудольным графом, если дополнительно 1, 2( , ) ( ). Полный двудольный граф обозначают 1, 2 .

На рисунке 36 d) слева приведено изображение полного двудольного графа 3,3. На рисунке 36 d) справа этот же граф изображен так, чтобы было лучше видно множества 1 и 2.

Цикл (рис. 35 c)). Циклом называется граф, состоящий из вершин

последовательно соединены ребрами в кольцо.

Цикл из вершин обозначают . Примеры циклов изображены на рисунке 37: цикл 6 слева и 5 справа.

Колесо (рис. 35 d)) — цикл −1, к которому добавлена еще одна, смежная со всеми остальными, вершина.

Звезда 1, −1 (на рис. 38 изображена звезда 1,5).

К наиболее общим классам графов помимо обыкновенных графов и графов Бержа относятся ниже следующие.

Определение 68.1 . Мультиграфом называется граф, который может содержать кратные ребра — несколько ребер между одними и теми же двумя вершинами (несколько ориентированных ребер в одном направлении для орграфа).

Определение 68.2 . Псевдографом называется граф который может содержать кратные ребра и петли.

163

Рисунок 36: Примеры полного, пустого, двудольного графов

164

Рисунок 37: Примеры циклов

Рисунок 38: Граф “Звезда” 1,5

165

Пример псевдографа приведен на рисунке 39 a), пример мультиграфа — на рисунке 39 b).

Рисунок 39: Псевдограф, мультиграф, обыкновенный граф и граф Бержа.

Приведем еще одно определение понятия, которое уже не совсем является графом, но включает все виды графов как подмножества.

Гиперграфом назовем пару = ( , ), где — конечное множество элементов произвольной природы, а —семейство непустых (необязательно различных) подмножеств множества .

Это самый широкий класс, включающий в себя все описанные выше виды неориентированных графов.

2

3

6

5

7

89

Рисунок 40: Гиперграф

166

В дальнейшем под словом граф по умолчанию будем подразумевать обыкновенный граф, или граф Бержа, когда речь будет идти об ориентированном графе.

§69. Общее определение графа

Рассмотрим наиболее общее определение графа. Определения большинства понятий подразумевающихся под термином "граф" являются некоторыми сужениями этого определения.

Определение 69.1 . Пусть заданны конечные множества произвольной природы и , ̸= ?,∩ = ?, и трехместный предикат ( , , )

: × × → { , }.

Будем говорить, что задан граф = ( , , ) с множеством вершин , множеством ребер и инцидентором , если

1. определен для всех упорядоченных троек ( , , ), где , и ;

2.( )( , ){ ( , , )&( ′, ′ )[ ( ′, , ′) ( = ′ & = ′) ( = ′ & =

′)]}. То есть для любого ребра всегда существует две вершины (не обязательно различные),

которые оно соединяет, и никакие другие две вершины не могут быть соединены тем же ребром.

Кроме того для каждого ребра должно выполняться одно и только одно из соотношений:

A.( , )[ ̸= & ( , , ) & ( , , )]

B.( , )[ ̸= & ( , , ) & ( , , )]

C.( ) ( , , )

Ребро удовлетворяющее соотношению A называют неориентированным, удовлетворяющее соотношению B — ориентированным ребром или дугой; ребра удовлетворяющие соотношению C называют петлями. Ребро назовем кратным, если

( , )( 1 )[ ( , , )& ( , 1, )].

Определение 69.2 . Граф будем называть ориентированным или орграфом, если в нем отсутствуют ребра типа A (неориентированные ребра).

Граф будем называть неориентированным, если в нем отсутствуют ребра типа B (ориентированные ребра).

Если граф содержит и ориентированные, и неориентированные ребра, его называют смешанным.

Замечание 69.3 . В определении 69.1 описан смешанный псевдограф.

Определение 69.4 . В рамках определения 69.1 в обыкновенный граф входят только ребра типа A, причем не более одного ребра между любыми двумя вершинами.

167

Определение 69.5 . Граф = ( , , ), для которого верно определение 69.1, называется графом Бержа, если он удовлетворяет условию

( , )( , )[ ( , , )& ( , , ) ( = )].

Определение 69.9 . Два ребра , смежны, если существует вершина которой они оба инцидентны.

Замечание 69.10 . До сих пор мы говорили о конечных графах. Существует также понятие бесконечного графа, для которого множества и могут быть счетными.

§70. Изоморфизм графов

Когда говорят о графах, различают случай помеченных и непомеченных графов. Если для нам требуется хранить кроме структуры еще какую-то важную информацию о вершинах и ребрах графа, им (вершинам и ребрам) приписываются индивидуальные имена и такие графы называются помеченными. С другой стороны, часто индивидуальные имена вершин не важны, а интерес представляет только структура графа. В таком случае графы называют непомеченными.

В обыкновенном графе с вершинами может быть не более ребер.

Следовательно, если рассматривать все возможные способы расстановки ребер, оказывается, что существует всего 2(2) помеченных графов. При этом, далеко не

все графы различаются структурно.

На рисунке 41 изображены два графа. Очевидно, что их структура ничем не

Рисунок 41: Пример изоморфизма

168

различается, но строго по определению они не равны, поскольку их множества ребер не совпадают: например, ребро (1, 6) есть в левом графе, но его нет в правом.

Для обыкновенных графов и графов Бержа определение изоморфизма выглядит следующим образом.

Определение 70.1 . Графы 1 = ( 1, 1) и 2 = ( 2, 2) называют изоморфными,

Несложно показать, что изоморфизм на множестве графов является отношением эквивалентности. Действительно, чтобы доказать рефлексивность, достаточно взять в качестве тождественное отображение 1 → 1. Симметричность доказывается, использованием в качестве искомого отображения −1. Транзитивность будет

следовать из биективности композиции биективных отображений.

Таким образом, по свойству отношений эквивалентности все множество графов делится на классы, любые два графа в которых — изоморфны. В дальнейшем, когда нам не будут принципиальны особенности конкретных графов, мы будем обращаться

Рисунок 42: Изоморфные графы

следующим образом

( )

11

22

3 4 .

43

5 6

65

Несложно убедиться, что условие (33) для графов на рисунке 42 выполняется.

169

В рамках общего определения графа 69.1, определение изоморфизма будет таким.

Определение 70.3 . Два графа 1 = ( 1, 1, 1) и 2 = ( 2, 2, 2) изоморфны, если существуют биекции : 1 →2 и : 1 → 2, такие что

( , 1)( 1)[ 1( , , ) 2( ( ), , ( ), ( ))].

170