edited by
6,394 views
33 votes
33 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.

edited by

4 Answers

Best answer
62 votes
62 votes

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

edited by
10 votes
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$.

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

edited by
9 votes
9 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$

edited by
–2 votes
–2 votes

A) n2+2n

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

Related questions

21 votes
21 votes
1 answer
1
Kathleen asked Sep 29, 2014
4,792 views
Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$.Which of the following statements is true?$T(n) = O...
21 votes
21 votes
3 answers
2
Kathleen asked Sep 29, 2014
4,971 views
The correct matching for the following pairs is$$\begin{array}{ll|ll}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\\hline \text{B.} & \...
11 votes
11 votes
5 answers
3