Учебное пособие 1161

совокупности G=(X,U) называют графом, причем Х - множество вершин графа, а U - множество линий, которые соединяют все или часть из этих вершин. Если в образовании пары (х, у) играет роль порядок элементов, то эти линии называются дугами и изображаются направленным отрезком прямой (а граф G называется ориентированным графом или орграфом), иначе - ребрами и изображаются просто отрезком прямой (граф G в этом случае называется неориентированным графом или неорграфом). Как правило, граф задается с помощью матрицы смежности А={аij }n n (n= ), элементы которой определяются сле-

дующим образом: 1, (xi , x j ) U

aij =

0, (xi , xj ) U

Пример. Пусть матрица бинарного отношения R, заданного на универсальном множестве U - {a,b,c,d,e}, имеет вид

Тогда соответствующий граф будет иметь вид (рис. 1).

аb

e

Рис. 1

9

Так как отношение является прежде всего множеством упорядоченных пар, то для отношений можно ввести те же операции, что и для множеств, то есть операции объединения, пересечения, абсолютного и относительного дополнений. Кроме того, для отношений существуют специальные операции [1, 6]:

инверсией отношения R называется отношение

R 1 (x, y)|(y,x) R .

Пусть R1,R2 - отношения, заданные на множестве X, тогда

композицией отношений R1 и R2 называется отношение, опре-

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

R2 R1 (x,z)|(x,y) R1 и (y,z) R2 .

Заметим, что R2 R1 R1 R2 .

Рефлексивное, симметричное, транзитивное отношение называется отношением эквивалентности или эквивалентностью (обозначение I) [1, 2].

Классом эквивалентности K(x) элемента х называется множество всех элементов у Х, каждый из которых находится с этим элементом в отношении эквивалентности. Иными словами, класс эквивалентности - это множество эквивалентных элементов.

Для определения, является ли заданное отношение R отношением эквивалентности, используют следующий критерий:

Пусть R - матрица бинарного отношения. Если путем перестановки строк и столбцов ее можно привести к блочнодиагональному виду (на главной диагонали расположены подматрицы, состоящие из 1, а остальные элементы равны 0), то R является отношением эквивалентности, иначе - R не является отношением эквивалентности.

10

Примеры решения задач Задача 1. На множестве А={5, 6, 7, 8, 9, 10, 11, 12, 13, 14,

15} задано бинарное отношение R={(x,y) / x делится на y}. Построить граф данного бинарного отношения.

Решение. Точки x, y A, для которых (x, y) R, соединим дугой, направленной от x к y. Пары (x, x) R изобразим петлей вокруг точки x.

Задача 2. Для бинарного отношения R={(1,2), (2,1), (1,1), (1,3), (3,2), (3,3)}, заданного на множестве X={1, 2, 3}, выяс-

нить, какими свойствами (рефлексивность, симметричность, транзитивность) оно обладает, а какими нет.

Решение. Данное отношение не является рефлексивным, так как для точки 2 Х пара (2,2) R. Отношение не является симметричным, так как, например, пара (1,3) R, а пара (3,1) R. Отношение не является транзитивным, так как, например,

пара (3,2) R и пара (2,1) R, а пара (3,1) R.

Задача 3. Определить свойства отношения R={(x,y)| x,y N и x - делитель y}.

Решение.

транзитивно.

11

Задача 4. Доказать, что если R1 и R2 – симметричные отношения, то R1 R2 также симметричное отношение.

Решение. Чтобы доказать симметричность, рассмотрим элемент (x,y) R1 R2 и покажем, что элемент (y,x) также принадлежит этому отношению. Итак,

Является ли данное отношение эквивалентностью. Для отношения эквивалентности определить классы эквивалентности.

Решение. Переставляя строки и столбцы, попробуем привести матрицу отношения R к блочно-диагональному виду. Поменяем местами столбцы b, d и строки b, d, получим

12

множеств G=(X,U) называется графом. Вершины изображаются точками, а пары элементов – линиями, соединяющими точки, соответствующие образующим пары вершинам [3, 4, 5, 6].

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

Если в определении графа не существенен порядок вершин при образовании пары (хi, xj), то граф называют неориентированным или неорграфом, а пару (xi , xj) - ребром.

Путем в графе G называется такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей [5]. Для неорграфа такая последовательность ребер называется цепью. Если путь (цепь) проходит через вершины х1, ..., хk то будем обозначать его (ее) символом

[x1, …, xk].

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

Путь (цепь), у которого(-ой) начальная и конечная вершина совпадают, называется контуром (циклом).

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

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

Две вершины хi и хj называются смежными, если существует соединяющее их ребро (дуга), при этом вершины называются инцидентными этому ребру (дуге), а ребро (дуга) – инци-

16

дентным(-ой) этим вершинам. Аналогично, два различных ребра (дуги) называются смежными, если они имеют по крайней мере одну общую вершину [3, 4, 5].

Число дуг, исходящих из вершины хi ориентированного графа, называется полустепенью исхода вершины хi и обозна-

чается d (xi ). Число дуг, заходящих в вершину хi ориентиро-

ванного графа, называется полустепенью захода вершины хi и обозначается d (xi ).

В неориентирвоанном графе число ребер, инцидентных данной вершине хi, называется степенью вершины хi и обозначается d(хi). Вершина графа, имеющая степень 0, называется изолированной, а вершина, имеющая степень 1 – висячей.

3.1. Графы с заданной последовательностью степеней

Последовательность (d1,d2,...,dn) неотрицательных це-

лых чисел называется графической, если существует граф с такими вершинами x1, x2,...,xn, что вершина xi имеет степень di . Этот граф называется реализацией последовательности

(d1,d2,...,dn).

Назовем последовательность (d1,d2,...,dn) правильной,

если выполняются два следующих условия: 1) n 1 d1 d2 ... dn ,

n

2)di – четное число.

i 1

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

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

17

Шаг 1. (d1,d2,...,dn) – последовательность степеней,

упорядоченная по невозрастанию. Выберем произвольное dk 0 и «изымем» dk из последовательности, соединяя верши-

ну xk с первыми dk вершинами, не считая саму вершину xk .

Шаг 2. Упорядочим остаточную последовательность в порядке невозрастания.

Шаг 3. Шаги 1–2 выполнять до тех пор, пока не возникнет одна из следующих ситуаций:

а) все остаточные степени равны 0. В этом случае последовательность степеней является графической. Искомый граф получается в результате выполнения шагов, соответствующих порядку изъятия степеней;

б) хотя бы одна из остаточных степеней отрицательна – это означает, что последовательность (d1,d2,...,dn) не являет-

ся графической, т. е. не существует простого графа, который ее реализует.

Для иллюстрации описанного алгоритма рассмотрим пример последовательности

которая после переупорядочивания остаточных степеней принимает вид

Переупорядочивая остаточные степени в D'1, получим

2) графическая. Требуемый граф (рис. 2) получается в результате выполнения шагов, соответствующих порядку изъятия степеней:

x4 x3

Рис. 2. Граф с последовательностью степеней (4, 3, 3, 2, 2)

Задачи и упражнения

1.Доказать, что в неорграфе число вершин с нечетной степенью четно.

2.Построить граф (если он существует) с последовательностью степеней

а) (4,3,3,2,2); б) (5,4,2,2,1) .

19