Операции над графами
Пусть даны два графа 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) и (хi", хj") Î G(X) " (хi', хj', хi", хj") Î X.
Символически сумму двух графов обозначают следующим образом: G(X) = G1(X) È G2(X). Аналогично определяется сумма n графов Gi(X) (i = 1,..., n):
G(X) =
как граф, состоящий из ребер, принадлежащих хотя бы одному из графов Gi(X) (рис. 3.24).
Операция суммирования графов обладает переместительным свойством: G1(X) È G2(X) = G2(X) È G1(X).
Рассмотрим случай, когда операция суммы графов применяется к графам, определенным на различных множествах вершин. Тогда суммой G(X) будет граф
G(X) = G1(X1) È G2(X2) È … È Gn (Xn) =,
для которого справедливо:
X = X1 È X2 È... È Xn
и G(хj) = G1(хj) È G2(xj) È … È Gn(хj) =, хjÎХ.
Сумма графов G1(X1) и G2(X2) изображена на рис. 3.23.