[r-t] q-sets
Richard Smith
richard at ex-parrot.com
Sun Sep 10 11:04:02 UTC 2006
Philip Saddleton wrote:
> For it to be possible to connect all the blocks with the minimum number
> of q-sets (i.e. n for 2n+1 blocks), it is sufficient that the graph
> formed by these q-sets is connected.
I think we need to require that every pair of connected
q-sets have precisely one vertex in common -- in principle
it is possible to have two vertices in common, even with
size 3 q-sets (think OMI and 3H in PB6).
> Clearly we can arbitrarily remove
> one edge from each q-set and the graph will be still be connected. It
> now has 2n edges, and so is a tree.
But the reverse isn't obviously true -- given an arbitrary
tree with 2n edges (e.g. a spanning tree of the graph), we
cannot obviously add another n edges to form a connected
graph of q-sets.
So it's not obvious (to me) that this implies that an extent
covered by 2n+1 iblocks an always be connected by n q-sets.
RAS
More information about the ringing-theory
mailing list