Пусть G G G V G = { 1 , … , n G } V_{G} = \left\{ 1,\ldots ,n_{G}\right\} V G = { 1 , … , n G } E G ⊆ V G × V G E_{G} \subseteq V_{G} \times V_{G} E G ⊆ V G × V G A G A_{G} A G n G × n G n_{G} \times n_{G} n G × n G ( A G ) i j = χ E G ( i , j ) ∈ { 0 , 1 } (A_{G})_{ij} = \chi_{E_{G}}(i,j) \in \left\{ 0,1\right\} ( A G ) ij = χ E G ( i , j ) ∈ { 0 , 1 } i , j ∈ V i,j \in V i , j ∈ V G 1 G_{1} G 1 G 2 G_{2} G 2 n G 1 n G 2 × n G 2 n G 2 n_{G_{1}} n_{G_{2}} \times n_{G_{2}} n_{G_{2}} n G 1 n G 2 × n G 2 n G 2 V G 1 × V G 2 V_{G_{1}} \times V_{G_{2}} V G 1 × V G 2 ( i , j ) ≤ ( k , l ) (i,j) \leq (k,l) ( i , j ) ≤ ( k , l ) i < k i<k i < k i = k i=k i = k j ≤ l j \leq l j ≤ l
Декартово произведение G 1 × G 2 G_{1} \times G_{2} G 1 × G 2 G 1 G_{1} G 1 G 2 G_{2} G 2
V G 1 × G 2 = V G 1 × V G 2 V_{G_{1} \times G_{2}} = V_{G_{1}} \times V_{G_{2}} V G 1 × G 2 = V G 1 × V G 2 и рёбрами
E G 1 × G 2 = { ( ( a , b ) , ( a , b ′ ) ) : a ∈ V G 1 и ( b , b ′ ) ∈ E G 2 } E_{G_{1} \times G_{2}} = \left\{ ((a,b),(a,b')) : a \in V_{G_{1}} \text{ и } (b,b') \in E_{G_{2}} \right\} E G 1 × G 2 = { (( a , b ) , ( a , b ′ )) : a ∈ V G 1 и ( b , b ′ ) ∈ E G 2 } E G 1 × G 2 = ∪ { ( ( a , b ) , ( a ′ , b ) ) : ( a , a ′ ) ∈ E G 1 и b ∈ V G 2 } . \phantom{E_{G_{1} \times G_{2}} =} \; \cup \left\{ ((a,b),(a',b)) : (a,a') \in E_{G_{1}} \text{ и } b \in V_{G_{2}} \right\} . E G 1 × G 2 = ∪ { (( a , b ) , ( a ′ , b )) : ( a , a ′ ) ∈ E G 1 и b ∈ V G 2 } . Отсюда следует, что
( A G 1 × G 2 ) ( i , j ) , ( k , l ) = δ i j ( A G 2 ) ( k , l ) ⊞ δ k l ( A G 1 ) ( i , j ) (A_{G_{1} \times G_{2}})_{(i,j),(k,l)} = \delta _{ij} (A_{G_{2}})_{(k,l)} \boxplus \delta _{kl} (A_{G_{1}})_{(i,j)} ( A G 1 × G 2 ) ( i , j ) , ( k , l ) = δ ij ( A G 2 ) ( k , l ) ⊞ δ k l ( A G 1 ) ( i , j ) где ⊞ \boxplus ⊞ 1 ⊞ 1 = 1 1 \boxplus 1 = 1 1 ⊞ 1 = 1
A G 1 × G 2 = ( A G 1 ⊗ I n G 2 ) ⊞ ( I n G 2 ⊗ A G 2 ) . A_{G_{1} \times G_{2}} = (A_{G_{1}} \otimes I_{n_{G_{2}}}) \boxplus (I_{n_{G_{2}}} \otimes A_{G_{2}}) . A G 1 × G 2 = ( A G 1 ⊗ I n G 2 ) ⊞ ( I n G 2 ⊗ A G 2 ) . Лексикографическое произведение G 1 ∙ G 2 G_{1} \bullet G_{2} G 1 ∙ G 2 G 1 G_{1} G 1 G 2 G_{2} G 2
V G 1 ∙ G 2 = V G 1 × V G 2 V_{G_{1} \bullet G_{2}} = V_{G_{1}} \times V_{G_{2}} V G 1 ∙ G 2 = V G 1 × V G 2 и рёбрами
E G 1 ∙ G 2 = { ( ( a , b ) , ( a , b ′ ) ) : a ∈ V G 1 и ( b , b ′ ) ∈ E G 2 } E_{G_{1} \bullet G_{2}} = \left\{ ((a,b),(a,b')) : a \in V_{G_{1}} \text{ и } (b,b') \in E_{G_{2}} \right\} E G 1 ∙ G 2 = { (( a , b ) , ( a , b ′ )) : a ∈ V G 1 и ( b , b ′ ) ∈ E G 2 } E G 1 ∙ G 2 = ∪ { ( ( a , b ) , ( a ′ , b ′ ) ) : ( a , a ′ ) ∈ E G 1 и b , b ′ ∈ V G 2 } . \phantom{E_{G_{1} \bullet G_{2}} =} \; \cup \left\{ ((a,b),(a',b')) : (a,a') \in E_{G_{1}} \text{ и } b,b' \in V_{G_{2}} \right\} . E G 1 ∙ G 2 = ∪ { (( a , b ) , ( a ′ , b ′ )) : ( a , a ′ ) ∈ E G 1 и b , b ′ ∈ V G 2 } . Таким образом E G 1 × G 2 ⊆ E G 1 ∙ G 2 E_{G_{1} \times G_{2}} \subseteq E_{G_{1} \bullet G_{2}} E G 1 × G 2 ⊆ E G 1 ∙ G 2
( A G 1 × G 2 ) ( i , j ) , ( k , l ) = δ i j ( A G 2 ) ( k , l ) ⊞ ( A G 1 ) ( i , j ) . (A_{G_{1} \times G_{2}})_{(i,j),(k,l)} = \delta _{ij} (A_{G_{2}})_{(k,l)} \boxplus (A_{G_{1}})_{(i,j)} . ( A G 1 × G 2 ) ( i , j ) , ( k , l ) = δ ij ( A G 2 ) ( k , l ) ⊞ ( A G 1 ) ( i , j ) . Следовательно,
A G 1 × G 2 = ( A G 1 ⊗ 1 → n G 2 ) ⊞ ( I n G 2 ⊗ A G 2 ) . A_{G_{1} \times G_{2}} = (A_{G_{1}} \otimes \overrightarrow {1}_{n_{G_{2}}}) \boxplus (I_{n_{G_{2}}} \otimes A_{G_{2}}) . A G 1 × G 2 = ( A G 1 ⊗ 1 n G 2 ) ⊞ ( I n G 2 ⊗ A G 2 ) . Здесь 1 → n G 1 \overrightarrow {1}_{n_{G_{1}}} 1 n G 1 n G 2 × n G 2 n_{G_{2}} \times n_{G_{2}} n G 2 × n G 2
Тензорное произведение G 1 ⊗ G 2 G_{1} \otimes G_{2} G 1 ⊗ G 2 G 1 G_{1} G 1 G 2 G_{2} G 2
V G 1 ⊗ G 2 = V G 1 × V G 2 V_{G_{1} \otimes G_{2}} = V_{G_{1}} \times V_{G_{2}} V G 1 ⊗ G 2 = V G 1 × V G 2 и рёбрами
E G 1 ⊗ G 2 = { ( ( a , b ) , ( a ′ , b ′ ) ) : ( a , a ′ ) ∈ E G 1 и ( b , b ′ ) ∈ E G 2 } . E_{G_{1} \otimes G_{2}} = \left\{ ((a,b),(a',b')) : (a,a') \in E_{G_{1}} \text{ и } (b,b') \in E_{G_{2}} \right\} . E G 1 ⊗ G 2 = { (( a , b ) , ( a ′ , b ′ )) : ( a , a ′ ) ∈ E G 1 и ( b , b ′ ) ∈ E G 2 } . Отсюда следует, что
( A G 1 ⊗ G 2 ) ( i , j ) , ( k , l ) = ( A G 1 ) ( i , j ) ( A G 2 ) ( k , l ) = ( A G 1 ⊗ A G 2 ) ( i − 1 ) n G 2 + k , ( j − 1 ) n G 2 + l . (A_{G_{1} \otimes G_{2}})_{(i,j),(k,l)} = (A_{G_{1}})_{(i,j)} (A_{G_{2}})_{(k,l)} = (A_{G_{1}} \otimes A_{G_{2}})_{(i-1)n_{G_{2}}+k,(j-1)n_{G_{2}}+l} . ( A G 1 ⊗ G 2 ) ( i , j ) , ( k , l ) = ( A G 1 ) ( i , j ) ( A G 2 ) ( k , l ) = ( A G 1 ⊗ A G 2 ) ( i − 1 ) n G 2 + k , ( j − 1 ) n G 2 + l . Таким образом A G 1 ⊗ G 2 = A G 1 ⊗ A G 2 A_{G_{1} \otimes G_{2}} = A_{G_{1}} \otimes A_{G_{2}} A G 1 ⊗ G 2 = A G 1 ⊗ A G 2 ⊗ \otimes ⊗
Нормальное произведение G 1 ⋆ G 2 G_{1} \star G_{2} G 1 ⋆ G 2 G 1 G_{1} G 1 G 2 G_{2} G 2
V G 1 ⋆ G 2 = V G 1 × V G 2 V_{G_{1} \star G_{2}} = V_{G_{1}} \times V_{G_{2}} V G 1 ⋆ G 2 = V G 1 × V G 2 и рёбрами
E G 1 ⋆ G 2 = E G 1 × G 2 ∪ E G 1 ⊗ G 2 . E_{G_{1} \star G_{2}} = E_{G_{1} \times G_{2}} \cup E_{G_{1} \otimes G_{2}} . E G 1 ⋆ G 2 = E G 1 × G 2 ∪ E G 1 ⊗ G 2 . Таким образом,
A G 1 ⋆ G 2 = A G 1 × G 2 ⊞ A G 1 ⊗ G 2 = ( A G 1 ⊗ I n G 2 ) ⊞ ( I n G 2 ⊗ A G 2 ) ⊞ A G 1 ⊗ A G 2 . A_{G_{1} \star G_{2}} = A_{G_{1} \times G_{2}} \boxplus A_{G_{1} \otimes G_{2}} = (A_{G_{1}} \otimes I_{n_{G_{2}}}) \boxplus (I_{n_{G_{2}}} \otimes A_{G_{2}}) \boxplus A_{G_{1}} \otimes A_{G_{2}} . A G 1 ⋆ G 2 = A G 1 × G 2 ⊞ A G 1 ⊗ G 2 = ( A G 1 ⊗ I n G 2 ) ⊞ ( I n G 2 ⊗ A G 2 ) ⊞ A G 1 ⊗ A G 2 .