В.А. Носов - Комбинаторика и теория графов (1023552), страница 4
Текст из файла (страница 4)
Бинарное отношение R на множестве A1 × A 2 определяет отображение F: A1 → A2,если справедливо18′′a1Ra2 и a 1 Ra2 ⇒ a1 = a 1 .Иногда говорят, что множество пар (a1,a2) ∈ R задает график отображения F.2. Операции над отношениями.Исходя из операций над множествами, можно определить теоретикомножественные операции над отношениями. Для простоты считаем, что бинарные отношения заданы на множестве А. Для бинарных отношений R1 и R2 их пересечением(обозначение: R1 I R2 ) называется бинарное отношение, являющееся пересечениемсоответствующих множеств пар элементов из А, т.е.a1 ( R1 I R2 )a2 ⇔ a1R1a2 и a1R2a2Объединением отношений R1 и R2 (обозначение: R1 U R2 ) называется отношение, являющееся объединением соответствующих множеств пар элементов из А, т.е.a1 ( R1 U R2 )a2 ⇔ a1R1a2 или a1R2a2Очевидным образом определяется отношение включения для бинарных отношений, пишем R1 ⊆ R2, если множество пар элементов из А для отношения R1 содержится в множестве пар для отношения R2 .Дополнением отношения R называется отношение R , определяемое условием:a1 R a2 ⇔ (a1a2) ∈ R.
Определим теперь алгебраические операции на бинарных отношениях. Если R - отношение на А, то обратное отношение R-1 определяется условием:a1R-1a2 ⇔ a2Ra1.Если R1, R2 - отношения на А, то их произведение R1 ∗ R2 определяется условием:a1(R1 ∗ R2)a2 ⇔ ∃ b∈ Aa 1 R1 b и bR2a2.∨Транзитивное замыкание R отношения R определяется так:∨a1 R a2 ⇔ ∃ (z0 = a1, z1, … , zn-1, zn = a2) ∈ An+1 | z0Rz1, … , zn-1Rzn∨Легко видеть, что a1 R a2 ⇔ ∃ n | a1Rna2∨Таким образом, R = RU R2 U R3 U LВыясним теперь, как введенные операции над бинарными отношениями выразить с помощью операций на соответствующими им матрицами. Поскольку матрицы отношенийсостоят из элементов 0, 1, то введем операции умножения (⋅) и сложения (v) на множестве {0, 1} с помощью таблиц:19. 01v 010 000 011 011 11Теперь определим операции над матрицами, соответствующие операциям над отношениями.
Пусть отношениям R1 и R2 на множестве А = {a1, … , an} соответствуют матрицыD R1 = (ri1j ) и D R2 = (ri2j ) , i, j ∈1, n . Тогда отношению R1 I R2 соответствует матрицаDR = (cij), где cij = rij1 ⋅ rij2 , i, j ∈1, n .Отношению R1 U R2 соответствует матрица DR = (dij), где dij = rij1 ∨ rij2 , i, j ∈1, nОтношению R1 соответствует матрица DR = (fij), где fij = rij1 , i, j ∈1, nпричемrij10, е с ли rij1 = 1=11, е с ли rij = 0Отношению R1−1 соответствует матрица D TR1 - транспонированная к матрице D R1 .Произведению отношений R1 ⋅ R2 соответствует матрица DR = (gij), гдеgij = ri11 ⋅ r12j ∨ ri12 ⋅ r22j ∨L∨ rin1 ⋅ rnj2 , i , j ∈1, n.Действительно, пусть ai(R1R2)aj . Тогда существует ak, такое, что aiR1ak и akR2aj.
Значит,11= 1, rkj2 = 1. . Отсюда rik⋅ rkj2 = 1и тогда gij = 1. Обратно, пусть gij = 1. Тогда среди слаrikгаемых в выражении для gij хотя бы одно равно 1. Пусть rit1 ⋅ rtj2 = 1 . Отсюдаrit1 = 1 и rtj2 = 1. По определению матриц D R1 = (ri1j ) и D R2 = (rij2 ) имеем aiR1at и atR2aj.Отсюда следует ai(RiR2)aj и поэтому матрица DR = (gij) задает отношение R1 ⋅ R2. Матри∨ца для транзитивного замыкания R вычисляется через операции суммы и степени матрицы DR :D∨ =RDR ∨ DR2 ∨ DR3 ∨ LВ качестве упражнение предоставляется установить связь между операциями над отношениями и их графическими представлениями.203. Свойства операций над отношениями.Поскольку операции пересечения, объединения, дополнения отношения соответствуют теоретико-множественным операциям, то они обладают теми же свойствами.Рассмотрим теперь алгебраические операции.(R )−11.
Свойство обращения:( )♦Имеем a1 R −1−1a2⇔2. Ассоциативный закон:−1= R.a2 R−1 a1⇔a 1 R a2 ♦( R1 ⋅ R2 ) ⋅ R3= R1 ⋅ ( R2 ⋅ R3 )♦ Если a1( R1 ⋅ R2 ) ⋅ R3a2 , то существует z ∈ A, такое, что a1( R1 ⋅ R2 )z, zR3a2Далее a1( R1 ⋅ R2 ) влечет существование w ∈ A такое, что a1R1w и wR2z . Из wR2z иzR3a2 следует w( R2 ⋅ R3 )a2, а из a1R1w и w( R2 ⋅ R3 )a2 следует a1R1( R2 ⋅ R3 )a2.
Обратно,если a1R1( R2 ⋅ R3 ) ⋅ R3a2, то существует w ∈ A, такое, что a1R1w и w( R2 ⋅ R3 )a2 . Далееw( R2 ⋅ R3 )a2 влечет существование z ∈ A, такого, что wR2z и zR3a2. Теперь, из a1R1w иwR2z имеем a1( R1 ⋅ R2 )z, и учитывая справедливость zR3a2,получаем a1( R1 ⋅ R2 ) ⋅ R3a2. ♦3. Правило обращения произведения: (R1⋅R2)-1 = R 2−1 ⋅ R1−1♦ Если a1 (R1⋅R2)-1a2 , то a2 (R1⋅R2)a1. Значит, существует z ∈ A, такое, что a2R1zи zR2a1. Следовательно, имеем a1 R 2−1 z и z R1−1 a2 , откуда a1( R 2−1 ⋅ R1−1 ) a2. Обратно, еслиa1( R 2−1 ⋅ R1−1 ) a2, то существует z ∈ A, такое, что a1 R 2−1 z и z R1−1 a2, откуда имеем a2R1z иzR2a1.
Поэтому a2 (R1⋅R2)a1 и, следовательно, a1 (R1⋅R2)-1a2 .♦4. Дистрибутивный закон:а) ( R1 U R2 ) ⋅ R3 = ( R1 ⋅ R3 )U ( R2 ⋅ R3 )в) R3 ( R1 U R2 ) = ( R3 ⋅ R1)U ( R3 ⋅ R2 )Докажем а). Если a1( R1 U R2 ) R3a2, то существует z ∈ A, такое, чтоa1( R1 U R2 ) z и zR3a2. Но a1( R1 U R2 ) z означает, что либо a1R1z , либо a1R2z.
Поэтомуимеем либо a1R1R3a2, либо a1R2R3a2 и, следовательно, a1( R1 ⋅ R3 U R2 ⋅ R3 ) a2 . Обратно,если a1( R1 ⋅ R3 U R2 ⋅ R3 ) a2, то либо a1R1R3a2, либо a1R2R3a2. В первом случае существует z ∈ A, такое, что a1R1z и zR3a2. Но a1R1z ⇒ a1( R1 U R2 ) z и поэтому снова получаем21a1( R1 U R2 ) R3a2. Во втором случае существует w ∈ A такое, что a1R2w и wR3a2 . Далееa1R2w ⇒ a1( R1 U R2 ) w и поэтому получаем a1( R1 U R2 ) R3a2, что и доказывает равенство а). ♦Равенство в) доказывается аналогично.Другой дистрибутивный закон записывается в виде отношения включения:с) ( R1 I R2 ) ⋅ R3 ⊆ ( R1 ⋅ R3 )I ( R2 ⋅ R3 )d) R3 ( R1 I R2 ) ⊆ R3 ⋅ R1 I R3 ⋅ R2Данные соотношения доказываются аналогично.
Заметим, что здесь нельзя заменитьотношение включения равенством. В качестве упражнения предоставляется доказатьследующие свойства отношений:6. ( R1 U R2 ) −1 = R1−1 U R2−17. ( R1 I R2 ) −1 = R1−1 I R2−18. R1 ⊆ R2 ⇒ R1−1 ⊆ R 2−19. R1 ⊆ R2 ⇒ R1⋅R ⊆ R2⋅R и R⋅R1 ⊆ R⋅R2,∨∀R∨10. R1 ⊆ R2 ⇒ R1 ⊆ R 2∨∨∨11.
R = RУпражнения.1. Доказать, что R−1 = ( R) −1 для любого бинарного отношения R.2. Доказать, что если R1 ⊆ R2, тоа. R1−1 ⊆ R 2−1∨∨б. R1 ⊆ R 23. Пусть А - конечное множество из n элементов. Найти число бинарных отношений на множестве А.2223§ 4. Специальные классы бинарных отношений.1.
Отношения эквивалентности.Бинарное отношение R на множестве А называется рефлексивным, если справедливо aRa, ∀a ∈ A. Рефлексивные отношения представляются матрицами, у которыхна главной диагонали стоят единицы.Отношение R называется симметричным, если для любых a1,a2 ∈ A изa1Ra2 следует a2Ra1 . Симметричные отношения R представляются симметричными матрицами DR = (rij) , т.е. матрицами с условием rij = rji , ∀i, j ∈ 1, n .Отношение R называется транзитивным, если для любых a1,a2,a3 ∈ A из a1Ra2 иa2Ra3 следует a1Ra3. Свойство транзитивности отношения R хорошо интерпретируетсяна графе, изображающем отношение R. Именно, если из вершины a1 имеется дуга в вершину a2, а из вершины a2 имеется дуга в вершину a3, то имеется также дуга из вершиныa1 в вершину a3. Бинарное отношение R на множестве А называется отношением эквивалентности или просто эквивалентностью, если оно рефлексивно, симметрично и транзитивно.
Данное определение отвечает интуитивному понятию одинаковости или неразличимости предметов. Пусть R - отношение эквивалентности на множестве А. Определимкласс эквивалентности, содержащий элемент a ∈ A (обозначение: R[a]), как множествоэлементов из А, находящихся в отношении R с элементом a, т.е.R[a] = {x x ∈ A и xRa}Теорема 1. Отношение эквивалентности R разбивает множество А на попарнонепересекающиеся классы эквивалентных элементов таким образом, что каждый элемент А принадлежит точно одному классу эквивалентности.♦ Покажем, что если два класса эквивалентности содержат общий элемент, тоони совпадают. Пусть z ∈ R[a1] и z ∈ R[a2]. Тогда справедливо zRa1 и zRa2. По симметричности отношения R имеем a1Rz, а по транзитивности R из a1Rz, zRa2 следует a1Ra2.Следовательно, a1 ∈ R[a2].
Аналогично имеем a2 ∈ R[a1]. Отсюда получаем,R[a1] ⊆ R[a2], поскольку xRa1, a1Ra2 ⇒ xRa2 и аналогично заключаем R[a2] ⊆ R[a1].Следовательно, R[a1] = R[a2]. Отсюда следует, что каждый элемент А находится не более, чем в одном классе эквивалентности. Поскольку из рефлексивности R следуетa ∈ R[a], ∀a ∈ A, то значит каждый элемент a ∈ А находится по крайней мере в одномклассе эквивалентности. ♦24Если R - отношение эквивалентности, то число классов эквивалентности называется рангом отношения R.Пример. Рассмотрим множество целых чисел Z.
Зафиксируем натуральное число n и определим отношение Rn на Z. xRny ⇔ x - y делится на число n (обозначение:x ≡ y(mod n)). Легко проверяется, что отношение Rn есть отношение эквивалентности.Класс эквивалентности [a] будет состоять из всех целых чисел вида a + kn, k ∈ Z. Поэтому, [0], [1], … , [n - 1] - различные классы эквивалентности. Других классов нет, таккак любое число a может быть записано в виде a = nq + r, где 0 ≤ r < n и поэтому a ∈ [r].Ранг отношения Rn равен n. Класс [a] называется классом вычетов по модулю n.Пусть А - произвольное множество.
Говорят, что семейство множеств X = (Xi),i ∈ S, где S - множество индексов, Xi ⊆ A образует разбиение множества А, если выполнены условия:1.U Xi = Ai∈S2. Xi I X j = ∅ при i ≠ j, i, j ∈ S.Справедливо обращение предыдущей теоремы.Теорема 2. Пусть X = (Xi), i ∈ S - разбиение множества А. Пусть R - бинарноеотношение на А, определенное условием:a1Ra2 ⇔ ∃i ∈ S a1, a2 ∈ XiТогда отношение R есть отношение эквивалентности.♦ Ясно, что R - рефлексивное отношение, поскольку по условию каждое a ∈ Анаходится в некотором Xi . Симметричность R следует из определения. Осталось проверить транзитивность R.
Пусть имеем a1Ra2 и a2Ra3. Значит, по определению, существуютi1, i2 ∈ S такие, что a1, a2 ∈ X i1 и a2, a3 ∈ X i2 . Из условий a2 ∈ X i1 и a2 ∈ X i2 по свойству разбиения имеем i1 = i2 , и тогда a1, a3 лежат в одном множестве X i1 , поэтому имеем a1Ra3, что и доказывает транзитивность R.
♦Рассмотрим теперь, какие операции над отношениями эквивалентности дают врезультате отношение эквивалентности. Легко доказать следующие утверждения:1. Если R - отношение эквивалентности, то R-1 - также отношение эквивалентности.2. Если R1, R2 - отношения эквивалентности, то R1 I R2 - также отношение эквивалентности.Заметим, что вообще говоря, объединение отношений эквивалентности не является от25ношением эквивалентности.Справедлива следующаяТеорема 3. Объединение R1 U R2 отношений эквивалентности R1 и R2 являетсяотношением эквивалентности в том и только в том случае, когда выполняется условиеR1⋅R2 = R1 U R2Произведение отношений эквивалентности также, вообще говоря, не являетсяотношением эквивалентности. Аналогично может быть доказанаТеорема 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
