CartesianProduct - Maple Help

GraphTheory

 CartesianProduct
 compute Cartesian product of graphs
 TensorProduct
 compute tensor product of graph
 ConormalProduct
 compute conormal product of graphs
 LexicographicProduct
 compute lexicographic product of graphs
 ModularProduct
 compute modular product of graph
 StrongProduct
 compute strong product of graphs

 Calling Sequence CartesianProduct(G1, G2, ...) TensorProduct(G1, G2, ...) ConormalProduct(G1, G2, ...) LexicographicProduct(G1, G2, ...) ModularProduct(G1, G2, ...) StrongProduct(G1, G2, ...)

Parameters

 G1, G2, ... - graphs

Description

 • CartesianProduct accepts a sequence of graphs as its arguments and returns the Cartesian product of those graphs.
 • TensorProduct accepts a sequence of graphs as its arguments and returns the tensor product of those graphs.
 • ConormalProduct accepts a sequence of graphs as its arguments and returns the Cartesian product of those graphs.
 • LexicographicProduct accepts a sequence of graphs as its arguments and returns the lexicographic product of those graphs.
 • ModularProduct accepts a sequence of graphs as its arguments and returns the modular product of those graphs.
 • StrongProduct accepts a sequence of graphs as its arguments and returns the strong product of those graphs.

