1
$\begingroup$

Basically, it's this rosalind problem.

You're given a number of nodes and an adjacency list. My initial guess was that the answer was the number of connected components minus 1, since by joining every connected component you would have a connected graph, and since it's stated that there are no cycles, that would be a tree.

Why is this approach wrong? The real answer is just the number of nodes-1-number of edges, which I understand, but can't see how is this not equivalent to my answer.

Also, the sample dataset given bugs me. I see three connected components so I don't see why the answer is not 2. Bear in mind, i'm almost new to graph theory so i'm sorry if i'm missing something simple.

$\endgroup$
0
$\begingroup$

Your first guess is correct. Sometimes there is more than one way to write the same solution.

Clearly, if there are $k$ connected components you'll need exactly $k-1$ edges to connect them (without forming any cycle).

On the other hand, a tree with $n$ nodes must have exactly $n-1$ edges, so if the graph is acyclic and already has $m$ edges, then it is missing $n-1-m$ edges.

Regarding the example: the given graph has $n=10$ vertices, $m=6$ edges, and $k=4$ connected components (not 3), so the answer is $3=k-1=n-m-1$. The sets of vertices in each connected component are $\{1,2,8\}, \{3\}, \{4, 6, 10\}$, and $\{5, 7, 9\}$.

$\endgroup$
1
  • $\begingroup$ Oh, i'm just stupid, thanks for the comment. I thought the sample dataset was wrong, since there was no $3$ in there, but you made me realize that lonely nodes don't appear in the adjacency list. Thanks $\endgroup$ – nicoyanovsky Jan 14 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.