Декартова сумма графов

Декартовой суммой графов G₁(x₁) и G₂(x₂) G(x) = G₁(x₁) + G₂(x₂) на­зывается граф, определенный следующим образом:

а) множество вершин X является декартовым произведением X₁ и X₂, т.е. X = X₁ ´ X₂ = {(x_i1, x_j2) / x_i1 Î X₁, x_j2 Î X₂};

б) множество вершин, смежных с вершиной (x_i1, x_j2) определяется как

G(x_i1, x_j2) = [G₁(x_i1) ´ {x_j2}] È [{x_i1} ´ G₂(x_j2)] (´ - операция декартова про­изведения).

Для примера 5

G(x₀₁, x₀₂) = {G₁(x₀₁) ´ {x₀₂}} È {{x₀₁} ´ G₂(x₀₂)} =

= {(x₁₁, x₀₂), (x₂₁, x₀₂)} È {(x₀₁, x₁₂)},

G(x₀₁, x₁₂) = {G₁(x₀₁) ´ {x₁₂}} È {{x₀₁} ´ G₂(x₁₂)}=

= {(x₁₁, x₁₂),(x₂₁, x₁₂)} È {(x₀₁, x₀₂)},

G(x₁₁,x₀₂) = {(x₀₁, x₀₂)} È {(x₁₁, x₁₂)}, G(x₁₁, x₁₂) = {(x₀₁, x₁₂)} È {(x₁₁, x₀₂)},

G(x₂₁,x₀₂) = {(x₀₁, x₀₂)} È {(x₂₁, x₁₂)}, G(x₂₁, x₁₂) = {(x₀₁, x₁₂)} È {(x₂₁, x₀₂)}.

Соответствующий граф изобра­жен на рис. 2.33.

Граф G(X) называется декарто­вой суммой n графов

G(X) = G₁(X₁) + G₂(X₂) +... + G_n(X_n), если

а) X = X₁ ´ X₂ ´... ´ X_n;

б) G(x₁, x₂,..., x_n) = [G₁(x₁) ´ {x₂} ´... ´ {x_n}] È [{x₁} ´ G₂(x₂) ´... ´ {x_n}] È... È [{x₁} ´ {x₂} ´... ´ G_n(x_n)].

Степени графов