 GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/CartesianProduct

GraphTheory

 CartesianProduct
 TensorProduct

 Calling Sequence CartesianProduct(G1, G2, ...) TensorProduct(G1, G2, ...)

Parameters

 G1, G2, ... - graphs

Description

 • CartesianProduct accepts a sequence of graphs as its arguments and returns the Cartesian product of those graphs.  If V1 is the set of vertices of G1, and V2 the set of vertices of G2, then the set of vertices of the Cartesian product G of G1 and G2, is the set V1 X V2.  If u is a vertex in G1, and v a vertex in G2, then the vertices in G are labeled by u:v.  For u1,u2 in V1 and v1,v2 in V2, the edge (u1:v1, u2:v2) is in G iff u1 is adjacent to u2 and v1 = v2 or u1 = u2 and v1 is adjacent to v2.
 • TensorProduct accepts a sequence of graphs as its arguments and returns the tensor product of those graphs.  If V1 is the set of vertices of G1, and V2 the set of vertices of G2, then the set of vertices of the tensor product G of G1 and G2, is the set V1 X V2.  If u is a vertex in G1, and v a vertex in G2, then the vertices in G are labeled by u:v. For u1,u2 in V1 and v1,v2 in V2, the edge u1:v1,u2:v2 is in G iff u1 is adjacent to u2 in G1 and v1 is adjacent to v2 in G2.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(\left\{\left\{0,1\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 2 vertices and 1 edge\left(s\right)}}$ (1)
 > $H≔\mathrm{CartesianProduct}\left(G,G\right)$
 ${H}{≔}{\mathrm{Graph 2: an undirected unweighted 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)
 > $T≔\mathrm{TensorProduct}\left(G,G\right)$
 ${T}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 4 vertices and 2 edge\left(s\right)}}$ (5)
 > $\mathrm{Vertices}\left(T\right)$
 $\left[{"0:0"}{,}{"1:0"}{,}{"0:1"}{,}{"1:1"}\right]$ (6)
 > $\mathrm{Edges}\left(T\right)$
 $\left\{\left\{{"0:0"}{,}{"1:1"}\right\}{,}\left\{{"0:1"}{,}{"1:0"}\right\}\right\}$ (7)
 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $H≔\mathrm{CartesianProduct}\left(G,G,G\right)$
 ${H}{≔}{\mathrm{Graph 4: an undirected unweighted graph with 8 vertices and 12 edge\left(s\right)}}$ (8)
 > $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]$ (9)
 > $Q≔\mathrm{RelabelVertices}\left(H,V\right)$
 ${Q}{≔}{\mathrm{Graph 5: an undirected unweighted graph with 8 vertices and 12 edge\left(s\right)}}$ (10)
 > $\mathrm{evalb}\left(\mathrm{Edges}\left(Q\right)=\mathrm{Edges}\left(\mathrm{HypercubeGraph}\left(3\right)\right)\right)$
 ${\mathrm{true}}$ (11)