Definitions

 • Let G and H be undirected graphs.
 • Define V to be the set of pairs u:v with u a vertex in G and v a vertex in H.
 • The Cartesian product of G and H is the graph with vertex set V and edges defined by this rule: for u1,u2 vertices in G and v1,v2 vertices in H, there is an edge from u1:v1 to u2:v2 if and only if u1 is adjacent to u2 and v1 = v2, or u1 = u2 and v1 is adjacent to v2.
 • The tensor product of G and H is the graph with vertex set V and defined by this rule: for u1,u2 vertices in G and v1,v2 vertices in H, there is an edge from u1:v1 to u2:v2 if and only if u1 is adjacent to u2 in G1 and v1 is adjacent to v2 in G2.
 • The conormal product of G and H is the graph with vertex set V and defined by this rule: for u1,u2 vertices in G and v1,v2 vertices in H, there is an edge from u1:v1 to u2:v2 if and only if u1 is adjacent to u2 in G1 or v1 is adjacent to v2 in G2.
 • The lexicographic product of G and H is the graph with vertex set V and defined by this rule: for u1,u2 vertices in G and v1,v2 vertices in H, there is an edge from u1:v1 to u2:v2 if and only if u1 is adjacent to u2, or u1=u2 and v1 is adjacent to v2.
 • The modular product of G and H is the graph with vertex set V and defined by this rule: for u1,u2 vertices in G and v1,v2 vertices in H, there is an edge from u1:v1 to u2:v2 if and only if u1 is adjacent to u2 in G1 and v1 is adjacent to v2 in G2, or u1 is not adjacent to u2 in G1 and v1 is not adjacent to v2 in G2.
 • The strong product of G and H is the graph with vertex set V and defined by this rule: for u1,u2 vertices in G and v1,v2 vertices in H, there is an edge from u1:v1 to u2:v2 if and only if u1=u2 and v1 is adjacent to v2, or if u1 is adjacent to u2 and v1=v2, or if u1 is adjacent to u2 and v1 is adjacent to v2.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(\left\{\left\{0,1\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 2 vertices and 1 edge\left(s\right)}}$ (1)
 > $H≔\mathrm{CartesianProduct}\left(G,G\right)$
 ${H}{≔}{\mathrm{Graph 2: an undirected graph with 4 vertices and 4 edge\left(s\right)}}$ (2)
 > $\mathrm{Vertices}\left(H\right)$
 $\left[{"0:0"}{,}{"0:1"}{,}{"1:0"}{,}{"1:1"}\right]$ (3)
 > $\mathrm{Edges}\left(H\right)$
 $\left\{\left\{{"0:0"}{,}{"0:1"}\right\}{,}\left\{{"0:0"}{,}{"1:0"}\right\}{,}\left\{{"0:1"}{,}{"1:1"}\right\}{,}\left\{{"1:0"}{,}{"1:1"}\right\}\right\}$ (4)
 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $H≔\mathrm{CartesianProduct}\left(G,G,G\right)$
 ${H}{≔}{\mathrm{Graph 3: an undirected graph with 8 vertices and 12 edge\left(s\right)}}$ (5)
 > $V≔\mathrm{map}\left(v→\mathrm{Select}\left(\mathrm{IsBinaryDigit},v\right),\mathrm{sort}\left(\mathrm{Vertices}\left(H\right)\right)\right)$
 ${V}{≔}\left[{"000"}{,}{"001"}{,}{"010"}{,}{"011"}{,}{"100"}{,}{"101"}{,}{"110"}{,}{"111"}\right]$ (6)
 > $Q≔\mathrm{RelabelVertices}\left(H,V\right)$
 ${Q}{≔}{\mathrm{Graph 4: an undirected graph with 8 vertices and 12 edge\left(s\right)}}$ (7)
 > $\mathrm{evalb}\left(\mathrm{Edges}\left(Q\right)=\mathrm{Edges}\left(\mathrm{HypercubeGraph}\left(3\right)\right)\right)$
 ${\mathrm{true}}$ (8)
 > $T≔\mathrm{TensorProduct}\left(G,G\right)$
 ${T}{≔}{\mathrm{Graph 5: an undirected graph with 4 vertices and 2 edge\left(s\right)}}$ (9)
 > $\mathrm{Vertices}\left(T\right)$
 $\left[{"0:0"}{,}{"0:1"}{,}{"1:0"}{,}{"1:1"}\right]$ (10)
 > $\mathrm{Edges}\left(T\right)$
 $\left\{\left\{{"0:0"}{,}{"1:1"}\right\}{,}\left\{{"0:1"}{,}{"1:0"}\right\}\right\}$ (11)
 > $\mathrm{G1}≔\mathrm{PathGraph}\left(2\right)$
 ${\mathrm{G1}}{≔}{\mathrm{Graph 6: an undirected graph with 2 vertices and 1 edge\left(s\right)}}$ (12)
 > $\mathrm{G2}≔\mathrm{Graph}\left(4,\mathrm{Trail}\left(1,2,3,4,1\right),\left\{\left\{2,4\right\}\right\}\right):$
 > $\mathrm{ConormalProduct}\left(G,G\right)$
 ${\mathrm{Graph 7: an undirected graph with 4 vertices and 6 edge\left(s\right)}}$ (13)
 > $\mathrm{LG1}≔\mathrm{GraphTheory}:-\mathrm{LexicographicProduct}\left(\mathrm{G1},\mathrm{G2}\right)$
 ${\mathrm{LG1}}{≔}{\mathrm{Graph 8: an undirected graph with 8 vertices and 26 edge\left(s\right)}}$ (14)
 > $\mathrm{Edges}\left(\mathrm{LG1}\right)$
 $\left\{\left\{{"1:1"}{,}{"1:2"}\right\}{,}\left\{{"1:1"}{,}{"1:4"}\right\}{,}\left\{{"1:1"}{,}{"2:1"}\right\}{,}\left\{{"1:1"}{,}{"2:2"}\right\}{,}\left\{{"1:1"}{,}{"2:3"}\right\}{,}\left\{{"1:1"}{,}{"2:4"}\right\}{,}\left\{{"1:2"}{,}{"1:3"}\right\}{,}\left\{{"1:2"}{,}{"1:4"}\right\}{,}\left\{{"1:2"}{,}{"2:1"}\right\}{,}\left\{{"1:2"}{,}{"2:2"}\right\}{,}\left\{{"1:2"}{,}{"2:3"}\right\}{,}\left\{{"1:2"}{,}{"2:4"}\right\}{,}\left\{{"1:3"}{,}{"1:4"}\right\}{,}\left\{{"1:3"}{,}{"2:1"}\right\}{,}\left\{{"1:3"}{,}{"2:2"}\right\}{,}\left\{{"1:3"}{,}{"2:3"}\right\}{,}\left\{{"1:3"}{,}{"2:4"}\right\}{,}\left\{{"1:4"}{,}{"2:1"}\right\}{,}\left\{{"1:4"}{,}{"2:2"}\right\}{,}\left\{{"1:4"}{,}{"2:3"}\right\}{,}\left\{{"1:4"}{,}{"2:4"}\right\}{,}\left\{{"2:1"}{,}{"2:2"}\right\}{,}\left\{{"2:1"}{,}{"2:4"}\right\}{,}\left\{{"2:2"}{,}{"2:3"}\right\}{,}\left\{{"2:2"}{,}{"2:4"}\right\}{,}\left\{{"2:3"}{,}{"2:4"}\right\}\right\}$ (15)
 > $\mathrm{LG2}≔\mathrm{GraphTheory}:-\mathrm{LexicographicProduct}\left(\mathrm{G2},\mathrm{G1}\right)$
 ${\mathrm{LG2}}{≔}{\mathrm{Graph 9: an undirected graph with 8 vertices and 24 edge\left(s\right)}}$ (16)
 > $\mathrm{Edges}\left(\mathrm{LG2}\right)$
 $\left\{\left\{{"1:1"}{,}{"1:2"}\right\}{,}\left\{{"1:1"}{,}{"2:1"}\right\}{,}\left\{{"1:1"}{,}{"2:2"}\right\}{,}\left\{{"1:1"}{,}{"4:1"}\right\}{,}\left\{{"1:1"}{,}{"4:2"}\right\}{,}\left\{{"1:2"}{,}{"2:1"}\right\}{,}\left\{{"1:2"}{,}{"2:2"}\right\}{,}\left\{{"1:2"}{,}{"4:1"}\right\}{,}\left\{{"1:2"}{,}{"4:2"}\right\}{,}\left\{{"2:1"}{,}{"2:2"}\right\}{,}\left\{{"2:1"}{,}{"3:1"}\right\}{,}\left\{{"2:1"}{,}{"3:2"}\right\}{,}\left\{{"2:1"}{,}{"4:1"}\right\}{,}\left\{{"2:1"}{,}{"4:2"}\right\}{,}\left\{{"2:2"}{,}{"3:1"}\right\}{,}\left\{{"2:2"}{,}{"3:2"}\right\}{,}\left\{{"2:2"}{,}{"4:1"}\right\}{,}\left\{{"2:2"}{,}{"4:2"}\right\}{,}\left\{{"3:1"}{,}{"3:2"}\right\}{,}\left\{{"3:1"}{,}{"4:1"}\right\}{,}\left\{{"3:1"}{,}{"4:2"}\right\}{,}\left\{{"3:2"}{,}{"4:1"}\right\}{,}\left\{{"3:2"}{,}{"4:2"}\right\}{,}\left\{{"4:1"}{,}{"4:2"}\right\}\right\}$ (17)
 > $T≔\mathrm{ModularProduct}\left(G,G\right)$
 ${T}{≔}{\mathrm{Graph 10: an undirected graph with 4 vertices and 2 edge\left(s\right)}}$ (18)
 > $\mathrm{Vertices}\left(T\right)$
 $\left[{"0:0"}{,}{"0:1"}{,}{"1:0"}{,}{"1:1"}\right]$ (19)
 > $\mathrm{Edges}\left(T\right)$
 $\left\{\left\{{"0:0"}{,}{"1:1"}\right\}{,}\left\{{"0:1"}{,}{"1:0"}\right\}\right\}$ (20)
 > $H≔\mathrm{StrongProduct}\left(G,G\right)$
 ${H}{≔}{\mathrm{Graph 11: an undirected graph with 4 vertices and 6 edge\left(s\right)}}$ (21)
 > $\mathrm{Vertices}\left(H\right)$
 $\left[{"0:0"}{,}{"0:1"}{,}{"1:0"}{,}{"1:1"}\right]$ (22)
 > $\mathrm{Edges}\left(H\right)$
 $\left\{\left\{{"0:0"}{,}{"0:1"}\right\}{,}\left\{{"0:0"}{,}{"1:0"}\right\}{,}\left\{{"0:0"}{,}{"1:1"}\right\}{,}\left\{{"0:1"}{,}{"1:0"}\right\}{,}\left\{{"0:1"}{,}{"1:1"}\right\}{,}\left\{{"1:0"}{,}{"1:1"}\right\}\right\}$ (23)

Compatibility

 • The GraphTheory[ConormalProduct], GraphTheory[LexicographicProduct], GraphTheory[ModularProduct] and GraphTheory[StrongProduct] commands were introduced in Maple 2023.