Материал: Дискретная математика теория и практика

ным графом (или просто графом) называется следующая геометрическая фигура: точки плоскости (вершины), представляющие элементы множества DomP I mP, и ориентированные ребра – каждой паре (a, b) P ставится в

соответствие линия (прямая или кривая), соединяющая точки a и b, на которой стрелкой указано направление от точки a к точке b. Ориентированное ребро,

соответствующее паре (a, b) P , где a = b, называется петлей. Направление

обхода петли при изображении графа фиксируется (например, всегда против часовой стрелки).

Любое бинарное отношение на конечном множестве можно предста- вить ориентированным графом. Обратно, любой ориентированный граф

задает отношение

P = {(a, 1), (a, 2), (b, 2), (c, 3), (d, 1), (d, 3)} A B.

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

Бинарные отношения – это множества упорядоченных пар. Следовательно, над ними можно выполнять любые теоретико-множественные операции, в частности, операции объединения и пересечения. Определим еще две операции над отношениями.

Определение 3.6. Отношением P-1, обратным к отношению P A B, называется подмножество прямого произведения B A такое, что

P−1 = {( y, x) | (x, y) P}.

Пример 3.6. Пусть P = {(a, 1), (b, 2), (c, 3), (d, 4), (e, 5)}. Тогда P-1 = {(1, a), (2, b), (3, c), (4, d), (5, e)}.

Определение 3.7. Композицией (суперпозицией) отношений P A B и Q B С называется множество

P oQ = {(x, y) | x A, y C ( z B) : (x, z) P, (z, y) Q} (рис. 3.3).

Здесь и далее знак « » заменяет союз «и».

37

Рис. 3.3

Пример 3.7. Если P = {(1, 6), (2, 5), (3, 4), (6, 7)}, Q = {(5, 8), (6, 1), (3, 7), (4, 2)}, то

P o Q = {(1, 1), (2, 8), (3, 2)} и Q o P = {(6, 6), (4, 5)}.

Утверждение 3.1. Для любых бинарных отношений P, Q и R выполняются следующие свойства:

1.(P −1 )−1 = P ;

2.(P o Q)−1 = Q −1 o P −1 ;

3.(P o Q) o R = P o (Q o R) (ассоциативность композиции).

Доказательство. Каждое из свойств 1 – 3 представляет собой равенство двух множеств. Следовательно, доказательство можно провести на основании определений 1.5, 3.6 и 3.7.

1.(x, y) P ( y, x) P −1 (x, y) (P −1 )−1.

2.(x, y) (P o Q)−1 ( y, x) P o Q ( z) : ( y, z) P (z, x) Q ( z) : (z, y) P −1

(x, z) Q −1 (x, y) Q −1 o P −1.

3.(x, y) (P o Q) o R ( z) : (x, z) P o Q (z, y) R ( z), ( t) : (x, t) P (t, z) Q

(z, y) R ( t) : (x, t) P (t, y) Q o R (x, y) P o (Q o R).

3.4.Свойства матриц бинарных отношений

жаются по обычному правилу умножения матриц, но произведение и сумма элементов при перемножении матриц находится по правилам п. 1.

3.|| P −1 || = || P ||T .

4.Пусть || P || = ( pij ) , || Q || = (qij ) . Если P Q , то ( i, j ) ( pij ) ≤ (qij ) .

38

3.5. Свойства бинарных отношений

Пусть A ≠ и P A2 .

Определение 3.8. Отношение P на множестве А называется рефлексив- ным, если ( a A) aPa .

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

Отношение P рефлексивно тогда и только тогда, когда каждая вершина графа имеет петлю.

Определение 3.9. Отношение P на множестве А называется антирефлек-

сивным, если ( a A) (a, a) P .

Например, отношение неравенства на некотором числовом множестве, отношение перпендикулярности на множестве всех прямых евклидовой плоскости являются антирефлексивными.

Отношение антирефлексивно тогда и только тогда, когда ни одна вершина графа не имеет петли.

Определение 3.10. Отношение P на множестве А называется симметрич-

ным, если ( a, b A) aPb bPa.

Примерами симметричных отношений являются отношение равенства на некотором числовом множестве, отношение параллельности на множестве всех прямых евклидовой плоскости.

Отношение симметрично тогда и только тогда, когда всякий раз вместе с ребром (х, y) граф содержит ребро ( y, x) .

Определение 3.11. Отношение P на множестве А называется антисим-

метричным, если ( a,b A) aPb bPa a = b .

39

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

Отношение антисимметрично тогда и только тогда, когда вместе с каждым ребром (х, y) граф не содержит ребро ( y, x) . Граф антисимметричного от-

ношения может содержать петли.

Замечание 3.2. Свойство антисимметричности не совпадает со свойством несимметричности. Например, отношение P = {(a, b), (b; a), (a; c)} на множестве

А = {a,b, c} не симметрично, поскольку (a, c) P , а (c, a) P , и не антисимметрично, так как (a,b) P и (b, a) P , но a ≠ b . Диагональ непустого множества А ( id A ) является примером симметричного и антисимметричного отношения. Во-

обще, любое подмножество id A обладает одновременно свойствами сим-

метричности и антисимметричности.

Определение 3.12. Отношение P на множестве А называется транзитив-

ным, если ( a, b, c A) aPb bPc aPc.

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

Отношение транзитивно тогда и только тогда, когда вместе с каждой парой ребер и ( у, z) граф содержит ребро (x, z) .

Утверждение 3.2. Пусть A ≠ и P A2 . Тогда справедливы следующие соотношения:

1.P – рефлексивно idA P;

2.P – антирефлексивно P ∩ idA = ;

3.P – симметрично P = P-1;

4.P – антисимметрично P ∩ P-1 idA;

5.P – транзитивно P o P P.

3.6.Определение свойств бинарного отношения по его матрице

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

1.P – рефлексивно idA P главная диагональ матрицы ||P|| состоит из одних единиц.

2.P – антирефлексивно P ∩ idA = главная диагональ матрицы ||P|| состоит из одних нулей.

3.P – симметрично P = P −1 || P || =|| P ||T матрица ||P|| симметрична относительно главной диагонали.

4.P – антисимметрично P ∩ P−1 id A матрица || P ∩ P−1 || вне главной диагонали содержит только нули.

40

шение P2 .

1.Отношение P2 не рефлексивно, так как главная диагональ матрицы || P2 || не состоит из одних единиц.

2.Отношение P2 не антирефлексивно, так как главная диагональ матрицы

||P2 || не состоит из одних нулей.

3.Отношение P2 не симметрично, так как матрица || P2 || не является симмет-

ричной относительно главной диагонали.

41