Page 41 - 2589

1 1 1 0  0
 0 1 0  0    0 0 1 0  1  0 0 1 0  1
   0 0 1 0 1     

 1 1 0 0      1 1 2 0 1   1 1 1 0 1 

  1 1 0 1 0    
 0 0 1 1     1 2 1 1 1   1 1 1 1 1 


 0 1 1 0 1 

Нехай A  X  Y, B  Y  Z . Щоб побудувати граф C  B  A,
потрібно до графа відношення A добудувати граф відношення B .

При цьому необхідно вилучити вершини, які відповідають
y
елементам множини Y . При вилученні вершини i кожний шлях,
що проходить через неї від вершин множини X до вершин
множини Z , замінюється однією дугою з тим самим напрямком.

Приклад 3.10: Процес побудови графа композиції відношень
A та B із прикладу 3.8 представлений на рис.3.4.

Рисунок 3.4 – Процес побудови графа композиції відношень A
та B із прикладу 3.11

Якщо A і B – відношення задані на одній множині X , то
графи цих відношень та граф композиції C  B  A будуються на

множині X за загальним правилом.

Приклад 3.11: Побудова графа композиції відношень A і B:
C  B  A, заданих на одній множині де:

A    , xx   ,, x x   ,, x x   ,, x x   ,, x x   ,, x x   ,, x x 
1 1 1 5 2 2 2 4 2 5 5 1 5 4
і

B    , xx   ,, x x   ,, x x   ,, x x   ,, x x   ,, x x   ,, x x 
1 2 2 3 2 4 4 3 1 1 4 5 5 2
наведено на рис.3.5. (на рис.3.5,а відношенню A відповідають
суцільні лінії) і відношенню B відповідають штрихові лінії).
Граф композиції зображено на рис.3.5,б.

41