Saturday, August 31, 2013

solving for the graceful graph

Suppose you have a simple graph like so:

And what you'd like to know is whether there is a way to label the vertices with integers so that the difference between every connected vertex is one of the natural numbers up to the number of connections. For example in this graph we would want the differences between vertices to be 1,2,3,4,5,6,7.
I'm imposing a further restraint that we want want vertex to be labeled 0, and the highest labeled 7.
So two are 0,7 we could guess they could be 0,1,2,3,7. With these numbers every natural number difference up to 7 is possible.

We could brute force the solution by trying every possibility but this goes up with factorial complexity so I found a way to solve them directly.
Consider the following system of equations and the solution (which Maple found in a fraction of a second)
The first equation is basically following from we know what we want the vertex labeled. The last equation is stating that the differences squared because we don't want the order to matter add up to the first 7 natural numbers each squared. And the middle equations I use the trick of raising each vertex to different powers so that we can have 5 different non-linearly related equations. As you can see this outputs four possible solutions which each work to fill out the graph.
The first one is:
See that this satisfies the objective. Later I will update with more information on exactly how fast the computer is able to solve these as the vertex size goes up...

No comments:

Post a Comment