Saturday, July 27, 2013

Completing my 32nd problem on Rosalind

I completed my 32nd problem on Rosalind.  As is sometimes the case I over-thought the problem.  Here's the short of it:

Give a count of nodes in a tree graph and a set of lines connecting particular pairs of nodes, how many additional lines will be needed to connect all of the nodes.  So here's the thing, there's really only one way to connect three nodes.  Here's the two ways to connect four nodes:
Count the nodes and count the lines.  There's a pattern there.  I don't know why I didn't see it.  I got bogged down counting the nodes that weren't connected to any other nodes and the sets of connected nodes:
OK, that's 13 nodes, 3 sets of connected nodes and 3 unconnected nodes.  Let's see, that's two lines to connect the three sets and three lines to connect the unconnected nodes for 5 lines.  That's 13 - 10 connected nodes for 3 unconnected nodes and 3 sets of connected nodes and - 1 because one set counts as the base. 13 - 10 + 3 - 1 = 5.  But how many nodes? 13 and how many lines are needed to connect them and how many lines have been defined?

That's as close as I'm going to get to providing the answer to Completing a Tree, my 32nd problem.

2 comments:

  1. Thankyou Gary - like you I was stuck and overthinking it but realised the answer as soon as I saw your first diagram!

    ReplyDelete
  2. Ah thank you, I couldn't figure out why the third edge was required and then, thanks to your explanation, I realised that I was forgetting 3 as a loose node.

    ReplyDelete