HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

How many minimal spanning trees are there when all edge costs are distinct?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
distinctcostshowallareedgetreeswhenmanyminimal

Problem

Suppose all costs on edges are distinct. How many minimal spanning trees are possible?

I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal's, and any other greedy algorithm should choose all the smallest weighted edges first. Then, if all weights on all edges are distinct, then there are no two equivalently weighted minimum spanning trees if a greedy algorithm is used.

Solution

Consider Kruskal's or Prim's algorithms to get minimal spanning trees. They consider arcs in increasing order of cost. If all costs are different, the order in which they are added is fixed, and so is the spanning tree constructed. It is unique in this case.

Context

StackExchange Computer Science Q#10728, answer score: 10

Revisions (0)

No revisions yet.