You can set up a set of equations like so for each of them, for the graph on the left it is:
a) a+m=b+c+f
b) b+m=a+c+d+e
c) c=m+a+b+d+e+f
d) d=m+b+c+e
e) e=m+b+c+d+f
f) f=m+a+c+e
Where each lettered equation is a letter for a vertex +m = the vertices that lettered vertex is connected to summed.
The set of equations for the figure on the right in the above image is:
a) a+m=b+e+f
b) b+m=a+c+d+e+f
c) c+m=b+d+e
d) d+m=b+c+f
e) e+m=a+b+c+f
f) f+m=a+b+d+e
Now solving each system respectively gives:
It's not too hard to see that these are the same solutions but with some of the letters having exchanged roles.
The idea is the graph is uniquely identified by the system of equations up to renaming vertices, and the solution for each variable is unique for the system of equations up to renaming variables, so isometrical graphs have the same set of solutions up to renaming variables.
** I did find that it can't always distinguish between a graph and the same graph where a vertex is connected to itself but it seems to work for simple graphs
No comments:
Post a Comment