Материал: Методические указания к выполнению лабораторных работ по дисциплине «Дискретная математика» для студентов направления подготовки бакалавров. Собенина О.В., Пак А.А

ределяются следующим правилом:

1, (xi , x j ) R

rij =

0,(xi , xj ) R

Рассмотрим свойства бинарных отношений:

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

рефлексивным, если для х Х (х,х) R;

антирефлексивным, если х Х (х,х) R;

симметричным, если из условия (х,у) R следует, что

(у,х) R;

антисимметричным, если из условия (х,у) R следует,

что (у,х) R;

транзитивным, если из условий (х,у) R и (у, z) R следует, что (x,z) R.

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

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

1, (xi , x j ) U

aij =

0,(xi , xj ) U

14

Заметим, что матрица смежности графа совпадает с матри-

цей соответствующего бинарного отношения.

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

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

a b

e

с d

Рис. 1

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

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

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

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

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

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

15

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

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

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

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

значается символом . Антирефлексивное, антисимметричное,

транзитивное отношение называется отношением строгого

порядка и обозначается символом . Отношения строгого и

нестрогого порядков иначе называют отношениями упорядоченности. Отношение, обратное отношению упорядоченности, также является отношением упорядоченности, т.е. ( ) 1 = .

Представление отношений в ЭВМ

Пусть R A2 и |A|=n. Перенумеруем элементы множества А. Тогда отношение R можно представить матрицей R: array[1..n,1..n] of 0..1, где

1, (xi , x j ) R

R[i,j]=

0,(xi , xj ) R.

Вопросы для самопроверки

1.Что какое отношение?

2.Что необходимо для задания отношения?

3.Каким образом можно представить бинарное отношение с помощью матрицы?

4.Какими свойствами может обладать бинарное отношение?

5.В чем состоит отличие свойства антисимметричности от несимметричности?

6.Можно ли представить отношение в виде графа?

16

7.Какими свойствами обладает отношение эквивалентности?

8.Что такое отношение порядка?

ПРАКТИЧЕСКАЯ ЧАСТЬ Задания

Написать программу, реализующую следующую процедуру:

1.Получить инверсию отношения в виде перечисления упорядоченных пар и матрицы отношения.

2.Даны два отношения А и В, заданные перечислением

пар. Получить A B и B A.

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

4.Даны два отношения А и В. Определить А В, А В, А\В.

A (A B).

7.Даны три отношения А, В и С. Определить A B C ,

A B C .

8. Даны три отношения А, В и С. Определить

(A B) \ (A C), (A\C) B.

9.Определить, является ли данное отношение отношением эквивалентности.

10.Определить, является ли данное отношение отношением строго порядка.

11.Определить, является ли данное отношение отношением нестрого порядка.

17

12.Приведением к блочно-диагональному виду матрицу отношения, определить, является ли данное отношение эквивалентностью.

Порядок выполнения работы

1.Получить задание у преподавателя.

2.Разработать алгоритм решения задачи.

3.Реализовать полученный алгоритм.

4.Проанализировать результаты работы алгоритма.

5.Оформить отчет по лабораторной работе.

Содержание отчета

1.Номер и тема лабораторной работы.

2.Цель выполнения работы.

3.Схема алгоритма.

4.Исходные данные и результаты вычислений.

5.Анализ полученных результатов и вывод по работе.

Контрольные вопросы

1.С помощью каких структур данных можно представить отношение в ЭВМ?

2.Существует ли в языках программирования специальный тип данных для задания отношений?

3.Какие способы представления бинарных отношений

знаете?

4.Бинарное отношение задано графом. Как представить такое отношение в ЭВМ?

5.Бинарное отношение задано перечисление пар. Как представить такое отношение в ЭВМ?

6.Бинарные отношения заданы матрицами. Как получить матрицу пересечения отношений?

7.Бинарные отношения заданы матрицами. Как получить матрицу объединения отношений?

8.Бинарные отношения заданы матрицами. Как получить матрицу композиции отношений?

18