minimum weight-spanning tree

Consider a graph whose vertices are points in the plane with integer coordinates (x, y) such that 1 ≤ x ≤ n and 1 ≤ y ≤ n, where n ≥ 2 is an integer. Two vertices (x1, y1) and (x2, y2) are adjacent iff |x1 - x2| ≤ 1 and |y1 - y2| ≤ 1. The weight of an edge {(x1, y1), (x2, y2)} is √((x1 - x2)2 + (y1 - y2)2). What is the weight of a minimum weight-spanning tree in the graph?

(A) n-1
(B) n
(C) n+1
(D) log n

Answer

Explain: (Answer- A)

3Comments
Adeema jain @adeema
17 Nov 2018 07:36 am
How?? there can be maximum n*n vertices are possible and in MST all are to be included..so i think ans should be n*n-1 can u please elaborate how it is n-1??
Adeema jain @adeema
17 Nov 2018 07:45 am
Nilabja Sarkar @nilabjasarka
18 Nov 2018 11:00 am
let take 3 vertices a(1,1),b(1,2),c(2,1) the distance a to b is 1 a to c is 1 and b to c is 2 s the weight of minimum spanning tree is 2 (1+1).that means (n-1) if n=3

Pages