The Gateway to Computer Science Excellence
+19 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.

in Algorithms by Veteran (52.1k points)
edited by | 1.9k views

4 Answers

+32 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 a 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$.

by Active (1.5k 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 ?
superb ....... thanks for such explanation.

@Jony Bhatt just observe the 3rd image ,you will see two tree ,in which one tree joining the alternate vertices

and another tree joining the remaining alternate vertices 

and the edge weight 1 connecting these tree to for single tree  that is why we added one

+10 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)$

by Veteran (60.4k 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.
+4 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$

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

Thank you @sushmita ji.


for OPTION B it is 


but this doesnt work for n=2


@Chhotu Ji,

You wrote "We need one more max distance link to connect them (D1and D2). " 

Is it "min'  distance link , i mean we connect edge with cost "1" which is min distance. Just need clarification :)

–2 votes

A) n2+2n

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

by Active (4.1k 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
50,654 questions
56,166 answers
94,260 users