### A primitive try at testing graph isomorphism in Excel/VBA

When we consider an adjacency matrix of a graph, each entry shows the
presence of an arc between the nodes. Taking the matrix to the power of two, an
entry shows the number of length two connections between the nodes considered.
Similarly, the adjacency matrix to the power of three shows the number of
length three connections, etc.

In this program a three-dimensional array is constructed, with the
initial matrix at the first position of the third dimension. Next the matrix is
taken to subsequent powers, each being stored at respective positions of the
third dimension. Thus, if we take position 2-3 of the adjacency matrix and look
at its powers on the third dimension, we will see how this node is connected to
the rest.

The program takes the
graph up to the power of the number of its elements. For each adjacency matrix
element the sequence of its successive powers is then written out as a text
string and the strings are sorted in an ascending order. The idea is that for
two isomorphic graphs, the results would be the same.

This, of course, is a
very primitive try at testing the isomorphism of graphs, as in the entire computational complexity theory this is one of only
two problems in existence, the complexity of which is neither polynomial time
nor NP-complete.

## 1 comment:

Hi Jaan , please link to download of your image processing Excel files examples.

thank you.

Flavio

Post a Comment