The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes

Consider a graph whose vertices are points in the plane with integer co-ordinates $(x,y)$ such that $1 \leq x \leq n$ and $1 \leq y \leq n$, where $n \geq 2$ is an integer. Two vertices $(x_1, y_1)$ and $(x_2, y_2)$ are adjacent iff $\mid x_1-x_2 \mid \leq 1 \text { and } \mid y_1 – y_2 \mid \leq 1$. The weight of an edge $\{(x_1, y_1), (x_2, y_2)\} \text{ is } \sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2}$

  1. What is the weight of a minimum weight-spanning tree in this graph? Write only the answer without any explanations.

  2. What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any explanations.

asked in Algorithms by Veteran (59.6k points)
edited by | 1.3k views
what answer you got for a?

4 Answers

+22 votes
Best answer

Consider $n=3$, we have $9$ vertices in the plane. The vertices are:

$(1,1),\quad(1,2),\quad (1,3), \quad (2,1),\quad    (2,2),\quad (2,3),\quad (3,1),\quad (3,2),\quad (3,3)$ 

So, the corresponding graph will be:


The cost of the  edge between the vertices $(2,3)$ and $(2,2)=1$  and  the cost of the edge between the vertices $(2,2)$ and $(2,1)=1$.

Minimum spanning tree:

(One of the possibilities)


There is no problem with minimum spanning tree. We have $n^{2}$ vertices so, the minimum spanning tree contains $n^{2}- 1$ edges of cost $1$. So, the cost of the minimum spanning tree is $n^{2}-1$.

Maximum spanning tree:


In this maximum spanning tree of $n^{2}$ $-$$ 1$ edges $n^{2}$ $-$$ 2$ edges is of cost ${\sqrt{2}}$ and $1$ edge is of cost $1$.

So, the answer is ${\sqrt{2}}$ $\left ( n{^{2}}-2 \right )+1$.

This pattern continues for high values of $n.$

For $n=4$, the maximum spanning tree is:

(one of possibilities)

For $n=4,16$  vertices are there and the maximum spanning tree requires $15$ edges. Out of $15$ edges, $14$ edges are of cost ${\sqrt{2}}$ and $1$ edge is of cost $1$. Thus satisfying the formula ${\sqrt{2}}$ $\left ( n{^{2}}-2 \right )$ $+1$.

The cost of Minimum spanning tree is: $n^{2}-1$.

The cost of Maximum spanning tree is: $\left ( n^{2}-2 \right )\sqrt{2}+1$.

answered by Active (1.4k points)
edited by
no, it wont form a cycle. Its needed to connect all the vertices.
Super like ... That is called explanation ....
Why add cost 1 edge in maximum spanning tree
+9 votes

A.  In the graph start applying Kruskal algorithm. So, we select all edges of cost $1$ first. 

For each $y = i$, there will be $n-1$ unit length path. Total cost = $n(n-1)$ 

Then we can join these $n$ lines by one vertical line whose length is $n-1$.

$$n(n-1) + (n-1) = (n-1)\cdot (n+1) = n^2 -1$$

B. We can apply Kruskal's algorithm by taking maximum weight edge (ref). Maximum weight edge here is $\sqrt 2$ as we are taking Euclidean distance as mentioned in question. 

All diagonals will sum to:
$$\sqrt{2} (n-1) +2 \Bigl ( \sqrt{2} (n-2) + \sqrt{2} (n-3)+ \dots + \sqrt{2} \Bigr ) \\= \sqrt{2} (n-1) +\sqrt{2}. (n-1). (n-2) \\= \sqrt{2}. (n-1)^2$$
(One main diagonal and $(n-1)$ diagonals on either side of it).

Now, we can no more add any edge of weight $\sqrt 2$  without forming a cycle. 

So, we take $2(n-1)$ edges of weight $1$ to interconnect these diagonals

$= \sqrt{2} (n -1)^2 + 2(n-1) \\= \sqrt{2} \cdot (n-1) \cdot (n-1+\sqrt 2)$

answered by Veteran (55.6k points)
edited by

in b for maximum spanning tree put n=3 gives 8*root(2)+4. which means  #'s of edges=12. but n=3 means #'s of vertices is V=9 { n2} . so #'s of edges in spanning tree will be V-1 i.e. 8
So how's it possible??

i think b ans is root(2)*(n-1)2+2(n-1)

You are right. There was a calculation mistake- corrected now.

it took me 5 minute to understand why did you take (n-1) total length in vertical line, then suddenly i got bcz of cycle :P Nice explanation !!

i am not able to see the cycle by adding more diagonal elements. can u plzz explain a bit more??
plzz someone explain part B
arjun sir plzz check it. If we just take n=2 that is 4 coordinates then we can make a spanning tree by taking both diagonal edges of length root 2 and one edge of length 1. So the formula derived here will give wrong answer. I dont know where i am makin mistake. I have wasted lot of time on this question. Plz verify and tell me where i am doing wrong.
+3 votes

Most of people have given correct answer for part A and B.

Just to provide another way of thinking, adding some explanation for Part B.

                   (3) Now if you will observe $D_1$ is connecting  odd number diagonal  and $D_2$ is connecting even number diagonal. We need one more max distance link to connect them ($D_1$ and $D_2$). So final answer is $\sqrt{2}*({n}^2-2)+1$

answered by Boss (11.4k points)
edited by
add 1 to ur answer.

Thank you @sushmita ji.


for OPTION B it is 


but this doesnt work for n=2

–2 votes

A) n2+2n

B) ((n2+2n-1)√2)+1

answered by Active (3.9k points)
Can you please explain....

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,598 questions
48,599 answers
63,711 users