in Algorithms edited by
5,096 views
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

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

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

in Algorithms edited by
5.1k views

4 Comments

MST will be -->

(A) Line graph.

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

(A) n-1

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

Application of this question has been asked in GATE 2020.

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

3
3

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
0

1 Answer

46 votes
46 votes
Best answer

$\text{(A)}$

$\text{(B)}$

edited by
by

3 Comments

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

Related questions