ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
Любовь на множестве людей+ + + Толерантность 134 3.6. Замыкание отношений Замыканием отношения A относительно свойства S, называется отношение С, наименьшее по мощности из всех отношений, обладающих свойством S и содержащих A в качестве подмножества. Для того, чтобы получить замыкание С отношения А относительно свойства S, в него нужно добавить минимально возможное количество пар, после чего полученное отношение будет обладать свойством S. Алгоритмы вычисления рефлексивного и симметричного замыкания довольно просты. Чтобы получить рефлексивное замыкание C ref отношения А, достаточно в отношение А добавить все пары вида (x,x), те. C ref = A I. Чтобы получить симметричное замыкание C sim отношения А, нужно просмотреть все пары отношения A и если пара (x,y) A, то пару (y,x) добавить в отношение, те. C sim = A Транзитивное замыкание C tran отношения А вычисляется сложнее. Рассмотрим несколько алгоритмов его вычисления. Предположим, что отношение А обладает свойством транзитивности, тогда C tran = A. Для определения транзитивности C tran вычислим C2 = C tran 2 и проверим истинность С C tran . Если С C tran истинно, то C tran транзитивно и представляет собой транзитивное замыкание отношения. Если же Сложно, тоне транзитивно и к нему нужно добавить пары, принадлежащие С : C tran := C tran СВ результате добавления пар, принадлежащих С, отношение C tran может стать транзитивным или не транзитивным. Для проверки опять вычислим C2 = C tran 2 и повторим процесс. Алгоритм 3.10 (рис) вычисления транзитивного замыкания отношения А. Вход А — двумерный массив, хранящий матрицу отношения А на множестве М. Выход С — двумерный массив, хранящий матрицу транзитивного замыкания отношения А. Существует наглядная интерпретация понятия транзитивного замыкания в терминах представления отношения в виде графа. Пусть дан граф, представляющий отношение А. Пара (x,y) принадлежит транзитивному замыканию отношения А тогда и только тогда, когда в графе отношения А есть цепочка дуг, ведущая из вершины x в вершину y. Предположим, в графе отношения А вершина x соединяется c вершиной y цепочкой из k дуг, тогда пара (x,y) принадлежит A k и транзитивному замыканию C tran отношения А. Если в графе N вершин и вершины x и 135 – Рис. Блок-схема алгоритма вычисления транзитивного замыкания соединяются цепочкой дуг, то обязательно найдется цепочка, состоящая не более чем из N дуг, соединяющая эти вершины. Поэтому для получения транзитивного замыкания C tran в исходное отношение А нужно добавить пары, принадлежащие А, А, Ат. е. C tran = A i , i = 1, N. Алгоритм 3.11 (рис) вычисления транзитивного замыкания отношения А. Вход А — двумерный массив, хранящий матрицу отношения А на множестве М N — мощность множества М. Выход С — двумерный массив, хранящий матрицу транзитивного замыкания отношения А. Рассмотрим графический способ получения транзитивного замыка- ня, основанный на преобразовании графа исходного отношения. Для того, чтобы построить граф отношения С, являющимся транзитивным замыканием отношения А, изготовим копию графа отношения А. Затем будем отыскивать такие тройки вершин x, y и z, для которых в графе есть дуги изв и изв. Для каждой такой тройки добавим в граф дугу изв, если такой дуги еще нет. Когда таким способом уже нельзя добавить новых дуг, каждые две вершины, соединенные + Конец C tran := C tran Транзитивное замыкание := A C2 := C tran 2 C2 C tran C2 := C tran 2 136 1 Рис. Блок-схема алгоритма вычисления транзитивного замыкания цепочкой дуг, оказываются соединенными одной дугой. Следовательно, построение закончено и граф транзитивного замыкания отношения А получен. Для того чтобы систематизировать процесс добавления дуг, будем последовательно рассматривать все вершины графа с первой до последней. Для каждого пути длины два, проходящего через рассматриваемую вершину, проведем дугу изначальной вершины этого пути в его конечную вершину. Граф транзитивного замыкания отношения А будет построен после однократного исследования всех вершин графа. Повторное исследование вершин не может добавить новых дуг (доказано Уоршаллом в 1962 году. Рассмотрим пример. Отношение А задано графом на рис. Рис. Граф отношения A Анализируя вершину 1 видим дуги изв и изв, образующие путь длины два и проходящий через вершину 1, поэтому добавляем дугу изв (риса. В вершину 2 теперь входят три дуги из 1, 4 и 5, а выходит одна дуга в вершину 3, поэтому добавляем дуги изв, изв Конец C tran := C tran Транзитивное замыкание := 2, N C tran := A 4 2 3 5 137 3, а дуга изв уже есть (рис, б. Из третьей вершины дуги не выходят, поэтому ничего не добавляем. Из четвертой вершины ребро идет в нее же и выходит во вторую, в этом случае новые дуги не добавляются. В пятую вершину дуги не входят, поэтому новые дуги не вводим. Таким образом исследованы все вершины графа, добавлены все необходимые дуги и граф (рис, б) транзитивного замыкания получена б Рис. Формирование транзитивного замыкания отношения А Алгоритм 3.12 (рис) вычисления транзитивного замыкания отношения А основан на рассмотренном выше принципе (алгоритм Уоршалла). Рис. Блок-схема алгоритма вычисления транзитивного замыкания 4 2 1 3 5 4 2 1 3 5 Конец C := A z:=1,N x:=1, N C x,y :=C x,y or C x,z and C z,y y:=1, N Транзитивное замыкание 138 3.7. Классы эквивалентности и фактормножества Пусть задано отношение эквивалентности R на множестве Ми х М. Подмножество элементов множества М, эквивалентных х, называется классом эквивалентности для хи Алгоритм 3.13 построения класса эквивалентности х. Вход М — множество x М R — отношение эквивалентности. Выход [x] – класс эквивалентности для х. 1. [x] := {x}; 2. Для всех у М выполнить если ух, то включить у в [x]; 3. Конец. Для любого элементах множества М класс эквивалентности не пуст, так как содержит в себе по крайней мере элемент х х х. Любые два эквивалентных элементах и у образуют равные классы эквивалентности, те. если х у , то [x]= [y]. Неэквивалентные элементы хи у образуют непересекающиеся классы эквивалентности. Всякое отношение эквивалентности R на множестве М определяет единственное разбиение множества М на классы эквивалентности. Множество всех классов эквивалентности называется фактормноже- ством множества М по эквивалентности R . Алгоритм 3.14 построения разбиения множества М на классы эквивалентности Вход множество Ми отношение эквивалентности R. Выход S — разбиение множества М на классы эквивалентности. 1. А := М S := ; 2. Пока А ≠ выполнять Для Ах Аи построить [x] по алгоритму 3.1, добавить его в S и вычесть из А 3. Конец. 139 Всякое разбиение S множества М определяет единственное отношение эквивалентности R на множестве М. Ниже приведены два алгоритма, определяющие отношение эквивалентности R на множестве М по заданному разбиению S. Алгоритм 3.15 построения отношения эквивалентности R по разбиению S множества М. Вход М — множество S — разбиение множества М. Выход R — отношение эквивалентности на множестве М, определяемое разбиением S. 1. R := ; 2. Для всех пар (х,у) М выполнить если x и y принадлежат одному и тому же подмножеству разбиения S , то (х,у) включить в R; 3. Конец. Алгоритм 3.16 построения отношения эквивалентности R по разбиению S множества М. Вход М — множество S — разбиение множества М. Выход R — отношение эквивалентности на множестве М, определяемое разбиением S. 1. R := ; 2. Для всех подмножеств S i S выполнить каждую пару (х,у), такую, что хи, включить в R; 3. Конец. 3.8. Упорядоченные множества Множество вместе с заданным на нем отношением порядка называют упорядоченным множеством. Множество Мс заданным на нем отношением порядка ≤ будем записывать как пару (М, ≤). Элементы x и y упорядоченного множества (М, ≤) называют сравнимыми по отношению порядка ≤ , если x ≤ y или y ≤ x (напомним, что запись x ≤ y означает, что пара (x, y) принадлежит отношению ≤). В противном случае элементы x и y называют несравнимыми. Если отношение является отношением линейного порядка, то все элементы множества М попарно сравнимы и множество М называется линейно упорядоченным. 140 Элемента называют наибольшим элементом множества М, если для всех x M верно x ≤ a. Элемент b M называют максимальным элементом множества М, если для всех x M верно x ≤ b или x и b несравнимы. Аналогично определяются наименьший и минимальный элементы множества. Минимальный и максимальный элемент существует в любом упорядоченном множестве, причем как максимальных, таки минимальных элементов может быть больше одного. Наибольший и наименьший элемент в упорядоченном множестве может и не существовать. Если же наибольший (наименьший) элемент существует, то он единственный и является максимальным (минимальным. Примером упорядоченного множества может служить множество {1, 2, 3, 5, 6, 10, 15, 30} с отношением делимости, те. пара (x, y) принадлежит отношению делимости, если x является делителем y (y делится на x без остатка. Матрица характеристической функции отношения делимости на множестве, 2, 3, 5, 6, 10, 15, 30} представлена на рис. 3.20. 1 2 3 5 6 10 15 30 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 30 15 10 6 5 3 2 Рис. Матрица характеристической функции отношения делимости Отношением < строгого порядка, ассоциированного с отношением порядка ≤ будем называть отношение, состоящее из всех таких пар (x, y), что x ≤ y и x ≠ y. Чтобы получить матрицу отношения < , нужно обнулить все элементы главной диагонали матрицы отношения ≤. Отношением ⪦ доминирования, ассоциированного с отношением порядка ≤ будем называть отношение, состоящее из всех таких пар (x, y), что x < y и не существует такого элемента z, что x < z < y. Чтобы получить матрицу отношения ⪦ , нужно проанализировать каждую единицу в матрице отношения < , и, если единица соответствует паре (x, y) и существует такой элемент z, что x < z < y, то заменить ее нулем. Матрица характеристической функции отношения доминирования, ассоциированного с отношением делимости на множестве, 2, 3, 5, 6, 10, 15, 30}, представлена на рис. 1 2 3 5 6 10 15 30 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 30 15 10 6 5 3 2 Рис. Матрица характеристической функции отношения доминирования Отношение доминирования удобно представлять графически в виде диаграммы Хассе. На этой диаграмме элементы множества изображаются кружочками. При этом если x ⪦ y, то кружочек, изображающий элемент y, располагается выше кружочка, изображающего элемент x, и соединяются стрелочкой, ведущей от x к y. На рис. 3.22 представлена диаграмма Хассе отношения доминирования, ассоциированного сот- ношением делимости на множестве, 2, 3, 5, 6, 10, 15, 30}. 30 3 10 15 6 5 2 1 Рис. 3.22. Диаграмма Хассе 142 На диаграмме Хассе элементы множества располагаются по уровням. Элемент y располагается на нулевом уровне, если не существует такого элемента x, что x ⪦ y. Элементы нулевого уровня соответствуют нулевым столбцам матрицы отношения доминирования. Если из матрицы удалить строки и столбцы, соответствующие элементам нулевого уровня, то элементы, соответствующие нулевым столбцам полученной матрицы, представляют собой элементы второго уровня. Продолжая процесс, получим элементы каждого уровня. Распределение элементов множества по уровням называют топологической сортировкой. При программной реализации топологической сортировки не стоит удалять строки и столбцы матрицы и каждый раз анализировать всю матрицу с целью поиска нулевых столбцов. Можно поступить следующим образом) найти суммы элементов по всем столбцам матрицы и сохранить их в массиве W; 2) элементы множества, соответствующие нулевым элементам массива, считать элементами очередного уровня 3) нулевые элементы массива W заменить отрицательным числом 4) если в массиве W есть неотрицательные элементы, то вычесть из него поэлементно каждую строку матрицы, соответствующую элементу полученного в п. 2 уровня и перейти к п. 2, иначе конец алгоритма. Применим описанный алгоритм к матрице на рис. 3.21. Суммируя элементы по столбцам матрицы, получим массив W = (0, 1, 1, 1, 2, 2, 2, 3). В этом массиве первый элемент равен нулю, следовательно, соответствующий элемент множества (1) принадлежит нулевому уровню. Заменим его значением –1 и вычтем из массива W строку матрицы, соответствующую элементу 1 множества. Получим W = (–1, 0, 0, 0, 2, 2, 2, 3). В этом массиве второй, третий и четвертый элементы равны нулю, следовательно, соответствующие элементы множества (2, 3 и 5) принадлежат первому уровню. Заменим нули значением и вычтем из массива W строки матрицы, соответствующие элементами множества. Получим W = (–1, –1, –1, –1, 0, 0, 0, 3). В этом массиве пятый, шестой и седьмой элементы равны нулю, следовательно, соответствующие элементы множества (6, 10 и 15) принадлежат второму уровню. Заменим нули значением –1 и вычтем из массива W строки матрицы, соответствующие элементами множества. Получим. Последний элемент массива равен нулю, следовательно, элемент множества (30) принадлежит третьему уровню. Заменим последний элемент значением –1. Неотрицательных элементов теперь в массиве нет, конец алгоритма. 143 Практическое занятие 3.1 Отношения и их свойства Цель занятия изучить способы задания отношений, операции над отношениями и свойства отношений, научиться программно реализовывать операции и определять свойства отношений. Задания Часть 1. Операции над отношениями 1.1. Представить отношения на множестве {1,2,3,4,5,6,7,8,9,10} (см.‖Варианты заданий, па) графиком, графом и матрицей. 1.2. Вычислить значение выражения (см.‖Варианты заданий, п.б) при заданных отношениях (см.‖Варианты заданий, па. 1.3. Написать программы, формирующие матрицы заданных отношений (см.‖Варианты заданий, па. 1.4. Программно реализовать операции над отношениями. 1.5. Написать программу, вычисляющую значение выражения (см. Варианты заданий, п.б) и вычислить его при заданных отношениях (см.‖Варианты заданий, па. Часть 2. Свойства отношений 2.1. Определить основные свойства отношений (см. Варианты заданий, па. 2.2. Определить, являются ли заданные отношения отношениями толерантности, эквивалентности и порядка. 2.3. Написать программу, определяющую свойства отношения, в том числе толерантности, эквивалентности и порядка, и определить свойства отношений (см. Варианты заданий, па. Варианты заданий Варианта) Аи и x < 11 и y < 11 и (x и y четные B = {(x,y) | x N и y N и x < 11 и y < 11 и |x– y| < 5} C = {(x,y) | x N и y N и x < 11 и y < 11 и y 2 кратно б) D = (A B) -1 C A 2 Варианта) Аи и x < 11 и y < 11 и x — четно и y > x} B = {(x,y) | x N и y N и x < 11 и y < 11 и (x – y = 1 или x + y = 11} 144 C = {(x,y) | x N и y N и x < 11 и y < 11 и (x,y) {2,5,8,9,10} б) D = А B A – C Варианта) Аи и x < 11 и y < 11 и (x > y или y > 7)} B = {(x,y) | x N и y N и x < 11 и y < 11 и 10 x + y кратно 3} C = {(x,y) | x N и y N и x < 11 и y < 11 и x — четно и y — нечетно} б) D = A B Варианта) Аи и x < 11 и y < 11 и x — четно и x + y < 10} B = {(x,y) | x N и y N и x < 11 и y < 11 и x + 2 y < 20} C = {(x,y) | x N и y N и x < 11 и y < 11 и (x > 7 или y кратно б D = (A – B) -1 C Варианта) Аи и x < 11 и y < 11 и x + y — четно B = {(x,y) | x N и y N и x < 11 и y < 11 и |x – y| > 5} C = {(x,y) | x N и y N и x < 11 и y < 11 и если x — четно, то y < x, иначе y > б) D=A B – A B Варианта) Аи и x < 11 и y < 11 и x + y — четно и x + y > 8} B = {(x,y) | x N и y N и x < 11 и y < 11 и x + 2 y > 20} C = {(x,y) | x N и y N и x < 11 и y < 11 и (x,y) {1,2,4,8} б) D = A B -1 A C B Варианта) Аи и x < 11 и y < 11 и x + y кратно трем B = {(x,y) | x N и y N и x < 11 и y < 11 и (2 < x < 8 или 2 < y < 8)} C = {(x,y) | x N и y N и x < 11 и y < 11 и x 2 + y 2 < б) D = A 2 – B A -1 C Варианта) Аи и x < 11 и y < 11 и (y > x + 5 или x > y + 5} B = {(x,y) | x N и y N и x < 11 и y < 11 и (x и y четные C = {(x,y) | x N и y N и x < 11 и y < 11 и |x – y| > 5} б) D = A B -1 A – C 145 Варианта) Аи и x < 11 и y < 11 и y< x + 1 и x 2 y} B = {(x,y) | x N и y N и x < 11 и y < 11 и x — четно и x + y < 10} C = {(x,y) | x N и y N и x < 11 и y < 11 и (x,y) {2,3,8} б) D = A A -1 B C Варианта) Аи и x < 11 и y < 11 и (x < y < (9 – x) или (9 - x) < y < x)} B = {(x,y) | x N и y N и x < 11 и y < 11 и x — четно и y — нечетно C = {(x,y) | x N и y N и x < 11 и y < 11 и x y кратно трем} б) D = A B 2 – C Варианта) Аи и x < 11 и y < 11 и (y > x + 3 или y < x – 3)} B = {(x,y) | x N и y N и x < 11 и y < 11 и если x < 9, то y кратно 3} Сии и y < 11 и x + 3 y > б D = A A -1 B C Варианта) Аи и x < 11 и y < 11 и x + y кратно x} B = {(x,y) | x N и y N и x < 11 и y < 11 и (x,y) {2,4,6,8} {1,7,9}} C = {(x,y) | x N и y N и x < 11 и y < 11 и x + y — четно и x y < б) D = A B C – A -1 C Варианта и y N и x < 11 и y < 11 и если x — четно, то y < x, иначе y > x} B = {(x,y) | x N и y N и x < 11 и y < 11 и (y < 7 или x кратно 3)} C = {(x,y) | x N и y N и x < 11 и y < 11 и (x 2 + y 2 > 100 или x = б) D = A B C 2 – Варианта) Аи и x < 11 и y < 11 и (y – x > 5 или x – y > 5} B = {(x,y) | x N и y N и x < 11 и y < 11 и 10 x + 2 y + 1 кратно 3} C = {(x,y) | x N и y N и x < 11 и y < 11 и ((x + 3) < y < (11 – x) или (9 – x) < y < (x + б) D = (A B) ( A – Варианта и y N и x < 11 и y < 11 и x y < y 2 } B = {(x,y) | x N и y N и x < 11 и y < 11 и ((x,y) {2,4,6,8,10} {1,3,5,7,9} или x = y)} C = {(x,y) | x N и y N и x < 11 и y < 11 и (1 < x < 7 или 3 < y < б) D = B A (B C) -1 146 Практическое занятие 3.2 Транзитивное замыкание отношения Цель занятия изучить и выполнить сравнительный анализ алгоритмов вычисления транзитивного замыкания отношения. |