in Algorithms edited by
4,169 views
21 votes
21 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
4.2k views

4 Comments

MST will be -->

(A) Line graph.

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

(A) n-1

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

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

42 votes
42 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