Re:A game based on the Havel-Hakimi algorithm
by nanofortnight on Monday March 24, 2014 @01:46PM
(#7459839)
The above algorithm was proven to work for all degree sequences by Václav in 1955: https://eudml.org/doc/19050 (Non-English)
Re:A game based on the Havel-Hakimi algorithm
by cschmidt on Monday March 24, 2014 @04:36PM
(#7461272)
For the curious this Václav Havel
http://en.wikipedia.org/wiki/V._J._Havel
is not the better known Czech politician of the same name
Re:A game based on the Havel-Hakimi algorithm
by MichaelAza on Monday March 24, 2014 @04:17PM
(#7461113)
My intuition on this was similar - Pick the highest degree node and connect it to a node of the same degree if available or to one with the next-highest degree, preferring nodes with less connections over those with more. Repeat.
Worked for me so far, and I'm about 6 levels in with the largest node being 8.
1. Pick the node with the highest degree 2. Make all the connections for that node until it has a value of zero by connecting it with the highest-value node that it isn't already connected to
For example, in this scenario: http://i.imgur.com/O8MlWzz.png
The way that I see it is that since the highest-degree node needs to make X number of connections, ensure it can make all of those connections before worrying about anything else. In this case, that means start by connecting the 4 to the next highest value node - the 3, then the 2, then the other 2, then the 1.
This leaves the following situation: http://i.imgur.com/9vZjafr.png
It's kind of easy to see where it goes from there. Sure this is a simple example, but as I said it's worked 100% of the time I've tried it.