1
$\begingroup$

I'm counting minimal spanning trees and my suggestion was the following, when I have a graph with 10 vertices and 13 edges:

For a minimal spanning tree I need 1 edge less then vertices, so (10,9). I can choose now 4 edges to be deleted to get a minimal spanning tree. However I have to take care to not disconnect the graph. But I'm missing something. Do I have to take care of 4 or 5 circles in the following example? And how can I compute then the amount of spanning trees? Is there a closed formula (not Prims algorithm)?

It should be mentioned, that the normal edges are weighted twice as the bolded edges.

enter image description here

$\endgroup$
  • $\begingroup$ Are the edge weights relevant in some way to counting the spanning trees? $\endgroup$ – Matt Sep 11 '18 at 14:27
  • $\begingroup$ Yes, it should be a minimal spanning tree, therefore the minimal weights. $\endgroup$ – John Smith Sep 11 '18 at 14:33
1
$\begingroup$

Problems like this typically require a bit of case-work.

Let's view the graph as two triangles connected by three vertical paths.

We need to delete four edges. Since we want minimal spanning trees, we should delete as many high-weight (thin) edges as possible.

However, we have to delete at least one edge from the top triangle and one edge from the bottom triangle. (There are 9 ways to do this.)

The remaining two deletions can be thin edges: We just need to make sure we cut two of the three vertical paths. Depending on which two paths we cut, there are either 2, 4, or 2 ways to do this.

So in total there are $9 \times (2+4+2) = 72$ minimal spanning trees.

$\endgroup$

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.