Сумма графов

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

Таким образом, если (х_i', х_j') Î G₁(X) и (х_i",х_j") Î G₂(X), то (х_i', х_j') Î G(X) и (х_i", х_j") Î G(X) " (х_i', х_j', х_i", х_j") Î X.

Символически сумму двух графов обозначают следующим об­разом: G(X) = G₁(X) È G₂(X). Аналогично определяется сумма n графов G_i(X) (i = 1, ..., n):

G(X) =

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

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

Рассмотрим случай, когда операция суммы графов применяется к графам, определенным на различных множествах вершин. Тогда суммой G(X) будет граф

G(X) = G₁(X₁) È G₂(X₂) È … È G_n (X_n) = ,

для которого справедливо:

X = X₁ È X₂ È ... È X_n

и G(х_j) = G₁(х_j) È G₂(x_j) È … È G_n(х_j) = , х_jÎХ.

Сумма графов G₁(X₁) и G₂(X₂) изображена на рис. 3.23.

Пример 1

Рис. 3.23. Суммирование графов с различными множествами вершин

Пример 2

Рис. 3.24. Суммирование графов с одинаковыми множествами вершин