GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
473 views

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 (64.6k points)   | 473 views
what answer you got for a?

4 Answers

+4 votes
Best answer

 

 

 

In the first image , 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.

 

 

answered by Junior (917 points)  
edited by
no, it wont form a cycle. Its needed to connect all the vertices.
+7 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$.

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

answered by Veteran (47k 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.
0 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 Active (2.2k points)  
edited by
add 1 to ur answer.

Thank you @sushmita ji.

–2 votes

A) n2+2n

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

answered by Loyal (3.6k points)  
Can you please explain....

Related questions



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2092 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,651 answers
79,695 comments
31,069 users