First time here? Checkout the FAQ!
+7 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 (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$.

$$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
31,069 users