Операции над графами. Пусть даны два графа G1(X) и G2(X) на одном и том же множестве вершин

Сумма графов

Пусть даны два графа G₁(X) и G₂(X) на одном и том же множестве вершин. Тогда суммой G(X), графовG₁(X) и G₂(X) является граф, состоя­щий из ребер, принадлежащих G₁(X), либо G₂(X). Таким образом, если

(x_i', x_j') Î G₁(X)и (x_i'', x_j'')Î G₂(X), то (x_i', x_j')Î G(X) и (x_i'', x_j'')Î G(X)

" (x_i', x_j', x_i'', x_j'')Î X.

Символически сумму двух графов обозначают следующим образом:

G(X) = G₁(X) È G₂(X). Аналогично определяется сумма n графов G_i(X)

(i =1, …, n): _n

G(X) = È G_i(X)

^{i =1}

как граф, состоящий из ребер, принадлежащих хотя бы одному из графов G_i(X) (рис. 2.24, а, б).

Операция суммирования графов обладает переместительным свойст­вом, то есть G₁(X) È G₂(X) = G₂(X) È G₁(X).