recategorized by
698 views
0 votes
0 votes

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 ly1 - y2I <= 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+1

c) n

d) log n

recategorized by

1 Answer

1 votes
1 votes
n-1 considerong one vertex yo be connected to all n-1 vertices would give best case scenario

Related questions

9 votes
9 votes
1 answer
1
firki lama asked Jan 16, 2017
3,394 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 c...
1 votes
1 votes
1 answer
2
radha gogia asked Feb 20, 2016
374 views
I tried by taking n=2 , and took points (1,1) ,(1,2) ,(2,2),(2,1) and I got the minimum weight to be 3 , which is n+1 but according to answer it is n-1
0 votes
0 votes
2 answers
4
Nidhi Budhraja asked Aug 31, 2018
734 views
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?