Пересечение графов
Пример 2
Пример 1
 |
Рис. 3.23. Суммирование графов с различными множествами вершин
Рис. 3.24. Суммирование графов с одинаковыми множествами вершин
Пусть даны два графа G1(X) и G2(X) на одном и том же множестве вершин. Тогда пересечением графов G1(X) и G2(X) называется граф G(X), состоящий из ребер, принадлежащих и G1(X) и G2(X), то есть если (хi, хj) Î G1(X) и (хi, хj) Î G2(X), то (хi, хj) Î G(X).
Обозначение пересечения двух графов:
G(X) = G1(X) Ç G2(X).
Аналогично пересечение n графов Gi(X) (i = 1, ..., n) обозначается как G(X) =
и определяет граф G(X), состоящий из ребер, принадлежащих всем графам Gi(X).
Для графов примера 2 (рис. 3.24) имеем:
а) пересечение G1(X) Ç G2(X) = Æ (ноль-граф);
б) пересечение G1(X) Ç G2(X) (рис. 3.25).
Для графов, определенных на различных множествах вершин операция пересечения определяется следующим образом:
G(X) = G1(X1) Ç G2(X2) Ç … Ç Gn (Xn) =
где X = X1 Ç X2 Ç ... Ç Xn =
 |
и G(хj) = G1(хj) Ç G2(хj) Ç … Ç Gn(хj) =
, хj Î Х.