pabs at cantab.net
Sun Sep 10 17:59:45 UTC 2006
Richard Smith said on 10/09/2006 12:04:
> 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).
But if the q-sets span the graph they can only have one vertex in common.
>> 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.
That's not what I am saying - unless the 2n edges consist of 2 edges
each from n q-sets.
As a counterexample, consider 5 blocks with q-sets joining
More information about the ringing-theory