yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->2.3.Операции с бинарными отношениями

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

2.3.Операции с бинарными отношениями

 

Поскольку бинарные отношения - это множества, для них  определены рассмотренные выше операции  над  множествами  (объединение, пересечение, разность, дополнение).  Необходимо заметить:

а) для бинарного отношения R универсальным множеством  W  всегда будет квадрат несущего множества М т.е  операция  "дополнение  R" всегда определена;

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

Операция "прямое произведение" при ее формальном применении  двум отношениям в результате даст отношение арности 4. Естественно потребовать, чтобы при выполнении этой  операции  арность  результата не  изменялась.  Это  достигается  применением  свойства транзитивности при выполнении операции перемножения отношений.

Пример: Пусть на несущем множестве M={a,b,c,d} заданы  два  бинарных отношения: R={ab,ac,ad} и Q={ac,ad,cd}. Произведением этих

отношений будет также бинарное отношение S, элементы которого являются подмножеством  элементов,  полученных  в  результате  формального перемножения множеств R и Q (из всего множества четырех символьных цепочек необходимо отобрать только те, у которых средние элементы одинаковы (при записи средние элементы опускаются):

S = R x Q = {accd,dccd} = {ad,dd}.

Примечание: Для более эффективного выполнения операции  аналитического перемножения отношений  нет  необходимости  перечислять все четырехсимвольные цепочки; нужно выбирать только те  комбинации, у которых второй символ элемента первого отношения совпадает с первым символом элемента второго отношения.

Операцию "прямое произведение  отношений"  для  двух  отношений можно выполнить графически (на графах перемножаемых отношений) по следующему алгоритму: если на графе первого отношения есть  дуга, соединяющая пару вершин (x,y), а на графе второго - дуга,  соединяющая вершины (y,z), то на графе результирующего отношения изобразить дугу, соединяющую вершины (x,z); продолжать до  исчерпания всех вариантов.

Конечный результат перемножения не зависит от способа выполнения операции (аналитический или графический).

Через прямое произведение отношений можно  определить  степени одного отношения: Q x Q = Q^2; Q x Q x Q = Q^3 и т.д.

Транзитивным замыканием отношения Q (обозначается Q+) называют объединение всех целых степеней отношения  Q.  Такое  определение транзитивного замыкания отношения не дает эффективного  алгоритма его построения для заданного отношения (по определению - это бесконечный процесс).

Аналитически это можно записать как объединение степеней  мно-

жества:Q+=Q U Q^2 U Q^3 U Q^4 U ... Q^n... или  Q+=U Q^i (i ї N).

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

Транзитивно-рефлексивное замыкание отношения  Q  (обозначается Q*) - это объединение нулевой степени отношения Q и транзитивного

замыкания отношения Q: Q* = Q^0 U Q+.  Нулевая степень любого отношения, построенного на несущем множестве М={a,b,c,d} имеет вид:

{aa, bb, cc, dd}.

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

 

 

11