26 votes 26 votes A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ if the weight of the edge $(u, v)$ is $\mid u-v\mid$ the weight of the edge $(u, v)$ is $u + v$ Algorithms gate1996 algorithms graph-algorithms spanning-tree normal descriptive + – Kathleen asked Oct 9, 2014 • edited May 14, 2018 by Milicevic3306 Kathleen 5.2k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Chhotu commented Aug 24, 2017 reply Follow Share MST will be --> (A) Line graph. (B) Star Graph. 6 votes 6 votes Ayan Kumar Pahari commented Jul 12, 2020 reply Follow Share Weight of the Minimum spanning tree-> (A) n-1 (B) n*(n-1)/2 4 votes 4 votes Shiva Sagar Rao commented Dec 1, 2020 reply Follow Share Application of this question has been asked in GATE 2020. https://gateoverflow.in/333182/gate-2020-cse-question-49 3 votes 3 votes Arpit Patel commented Oct 23, 2021 reply Follow Share Line Graph is different from Path Graph. Here it represents Path Graph for option (A). https://en.wikipedia.org/wiki/Path_graph https://en.wikipedia.org/wiki/Line_graph 0 votes 0 votes Please log in or register to add a comment.
Best answer 46 votes 46 votes $\text{(A)}$ $\text{(B)}$ Anu answered Jun 2, 2015 • edited May 7, 2019 by Lakshman Bhaiya Anu comment Share Follow See all 3 Comments See all 3 3 Comments reply talha hashim commented Jul 4, 2018 reply Follow Share nice @Anu 1 votes 1 votes Ritik Jain RJ commented Jan 19, 2019 reply Follow Share The graph is not complete 🏜️ 1 votes 1 votes vizzard110 commented Sep 10, 2019 reply Follow Share This is the minimum spanning tree for the complete graph. 2 votes 2 votes Please log in or register to add a comment.
