Maths - Graph Theory - Product

Sum, Product and Exponent of Graphs

There are many operations that we can apply to graphs including:

  Nodes Arcs

 

Sum
disjoint union

 

The nodes are added in the same way as sum (disjoint union) of sets.
graph sum

Arcs are just moved with the corresponding nodes.

Product
Cartesian

We can take the
Cartesian product
of two domains
A and B.

graph product

cartesion graph
If:

  • a1->a2 and
  • b1->b2 then:
  • <a1,b1>-><a2,b2>

Product
tensor

tensor graph
If:

  • a1->a2 and
  • b1->b2 then:
  • <a1,b1>-><a2,b2>
Exponent
(function)
 

For f,g∈Hom(A,B)

f->g if f(x)->g(x) for all x∈A

exponent

This page contains the following examples:

Simple Example

First we will try out some sums and products of very simple graphs, just to get a feel for how things work.

Here we construct a very simple graph with two nodes "a" and "b" with an arrow between them:

Graph Adjacency Matrix
graph diagram
  a b
a 0 1
b 0 0

Now we build the other operand for our various sums and products. This will also be a simple graph with two nodes and an arrow between them, but we will draw it differently and use different names to make the resulting diagrams more useful.

Graph Adjacency Matrix
graph diagram
  1 2
1 0 1
2 0 0

Now we have two graphs to combine we can start testing out the sums and products. First a sum (which uses the "+" operator).

As you can see below this produces a graph with 4 vertices and 2 arrows. The arrows do not interact.

Graph Adjacency Matrix
graph diagram
  a b 1 2
a 0 1 0 0
b 0 0 0 0
1 0 0 0 1
2 0 0 0 0

We can now go on to to look at 'merge', this is similar to '+' above, in fact if we used the same operands as above it would have produced the same result. In order to illustrate the effect of 'merge' we will change the second operand slightly, it now has vertex 'a' and vertex '2' so it shares 'a' with the first operand. As we can see below, this common vertex is used by both arrows:

Graph Adjacency Matrix
graph diagram
  a b 2
a 0 1 1
b 0 0 0
2 0 0 0

We can now go on to look at the types of product supported. There are two types of product:

First the tensor product, this generates 4 vertices (2*2) and one arrow which is a sort of composition of the two arrows from the two operands. The tensor product is represented by the '*' operation:

Graph Adjacency Matrix
graph diagram
  a1 b1 a2 b2
a1 0 0 0 1
b1 0 0 0 0
a2 0 0 0 0
b2 0 0 0 0

Now the Cartesian product, this always has the same vertices as the tensor product. However the arrows are different:

Graph Adjacency Matrix
graph diagram
  a1 b1 a2 b2
a1 0 1 1 0
b1 0 0 0 1
a2 0 0 0 1
b2 0 0 0 0

Non-simple Example

Now that we have seen a simple case of these operations we will look at a more complicated case for the products. So that we can check our results we will use the examples on these wiki pages:

Here we construct the first operand from the wiki pages:

Graph Adjacency Matrix
graph theory diagram
  a b c d e
a 0 1 1 0 0
b 0 0 0 1 0
c 0 0 0 1 0
d 0 0 0 0 1
e 0 0 0 0 0

Now we build the other operand from the wiki pages.

Graph Adjacency Matrix
graph theory diagram
  1 2 3 4
1 0 1 0 0
2 0 0 1 0
3 0 0 0 0
4 0 0 0 0

We can now go on to look at the types of product supported. There are two types of product:

First the tensor product:

Graph Adjacency Matrix
graph theory diagram
  a1 b1 c1 d1 e1 a2 b2 c2 d2 e2 a3 b3 c3 d3 e3 a4 b4 c4 d4 e4
a1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
b1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
c1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
d1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
e1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0
b2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
c2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
d2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
e2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
b3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
d3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
e3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a4 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
b4 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
c4 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
d4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
e4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Now the Cartesian product:

