GATE CSE 2020 | Question: 49

Question

Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j \mid$. The weight of minimum spanning tree of $G$ is _________

Comments

Similar questions:

https://gateoverflow.in/2768/gate1996-16

https://gateoverflow.in/890/gate2006-11

---

Everyone got the answer like 1->2->3...->100 , so total weight is 99. But i just want to discuss something about G . Ladies and gentleman i just want to clarify that G is a complete graph , except self loop every vertex is connected to other vertex . 👍

---

In graph $G=(V,E)$
$V=\{v_1,v_2,…,v_{100}\}$
$E=\{(v_1,v_2),(v_2,v_3),…,(v_{99},v_{100})\}$
Weights
$W=\{1,1,…,1\}$

So, there will be $99$ edges in $100$ vertices each of weight $1$
$\therefore$ Weight of min spanning tree $=99\times 1=99$

Answer 1

Vertices are given from $1$ to $100$ and edge weight between the vertices is absolute values of the difference between the suffix values of the vertices.

So, if we choose the vertices consecutively as $1-2-3-4-5-  \ldots -99-100$ we get the spanning tree with minimum weight.

Spanning tree will contain $99$ edges since there are $100$ vertices and cost of each edge is $ ‘1\text{'}.$

Therefore, weight of spanning tree would be $99\ast 1 = 99$.

Comments

This is a very good aptitude question.

---

Here we can directly take up a smaller example of 4 or 5 edges and then check it, instead of taking it for 100 Edges.

Is my approach correct @Sachin Mittal 1 sir ?

---

@Harshit Dubey
How you will check it? 
It is a NAT question.

---

Sir for a smaller set of numbers we can check check it like for V = 2 it is 1, for V = 4 it comes to be 3, for V = 5 it comes to be 4. Thus for V it will be v-1.

Answer 2

THIS IS A REPETITIVE QUESTION, WITH LITTLE BIT MODIFICATION. ONCE ASKED IN GATE 2006

WE WILL BE SELECTING EDGES SUCH THAT EDGE WEIGHT IS MINIMUM 

2-1=1

3-2 = 1

4-2=1

…

100-99=1

 

THIS IS A PATH 1-2-3-4-5-6-...-98-99-100

HAVING 99 EDGES AND EACH HAVING EDGE WEIGHT 1

 

https://www.geeksforgeeks.org/gate-gate-cs-2006-question-11/

 

 

Answer 3

In MST, all the edges of weight 1 will be connected like V1 to V2, V2 to V3 and so on.

So. the Weight of MST of G will be 99.

Answer 4

99 Because Vertex 1 is connected to all 2...99 vertex

so weight of minm spanning tree is 99

Comments

NO  vertex 1 is not connected to all other 99 vertices….

here  1 is connected to 2 and 2 is connected to 3 and so on…..99 is connected to 100.

thats why 99 edges.