Page 81 - 2589

яких належать V.

Зірчастий граф для вершини v  G складається з усіх ребер із
початком або кінцем у вершині у і вершин, інцидентних цим

ребрам (включаючи вершину у).
Доповнення H частини H визначається множиною всіх ребер
графа G, що не належать H.

Об'єднання H  H та переріз H  H частин H та H
1 2 1 2 1 2
графа G визначаються природно:

V (H  H ) V (H )  V (H )
1 2 1 2
E (H  H )  E (H )  E (H )
1 2 1 2
Y (H  H ) Y (H )  V (H );
1 2 1 2
E (H  H ) Y (H )  T (H ) 2 .
1 2 1
Дві частиниH та H не перерізаються по вершинах, якщо
1 2
вони не мають спільних вершин, а значить, і спільних ребер.
Об'єднання H  H , частин, що не перерізаються по вершинах,
1 2
називається прямою сумою. Аналогічно визначається пряма сума
будь-якої кількості частин. Частини H й H не перерізаються по
1 2
ребрах, якщо (HE  H )   . Наприклад, для будь-якої частини
1 2
H та її доповнення H сума G  H  H є прямою по ребрах.

5.5 Графи та бінарні відношення

Між орієнтованими графами без кратних ребер із множиною
вершин V   ,...,   і бінарними відношеннями на множині
1 2
V існує взаємно однозначна відповідність: відношенню R
відповідає орієнтований граф (RG ), в якому ребро ( , ) існує
i j
тоді й тільки тоді, коли виконано співвідношення  R .
i j
Аналогічна взаємно однозначна відповідність є між
симетричними бінарними відношеннями і неорієнтованими
графами.

Розглянемо відповідність між операціями над відношеннями
й операціями над графами. Кожне відношення R має заперечення
R , істинне тоді й тільки тоді, коли – хибне. Наприклад, для
відношення рівності a  запереченням є відношення нерівності
b
a  b, а для відношення ортогональності a  , визначеного для
b
елементів векторного простору, запереченням є відношення

( :
відмінності скалярного добутку від 0 a ,b )  . 0 Граф G (R ) є
доповненням графа (RG ) відносно повного орієнтованого графа

P (V ) з множиною вершин V , на якій задано бінарне відношення

81