Дискретная математика

17 если (ai,bj)eR, то из вершины а, идёт дуга в вершину bj, иначе - из я,- нет дуги в bj. Пусть, например, А ~ {1, 2, 3, 4, 5, 6} и 7? таково, что; aRb тогда и только тогда, когда а<Ь. Рассмотрим некоторые способы задания этого отношения. Задание R перечислением: R={(\,2), (1,6), (2,3),(2,4),..., (2,6), Г5,6Л. Задание R матрицей Ац: Задание R орграфом дано на рис. 1.9. I Лд - 1 2 3 4 5 6 1Г0 1 1 1 1 2 0 0 1 1 1 3 0 0 0 1 1 4 0 0 0 0 1 5 0 0 0 0 0 61^0 О О О О О Рис. 1.9 Матрица Li^ -(l,j) отношения R получится из матрицы Ац, если в этой матрице всюду вместо 1 записать Я, а вместо О записать Л. § 5. Операции над отношениями Так как отношения на Л и S являются подмножествами, то над ними можно ввести все теоретико-множественные операции, например; 1) пересечение отношений (RinRz), здесь и далее перечисляемых пунктах 2)-4), Rj и R2 произвольные бинарные отношения; 2) объединение отношений (RjUR^)-, 3) разность отношений (RMi)', 4) дополнение к данному отношеншо R: CR= R ={AxB)\R, {х,у)е R тогда и только тогда, когда (x,y}eR. Кроме того, введем новые операции: 5) обратное KR отношениеR''={(Ь,а): (a,b)eR}. В дальнейшем вместо «тогдаи только тогда» записываем:^; / вместо «существует» записываем; Д ' вместо «всех (каждого)» записываем: V. 7) композиция отношений. Пусть R - отношение на множествах А vi В, S - отношение на множествах S и С. композицией R я S называется отношение (обозначаемое 6 И Б Л И О Т Н О А