retagged by
409 views

1 Answer

1 votes
1 votes
The length of an MST (number of edges required to make it) in an nXn grid where each square is a vertex is always n^2-1 ...(1)
Further, if an edge is axial (vertical or horizontal), then its weight should be 1 according to the formula given in the problem. ...(2)
 
Now since we are taking only axial edges, the total weight of the MST from (1) & (2) comes out to be: (n^2-1)*1
So the weight of the MST of this graph should be n^2-1 according to me.
edited by

Related questions

1.1k
views
2 answers
0 votes
gshivam63 asked May 31, 2016
1,138 views
If average weight of a minimum spanning tree is Aavg.Then minimum spanning tree will have weight almost (n-1)Aavg, where n is no of vertices in the graph. It is true or false?why?
560
views
0 answers
0 votes
Lakshman Bhaiya asked Nov 10, 2018
560 views
Which algorithm will be implemented on the weighted graph in which the edges are uniformly distributed over the half-open interval $[0,1)$ ... $D)$ None of these
1.2k
views
3 answers
0 votes
Purple asked Jan 11, 2017
1,178 views
I think all options are wrong
3.6k
views
1 answers
9 votes
firki lama asked Jan 16, 2017
3,607 views
A complete graph G with 5 nodes has positive weight edges,each edge has a distinct weight with an integer value and maximum weight is equal to number of edges in G.What can be maximum weight of minimum spanning tree for graph G?