Graph Adjacency Matrix
graph theory diagram
  a1 b1 c1 d1 e1 a2 b2 c2 d2 e2 a3 b3 c3 d3 e3 a4 b4 c4 d4 e4
a1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
b1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
c1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
d1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
e1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
a2 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0
b2 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0
c2 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0
d2 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0
e2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
a3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
b3 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
c3 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
d3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
e3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
b4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
c4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
d4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
e4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Check Product Axioms

Here I would like to investigate the properties of the tensor and Cartesian products of graph. So is it associative? First we need to create 3 elements of graph which are not too big but just big enough to be interesting:

Here is the first graph:

graph theory diagram
(47) -> hs21 := ["a","b","c"]::GS
   (47)  "a","b","c"|"a1":"a"->"b","a2":"b"->"c"
                                            Type: DirectedGraph(String)

(48) -> diagramSvg("testGraph/testGraph4s12.svg",hs21,true)
                                                             Type: Void

Here is the second graph:

graph theory diagram
(49) -> hs22 := cycleClosed(["1","2","3"],"b")$GS
   (49)  "1","2","3"|"b1":"1"->"2","b2":"2"->"3","b3":"3"->"1"
                                            Type: DirectedGraph(String)

(50) -> diagramSvg("testGraph/testGraph4s13.svg",hs22,true)
                                                             Type: Void

Here is the third graph:

graph theory diagram
(51) -> hs23 := ["x","y","z"]::GS
   (51)  "x","y","z"|"a1":"x"->"y","a2":"y"->"z"
                                            Type: DirectedGraph(String)

(52) -> diagramSvg("testGraph/testGraph4s14.svg",hs23,true)
                                                             Type: Void

First we will try tensor product.

Here is (hs21*hs22)*hs23:

Graph Adjacency Matrix
graph theory diagram
  a1x b1x c1x a2x b2x c2x a3x b3x c3x a1y b1y c1y a2y b2y c2y a3y b3y c3y a1z b1z c1z a2z b2z c2z a3z b3z c3z
a1x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a1y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a1z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

and here is hs21*(hs22*hs23) :

 

Graph Adjacency Matrix
graph theory diagram
  a1x b1x c1x a2x b2x c2x a3x b3x c3x a1y b1y c1y a2y b2y c2y a3y b3y c3y a1z b1z c1z a2z b2z c2z a3z b3z c3z
a1x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a1y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a1z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

'looseEquals' returns true, so the two graphs are isomorphic, which means that (hs21*hs22)*hs23 is isomorphic to hs21*(hs22*hs23) where '*' is tensor product.

Now we can try Cartesian product.

Here is (hs21*hs22)*hs23:

Graph Adjacency Matrix
graph theory diagram
  a1x b1x c1x a2x b2x c2x a3x b3x c3x a1y b1y c1y a2y b2y c2y a3y b3y c3y a1z b1z c1z a2z b2z c2z a3z b3z c3z
a1x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a1y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a1z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

and here is hs21*(hs22*hs23) :

Graph Adjacency Matrix
graph theory diagram
  a1x b1x c1x a2x b2x c2x a3x b3x c3x a1y b1y c1y a2y b2y c2y a3y b3y c3y a1z b1z c1z a2z b2z c2z a3z b3z c3z
a1x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3x 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a1y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3y 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a1z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b1z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c1z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a2z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b2z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c2z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a3z 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
b3z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c3z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

'looseEquals' returns false, however the diagrams look the same except some of the arrow names are different. So the graphs may well be isomorphic? We really need a proper test for isomorphism between graphs.

Check Using Adjacency Matrix

We can calculate the adjacency matrix of our required product by taking:

(63) -> am21 := adjacencyMatrix(hs21)
         +0  0  0+
   (63)  |1  0  0|
         +0  1  0+
                                       Type: Matrix(NonNegativeInteger)

(64) -> am22 := adjacencyMatrix(hs22)
         +0  0  1+
   (64)  |1  0  0|
         +0  1  0+
                                       Type: Matrix(NonNegativeInteger)

