Декартово произведение

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

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

б) множество вершин, смежных с вершиной (х_i1, х_j2) декартова про­изведения двух графов, определяется как G(x_i1, x_j2) = G₁(x_i1) ´G₂(x_j2), т.е. как декартово произведение множеств вершин графа G₁(X₁), смежных с х_i1 и графа G₂(X₂), смежных с x_j2. Пример приведен на рис. 2.32.

Пример 5.

Для примера 5 G(x₀₁,x₀₂)={(x₁₁,x₁₂), (x₂₁,x₁₂)},

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

G₁(x₁₁)= x₀₁, G₂(x₀₂)=x₁₂, G(x₁₁, x₀₂)=(x₀₁, x₁₂),

G₁(x₂₁)= x₀₁, G₂(x₁₂)=x₀₂, G(x₁₁, x₁₂)=(x₀₁, x₀₂),

G(x₂₁, x₀₂)=(x₀₁, x₁₂),

G(x₂₁, x₁₂)=(x₀₁, x₀₂).

Пусть даны n графов G₁(x₁), G₂ (x₂),..., G_n (x_n). Тогда граф

G(x)= G₁(x₁) ´ G₂(x₂) ´... ´ G_n(x_n) называется декартовым произве-

­­­­де­­нием указанных графов, если

а) x = x₁ ´ x₂ ´... ´ x_n = {(x₁ , x₂ ,..., x_n) / x₁ Î X₁, x₂ Î X₂,..., x_n Î X_n};

б) G(x₁ , x₂ ,..., x_n) = G₁(x₁) ´ G₂(x₂) ´... ´ G_n(x_n) – декартово произве­дение подмножеств вершин графов G_i(x_i) (i = 1,..., n), смежных с верши­нами x₁, x₂,..., x_n.