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:
Anyway, look at this example for partitioning 12 into 7 parts:
At the top are the partitions, in the middle the trees (colored by degree) and at the bottom the desired output of "lattice-trees" (a kind of polyomino, apparently). I should really have a consistent degree color scheme...
Anyway, it's probably not the neatest approach for this particular problem, but I think it would work. Since the number of trees generated from each degree sequence is only a fraction of the space, it seems reasonable to do all-v-all checking for isomorphism in this case.
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.
Anyway, look at this example for partitioning 12 into 7 parts:
Anyway, it's probably not the neatest approach for this particular problem, but I think it would work. Since the number of trees generated from each degree sequence is only a fraction of the space, it seems reasonable to do all-v-all checking for isomorphism in this case.
Comments