Операции над графами

1.

8. Операции над графами
a) Дополнением графа G1 (V1 , E1 ) называется граф G1 (V1 , E1 ), множеством вершин
которого является множество V , а множеством его ребер является множество
E1 { e V1 V1 : e E1 }.
1
b) Объединением графов G1 (V1 , E1 ) и G2 (V2 , E2 ) при условии, что V1 V2 ; E1 E2 ,
называется граф G1 (V1 , E1 ) и G2 (V2 , E2 ), множеством вершин которого является
множество V1 V2 , а множеством его ребер является множество E1 E2 .
c) Пересечением графов G1 (V1 , E1 ) и G2 (V2 , E2 ) называется граф G1 (V1 , E1 ) G2 (V2 , E2 )
множеством вершин которого является множество V1 V2 , а множеством его
ребер – множество E1 E2 .
d) Суммой по модулю два графа G1 (V1 , E1 ) и G2 (V2 , E2 ) при условии, что V1 V2 ; E1 E2 ,
называется граф G1 (V1 , E1 ) G2 (V2 , E2 ), множеством вершин которого
является множество V1 V2 , а множеством его ребер – множество E1 E2 .
Другими словами, этот граф не имеет изолированных вершин и состоит только из
ребер, присутствующих либо в первом графе, либо во втором, но не в обоих
графах одновременно.