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 | 473 views
what answer you got for a?

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
no, it wont form a cycle. Its needed to connect all the vertices.

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

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.

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

Thank you @sushmita ji.

A) n2+2n

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

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