4,169 views

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

1. the weight of the edge $(u, v)$ is $\mid u-v\mid$

2. the weight of the edge $(u, v)$ is $u + v$

MST will be -->

(A) Line graph.

(B) Star Graph.
Weight of the Minimum spanning tree->

(A) n-1

(B) n*(n-1)/2

Application of this question has been asked in GATE 2020.

https://gateoverflow.in/333182/gate-2020-cse-question-49

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

$\text{(A)}$

$\text{(B)}$

by

nice @Anu
The graph is not complete 🏜️
This is the minimum spanning tree for the complete graph.

1
2
3