GATE CSE 1997 | Question: 9

Question

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}$

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

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

Comments

Can easily modify this question and ask in future GATE with fixed value of n

---

Good question! Can teach many things in one.

---

I was initially confused because I did not realize that the adjacency condition is effectively defining the edge set of the graph. I was interpreting it as additional information about adjacent vertices rather than a restriction on which pairs of vertices can be connected.

Answer 1

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:

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 are 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$.

Comments

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

---

good explanation

---

One thing to notice here x and y both are ranging from 1 to n.

but if range is not same like :

x ranges from 1 to m    ,  1<=x<=m

y ranges from 1 to n    ,  1<=y<=n

then, weight of a minimum weight-spanning tree in the given graph will be,

 = m*n -1

and weight of maximum weight spanning tree in the graph will be,

= (m*n-2)*$\sqrt{2}$+1

---

@balaeinstein
1st)  Isnt it given that n>=2, but here you just used n>=1
2nd) You added 1 to complete n-1 edges ? right. so in maximum Spanning tree , couldnt we add root(2) instead

making the formulas::

min ST : N^2 -1
max ST : (N^2 -1)root(2)

where N is num of vertices in a row/column, rather than the value n in question.
as acc to question n>=2.
so N = n-1 everywhere

---

How are you taking the nodes as adjacent when they have √2 distance between them , when in question it's written that adjacent nodes are those nodes in which both x cordinate and y cordinate distance should be less than 1??just have this doubt

---

@Arpit Sawade
the adjacent condition given is as |x1 - x2| and |y1 - y2|
take example from the best answer image (1,1) and (2,2) have an edge of weight √2,
here x1 = 1 and x2 = 2 -> |1-2| = 1
similarly y1 = 1 and y2 = 2 -> |1-2| = 1
so the conditions are met
it checks with the same axis coordinate not with the other!

Answer 2

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$

Comments

for OPTION B it is 

√2∗(n²−2)+1

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 :)

---

Thank you, this explanation is clear and concise.

Answer 3

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$.

Total:
$$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)$

Comments

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.

Answer 4

A) n²+2n

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

Comments

Can you please explain....