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$
2
  • $\begingroup$ Are the edge weights relevant in some way to counting the spanning trees? $\endgroup$
    – Matt
    Sep 11, 2018 at 14:27
  • $\begingroup$ Yes, it should be a minimal spanning tree, therefore the minimal weights. $\endgroup$
    – user582360
    Sep 11, 2018 at 14:33

1 Answer 1

0
$\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$
0

Your Answer

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