in Algorithms retagged by
1,451 views
15 votes
15 votes

In a connected weighted graph with $n$ vertices, all the edges have distinct positive integer weights. Then, the maximum number of minimum weight spanning trees in the graph is

  1. $1$
  2. $n$
  3. equal to number of edges in the graph.
  4. equal to maximum weight of an edge of the graph.
  5. $n^{n-2}$
in Algorithms retagged by
1.5k views

1 comment

Distinct weights: $1$ (unique)

Cycle graphs: $n$

Complete graphs: $n^{n-2}$
3
3

2 Answers

18 votes
18 votes
Best answer

There will be unique min weight spanning tree since all weights are distinct.
Option is A.

edited by

1 comment

The reason it is 1 because, at each step, for any cut of the graph, we would have unique light edge crossing the cut and hence it would be fairly straight forward to select that edge.No Choices here.
6
6
14 votes
14 votes

OPTION a is correct


--> if all weights are distinct values then there exist unique min/max spanning tree.(option a)

Knowing the other option is also important while preparation ::

--> if graph is cyclic graph(n vertices) with same edge weights then there exist n spanning trees.(option b/c)

--> //y if graph is complete graph(n vertices) with same edge weights then there exist nn-2 spaning trees (option e).

//up vote if you  agree.

2 Comments

Awesome explanation for option b/c
0
0
if graph is cycle graph then there will be n spanning tree not for cyclic graph always
0
0
Answer:

Related questions