8 votes 8 votes 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 _________ Algorithms gatecse-2020 numerical-answers algorithms graph-algorithms 2-marks + – Arjun asked Feb 12, 2020 • retagged Nov 30, 2022 by Lakshman Bhaiya Arjun 9.8k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Shiva Sagar Rao commented Dec 1, 2020 reply Follow Share Similar questions: https://gateoverflow.in/2768/gate1996-16 https://gateoverflow.in/890/gate2006-11 2 votes 2 votes Vijay Devagonda commented Dec 26, 2023 reply Follow Share 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 . 👍 0 votes 0 votes Akash 15 commented Jan 4 reply Follow Share 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$ 0 votes 0 votes Please log in or register to add a comment.
Best answer 18 votes 18 votes 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$. Srinivas_Reddy_Kotla answered Feb 12, 2020 • edited May 30, 2021 by Lakshman Bhaiya Srinivas_Reddy_Kotla comment Share Follow See all 4 Comments See all 4 4 Comments reply Argharupa Adhikary commented Dec 15, 2022 reply Follow Share This is a very good aptitude question. 3 votes 3 votes Harshit Dubey commented Jul 26, 2023 reply Follow Share 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 ? 1 votes 1 votes Sachin Mittal 1 commented Jul 26, 2023 reply Follow Share @Harshit Dubey How you will check it? It is a NAT question. 0 votes 0 votes Harshit Dubey commented Jul 26, 2023 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes 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/ shashankrustagi answered Oct 28, 2020 shashankrustagi comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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. Anshul999 answered Feb 12, 2020 Anshul999 comment Share Follow See all 0 reply Please log in or register to add a comment.
–2 votes –2 votes 99 Because Vertex 1 is connected to all 2...99 vertex so weight of minm spanning tree is 99 lovegate answered Feb 25, 2020 lovegate comment Share Follow See 1 comment See all 1 1 comment reply Pranavpurkar commented Sep 14, 2021 reply Follow Share 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. 2 votes 2 votes Please log in or register to add a comment.