К Лекция №4

В графе G(R_) присутствуют только те дуги, которые отсутствуют в графе G(R).

Операции над отношениями.

Т.к. любое отношение R есть подмножество множества пар W2, то для отношений можно определить все те операции, которые определены для подмножеств фиксированного множества.

1. Операция вложения отношений:

Отношение R1 вложено (включено) в отношение R2, если множество пар, для которых выполнено отношение R1, содержится во множестве пар, для которых выполнено отношение R2.

2. Отношение R_ называется дополнением отношения R, если оно выполняется для тех и только тех пар, для которых не выполняется отношение R.

Т.е. граф G(0) такой, что присутствуют только М2/ R

Или в матричной записи (R_)=1- (R)

- R_+(x)= М/ R+(x) для любого хМ

- R_-(x)= М/ R-(x) для любого хМ

Антидиагональное отношение Е_ является дополнением диагонального отношения Е.

3. Пересечением отношений R1 и R2 называется отношение, определяемое пересечением соответствующих подмножеств из М*М.

4. Объединениемотношений R1 и R2 называется отношение, определяемое объединением соответствующих подмножеств из М*М.

5. Введем операцию обращения отношений:

Обратным к отношению R называется отношение R(-1), определяемое условием xR(-1)yyRx

· (R(-1))= (R);

· граф G(R(-1)) получается из графа G(R) изменением направлений всех дуг;

· R(-1)+(х)= R-(х).

6. Результат последовательного выполнения операций дополнения и обращения не зависит от порядка, в котором они выполняются:

R(-1)_=R_(-1);

Двойственным к R называется отношение Rd, определяемое формулой:

Rd=R_(-1);

Т.е. двойственным к R является отношение Rd, дополнительное к обратному к R.

Специальные свойства бинарных отношений

Рассмотрим свойства отношений, позволяющие выделить типы отношений, широко используемых при анализе систем и в процедурах принятия решений. Для этого введем понятие отношения равенства Е и обратного отношения R(-1), через которые определим 6 свойств, достаточных для классификации интересующих нас соотношений.

Множество М с заданным на нем отношением строгого порядка R называют упорядоченным множеством.

Отношение R на множество М называется отношением нестрогого порядка, если оно может быть представлено в виде:, где R₁- строгий порядок на М, а Е– диагональное отношение.

Любое отношение нестрогого порядка – рефлексивно, антисимметрично и транзитивно.

Важный специальный класс отношений порядка - так называемые древесные порядки. Можно видеть, что наибольший элемент единственен.

Определение.Отношение строгого порядка < на множество М называется отношением древесного порядка если:

1) из того, что x < y и x < z следует, что y и z сравнимы;

2) на множестве М существует наибольший элемент.

Элемент x₀ мы будем называть наибольшим, если для всякого элемента, отличного от х₀, выполнено соотношение у<х₀ , .

Множество М с заданным на нем древесным порядком – называется деревом, а наибольший элемент – корнемдерева.

Дерево задается с помощью графов.

(назовем окрестностью элемента y совокупность элементов Z , для которых выполняется yRZ). Дерево изображается по ярусам.

ZA^ry, где A^r - редукция отношения А, определяемая уравнением A^r=A\A^r

Это означает, что xA^ry, выполняется т. и т. тогда, когда выполняется само соотношение xAy, но не существует промежуточного Z такого, что xAz и ZAy, т.е. xA^ry означает, что x непосредственно подчинен элементу y.

В первом ярусе поместим корень дерева – наибольший элемент x₀. Во втором ярусе элементы, входящие в окрестность x₀. В третьем ярусе поместим элементы, входящие в окрестности элементов второго яруса и т.д., стрелки в графе могут идти только от яруса к ярусу.

При этом от каждого элемента к верхнему ярусу идет ровно одно ребро, а к нижнему может идти сколько угодно ребер.

Общее число ярусов называется высотойдерева – h. Максимальное число элементов в одной окрестности (максимально число ростков, выходящих из одной вершины) называется шириной дерева – d.

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

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

Отношение Е называется отношением равенства (диагональным отношением), если отношение xEy означает, что x и y – один и тот же элемент множества М.

Отношение R^-1 называется обратным отношению R на множестве М, если для любых x, y из М соотношение xR^-1y равносильно соотношению yRx.

На графике G(RM) переход от отношения R к обратному соответствует изменению направления дуг на обратное.

Свойство 1: отношение R является рефлексивным, если E R; т.е. если оно выполнено между объектом и самим xRx.

Например: “x имеет общий признак с y ”, “х похож на у ” и т.д.

На графе G(RM) рефлексивного отношения каждая вершина х М имеет петлю.

Свойство 2: отношение R является антирефлексивным, если R E = ,т.е. если из соотношения xRy следует, что х у (отношение R может выполняться лишь для несовпадающих объектов).

Например: «х старше у», «операция у не может начаться, пока не закончится операция х и т.д.».

Свойство 3: отношение Rявляется симметричным, если R=R^-1, т.е. из выполнения соотношения xRy следует, что выполняется соотношение yRx.

Например: «х похож на у», “операция х несовместна с операцией у ” и т.д.

На графе симметричного отношения каждой дуге (х,у). Соответствует ориентированная ей навстречу дуга. Пару встречно ориентированных дуг можно заменить ребром, тогда симметричное отношение можно описывать неориентированным графом.

Свойство 4: отношение R является симметричным, если , т.е. из двух соотношений xRy и yRx по меньшей мере одно не выполнено.

Например: «х подчиняется у», «операция х выполнена раньше операции у» и т.д.

Если отношение R асимметрично, то оно антирефлексивно.

Доказательство: пусть для выполнено xRx. По определению обратного отношения это значит, что хR^-1x, но тогда т.о. что противоречит асимметричности.

Свойство 5: отношение R является антисимметричным, если , т.е. оба соотношения xRy и yRx выполняются одновременно только тогда, когда х=у.

Например: «операция х является частью операции у».

Свойство 6: отношение Rявляется транзитивным, если для любых элементов х, у, z из М из соотношений xRy, yRz следует соотношение xRz.

Через свойства 1 – 6 можно определить основные типы отношений:

Свойство 7: отношение связности

Отношение R называется линейным (связным) если для любых илиили или оба условия выполняются одновременно. (по крайней мере одно из них обязательно выполнено – в противовес антисимметричным).

В матрице (линейного) связного отношения или a_ij = 1 или a_ij = 1 для любых