(65) -> hs28 := closedTensor(hs21,hs22,concat)$GS
   (65)
   "a1","a2","a3","b1","b2","b3","c1","c2","c3"|"a1*b1":"a1"->"b2",
     "a1*b2":"a2"->"b3",
     "a1*b3":"a3"->"b1",
     "a2*b1":"b1"->"c2",
     "a2*b2":"b2"->"c3",
     "a2*b3":"b3"->"c1"
                                            Type: DirectedGraph(String)

(66) -> am28 := adjacencyMatrix(hs28)
         +0  0  0  0  0  0  0  0  0+
         |0  0  0  0  0  0  0  0  0|
         |0  0  0  0  0  0  0  0  0|
         |0  0  1  0  0  0  0  0  0|
   (66)  |1  0  0  0  0  0  0  0  0|
         |0  1  0  0  0  0  0  0  0|
         |0  0  0  0  0  1  0  0  0|
         |0  0  0  1  0  0  0  0  0|
         +0  0  0  0  1  0  0  0  0+
                                       Type: Matrix(NonNegativeInteger)

(67) -> kroneckerProduct(am21,am22)
         +0  0  0  0  0  0  0  0  0+
         |0  0  0  0  0  0  0  0  0|
         |0  0  0  0  0  0  0  0  0|
         |0  0  1  0  0  0  0  0  0|
   (67)  |1  0  0  0  0  0  0  0  0|
         |0  1  0  0  0  0  0  0  0|
         |0  0  0  0  0  1  0  0  0|
         |0  0  0  1  0  0  0  0  0|
         +0  0  0  0  1  0  0  0  0+
                                       Type: Matrix(NonNegativeInteger)

(68) -> hs29 := closedCartesian(hs21,hs22,concat)$GS
   (68)
   "a1","a2","a3","b1","b2","b3","c1","c2","c3"|"b1#1":"a1"->"a2",
     "b2#1":"a2"->"a3","b3#1":"a3"->"a1","a1#1":"a1"->"b1",
     "a1#2":"a2"->"b2","a1#3":"a3"->"b3","b1#2":"b1"->"b2",
     "b2#2":"b2"->"b3","b3#2":"b3"->"b1","a2#1":"b1"->"c1",
     "a2#2":"b2"->"c2","a2#3":"b3"->"c3","b1#3":"c1"->"c2",
     "b2#3":"c2"->"c3","b3#3":"c3"->"c1"
                                            Type: DirectedGraph(String)

(69) -> am29 := adjacencyMatrix(hs29)
         +0  0  1  0  0  0  0  0  0+
         |1  0  0  0  0  0  0  0  0|
         |0  1  0  0  0  0  0  0  0|
         |1  0  0  0  0  1  0  0  0|
   (69)  |0  1  0  1  0  0  0  0  0|
         |0  0  1  0  1  0  0  0  0|
         |0  0  0  1  0  0  0  0  1|
         |0  0  0  0  1  0  1  0  0|
         +0  0  0  0  0  1  0  1  0+
                                       Type: Matrix(NonNegativeInteger)

(70) -> kroneckerSum(am21,am22)
         +0  0  1  0  0  0  0  0  0+
         |1  0  0  0  0  0  0  0  0|
         |0  1  0  0  0  0  0  0  0|
         |1  0  0  0  0  1  0  0  0|
   (70)  |0  1  0  1  0  0  0  0  0|
         |0  0  1  0  1  0  0  0  0|
         |0  0  0  1  0  0  0  0  1|
         |0  0  0  0  1  0  1  0  0|
         +0  0  0  0  0  1  0  1  0+
                                       Type: Matrix(NonNegativeInteger)

That concludes our overview of ways to combine graphs such as sums and products graphs, click here to go to the next stage of the tutorial which is about ways to create new graphs by mapping from existing graphs.


metadata block
see also:

For a discussion about using and representing graphs in category theory see this page.

There is a program which can represent and do calculations on graph theory on this page.

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.