2
$\begingroup$

Given a graph and its weight function, is there a general strategy to compute all of its spanning trees of a given weight?

Maybe we can write a program to sort out all the combinations of edges which sum to that weight, and check which among them are spanning trees. But I'm wondering if there are ways that we can compute without the aid of programming.

More specifically, my task to find out all spanning trees of weight 49 and 50 of the below graph. Its min-cost spanning tree is of weight 49, and since every edge has a different weight, the min tree is unique. So I'm up to find all spanning trees of weight 50. I can already see several but don't know how to exhaust all of them...

enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

There are only two spanning trees with weight 50. Each one arises from the unique minimum spanning tree by replacing one tree edge of weight $w$ with a non tree edge of weight $w+1$. Removing an edge disconnects the graph, and the replacement edge must have exactly one endpoint in each of the two resulting connected components.

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