§ 25. Граф. Определение

Рассмотрим теоретико-множественное произведение множеств

и его разбиение на две части

и

причем

и

Тогда (а также и G) называют графом, определенным в Граф называют дополнением к G.

В этой главе будем рассматривать частный вид графа

где конечное множество. Графы трактуются здесь, как у Кёнига [21] и Бержа [8].

Рис. 74

Рис. 75.

На рис. 74—78 приведены различные представления одного и того же графа: на рис. 74 — в виде сот, на рис. 75 в виде булевой матрицы, на рис. 76 — с помощью латинской матрицы, на рис. 77 — соответствием, на рис. 78 — с помощью стрелок.

Описание Бержа. В книге Бержа [8] граф описывается соответствием между подмножествами множества Например, для графа на рис. 74—78

В связи с этим граф можно рассматривать как пару

образованную множеством и многозначным отображением множества в себя.

Отображение можно определить для любого подмножества из Например,

Определим граф с помощью обратного отображения

Например, из (25.7)

и соответствующие представления графа получаются, если на рис. 74 и 75 переставить строки со столбцами, на рис. 77, 78 изменить направление всех стрелок, а на рис. 76 переставить строки со столбцами и изменить порядок букв в каждой клетке.

Рис. 76

Рис. 77.

Рис. 78.

Граф имеет порядок если На языке теории графов элемент называют вершиной, а пару где дугой.

Если обозначить через множество всех дуг графа (в нашем примере

то граф можно определить так:

Для удобства дуги обозначают также одной буквой:

Концевые точки. Для дуги назовем началом, концом.

Петля. Дуга, начало и конец которой совпадают, называется петлей. На рис. 78 дуги петли, а на рис. 74, 75 и 76 петли расположены на главных диагоналях.

Рис. 79.

Смежные дуги. Дуги называются смежными, если они различны и имеют общую концевую точку. Например, на рис. 78 дуги и смежные.

Смежные вершины. Две вершины смежны, если они различны и существует дуга, идущая от одной из них к другой. Например, на рис. 78 вершины смежны, а не смежны.

Дуги, инцидентные подмножеству вершин. Пусть задан граф и непустое подмножество множества Говорят, что дуга заходит в если Если же то говорят, что и исходит из В обоих случаях дугу и называют инцидентной подмножеству

Обозначим соответственно через множества дуг, заходящих в и исходящих из него. Например, на рис. 79

Если подмножество сводится к одной вершине, то дугу называют инцидентной этой вершине (заходящей в нее или исходящей из нее).

Полустепень подмножества. Внутренней полустепенью называется число дуг, заходящих в а внешней полустепенью — число дуг, исходящих из Например, на рис. 79

Частичный граф. Подграф. Рассмотрим два графа: . Если

то называют частичным графом графа Иначе говоря, есть частичный граф графа если Граф на рис. 81 — частичный граф графа на рис. 80.

Подграфом графа называется граф если и

Граф на рис 82 — подграф графа на рис. 80.

Рис. 80.

Рис. 81.

Рис. 82.

Рис. 83.

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

Можно определить частичные подграфы (пример на рис. 83).

Рис. 84.

Рис. 85

Рис. 86.

Симметрический граф. Антисимметрический граф. Полный граф. Граф называется симметрическим, если

(любые две вершины соединены двумя противоположно направленными дугами).

Пример такого графа приведен на рис. 84.

Граф называется антисимметрическим, если

(каждая пара смежных вершин соединена лишь в одном направлении, петли отсутствуют). Пример такого графа приведен на рис. 85.

Граф называется полным, если

(любые две вершины соединены по крайней мере в одном направлении).

Пример полного графа дан на рис. 86.

Полный граф с петлями. Граф называется полным графом с петлями, если

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

Рис. 87.

Рис. 88.

Рис. 89.

Дополнительный граф. Пусть заданы граф и соответствующий ему полный граф с петлями

Граф называется дополнительным к графу

Очевидно,

Графы на рис. 88 и 89 дополнительные друг к другу.

Можно описать дополнительный граф по-другому:

УПРАЖНЕНИЯ

(см. скан)

(см. скан)