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

how we know whether it is a line graph or star graph?

---

Main beauty of this Question lies in how (indirectly) they have mentioned that the graph is complete graph of 100 vertices in the edge set decription
Variation:If edge weights were $v_i+v_j$, the weight of MST would be $ 5148 $ (for the same graph)

---

How $5148$?

First go through this PYQ- https://gateoverflow.in/2768/gate-cse-1996-question-16
Here, the $n$ vertices are labelled as $(0,1,2,3....n-1)$
Thus, if edge weights are $u+v$ (for edge $(u,v))$, we get weight of MST as $1+2+3+4.....+n-1 = nC_2$

Now in the given question, vertices are labelled  as $(1,2,3.....n)$ 
Thus, for every edge the weight has increased by $2$ ( as each vertex is increased by 1 as compared  to the PYQ mentioned above.You can check by taking small examples.)
Thus,
Total weight  = $nC_2 + 2(n-1)$ ..(because it is MST, the total edges will be $n-1)$
Hence, for $n=100$
Total MST weight $= 100C_2 + 2(99)$

                            $=4950+198$

                            $=5148$

I believe this application can also be asked in Future GATE exams.
 
 

---

Its a Complete Graph or DAG ?, 12 is egde but not 21

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

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.

---

yes , it could be we will see that there is always no edge  between first vertex and last vertex , and rest will have edge weight as 1 so total v-1 edges 

---

Correct Dubey ji I to follow that method

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

Here is the solution : 

Comments

Best One @Kshitij Sharma Bhaiya

---

This one is nice explanation......@kshitij Sharma

Answer 4

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 5

Its better to take small example of 10 vertices and solve where each vertex 1,2 ,3, 4, 5,6,7,8,9,10 has number of edges from 9, 8, 7,6,5,4,3,2,0 respectively. And each vertex has edge with weight 1 so we take edges |V-1| times as the last vertex would form cycle.

For the example with 10 vertex we got weight of MST as 9 similarly for 100 vertices we get weight as 99.

Answer 6

Let's read the below explanation 

Comments

good explanation