Some Stuff

The previous post mentioned the restricted weak composition (RWC), but didn't expand on it at all! Basically, I found this excellent paper : " Generalized Algorithm for Restricted Weak Composition Generation " by Daniel R. Page. It even gave some java code in an appendix - good stuff :) Anyway, a RWC is a composition (which is a partition where order matters) that is weak  - has zeros in it - and the parts are restricted . So [1, 0, 1, 1] is a weak composition of 3 into 4 parts and lets say we have restricted the parts to {0, 1, 2}. Here is an overview of the scheme: where we take a degree sequence, convert to a multiset and use a RWC to get a particular sub-multiset. This allows us to take some count of some subset of elements from the multiset. Doing this for all sub-multisets at each round should then allow us to list graphs - although not without redundant examples:  This shows all starting points for 3 -> [3, 2, 2, 1, 1] and ...

So in the last post about listing trees  I outlined a slightly cumbersome method to list trees from degree sequences. Thinking about it a bit more, it would probably be far easier to just list all trees on some number of vertices and filter out by degree sequence. I talked a little about the WROM algorithm in this old post  which is a constant time generator of 'free' (unlabelled) trees. Anyway, that's boring so I was trying out the more complicated approach. It looks like generating a single  tree from a degree sequence is as simple as the Havel-Hakimi method. Connect the largest degree (dn) to the dn next largest degrees.  Also maintain a list of vertices that have already been connected to, and then at the next step connect only to those not already connected to. So, for [3, 3, 2, 1, 1, 1, 1] we get: You might notice that trees a) and c) are isomorphic. Below the trees labelled by degree are the same trees labelled by DFS discovery order, and below that th...

Although stack overflow is generally just an endless source of questions on the lines of "HALP plz give CODES!? ... NOT homeWORK!! - don't close :(" occasionally you get more interesting ones. For example this one  that asks about degree-restricted trees. Also there's some stuff about vertex labelling, but I think I've slightly missed something there. In any case, lets look at the simpler problem : listing non-isomorphic trees with max degree 3. It's a nice small example of a general approach that I've been thinking about. The idea is to: Given N  vertices, partition 2(N - 1) into N parts of at most 3 -> D = {d0, d1, ... } For each d_i in D, connect the degrees in all possible ways that make trees. Filter out duplicates within each set generated by some d_i. Hmm. Sure would be nice to have maths formatting on blogger.... Anyway, look at this example for partitioning 12 into 7 parts: At the top are the partitions, in the middle the trees...