Page 82 - 2589

R, що розглядається, і множиною дуг - E( P( V ))  V  V . Граф

1

G (R  1 ), де R – відношення, обернене до R, різниться від графа
G (R ) тим, що напрямки всіх дуг замінено на зворотні.
'
Відношення R містить відношення R , якщо вони визначені

'
'
на одній і тій самій множині V та з  R  ,- випливає  R  . У
i 1 J i j
'
цьому випадку кажуть також, що відношення R утворюється з
'
відношення R, і пишуть R  R. Відповідні графи (RG ) та (RG ' )

мають одну й ту саму множину вершин V , а множина E (R ' )

ребер першого є підмножиною множини E (R ' ) ребер другого.

Таким чином, G (R ) є суграфом графа G (R ' ), тобто

(RG ' )  G (R ).

Для будь-яких бінарних відношень R й R , заданих на одній
1 2
і тій самій множині V , можна визначити суму (об'єднання)
R  R і переріз R  R :
1 2 1 2

 ( R  R )   R    R 
i 1 2 j i 1 j i 2 j
 ( R  R )   R    R 
i 1 2 j i 1 j i 2 j
Відповідні графи також є сумою та перерізом:

G (R  R )  G (R )  G (R );
1 2 1 2
G (R  R )  G (R )  G (R ).
1 2 1 2
Деякі типи графів добре описуються на мові бінарних

відношень Наприклад, нуль-граф  (V ), що не має ребер,
відповідає нульовому відношенню O , яке не містить жодної
i j
пари (  ,  )  V  V ; повному орієнтованому графу D (V )
i j
відповідає універсальне (повне) відношення P , завжди істинне.

Якщо R – рефлексивне, то (RG ) має петлі у всіх вершинах;
якщо R – антирефлексивне, то G (R ) не має петель. Якщо R –

транзитивне, то в графі G (R ) для кожної пари ребер ( , ) і
i j
( , ) існує замикальне ребро ( , ).
j k j k

Приклад 4.4 Побудувати граф G, заданий множиною вершин
V  {v ,v ,v ,v } і їх відображеннями R (v )  {v ,v },
1 2 3 4 1 1 2
R (v )  {v ,v }, (vR )  {v ,v }, (vR )  {v ,v }.
2 3 4 3 1 4 4 1 3

82