Question
Download Solution PDFA weighted complete graph with n vertices has weight 2|i - j| at edges (vi, vj). The weight of a minimum spanning tree is
Answer (Detailed Solution Below)
Detailed Solution
Download Solution PDFConcept:
- A minimum spanning tree is a spanning tree in which the sums of the weight of the edges are as minimum as possible.
- A minimum spanning tree has n vertex and n - 1 edge.
Explanation:
Suppose n = 3
Complete graph with n = 3
The minimum spanning tree of graph G is:
Option 1: False
The total weight of the minimum spanning tree is: \(\frac{{{3^2}}}{2}\) = 4.5
Option 2: False
The total weight of the minimum spanning tree is: \(\frac{{{3}}}{2}\) = 1.5
Option 3: True
The total weight of the minimum spanning tree is: 2 × 3 - 2 = 4
Option 4: False
The total weight of the minimum spanning tree is: 3 - 2 = 1Last updated on Jul 2, 2025
-> ESE Mains 2025 exam date has been released. As per the schedule, UPSC IES Mains exam 2025 will be conducted on August 10.
-> UPSC ESE result 2025 has been released. Candidates can download the ESE prelims result PDF from here.
-> UPSC ESE admit card 2025 for the prelims exam has been released.
-> The UPSC IES Prelims 2025 will be held on 8th June 2025.
-> The selection process includes a Prelims and a Mains Examination, followed by a Personality Test/Interview.
-> Candidates should attempt the UPSC IES mock tests to increase their efficiency. The UPSC IES previous year papers can be downloaded here.