Testbook Logo
Exams SuperCoaching Test Series Skill Academy
More
English
Hindi

Question

Download Solution PDF

The weight of minimum spanning tree in graph G, calculated using Kruskal’s algorithm is:

F1 R.S 18.5.20 Pallavi D2

This question was previously asked in
UGC NET Computer Science (Paper 2) Dec 2019 Paper
Attempt Online
View all UGC NET Papers >
  1. 14
  2. 15
  3. 17
  4. 18

Answer (Detailed Solution Below)

Option 2 : 15
Free Tests
View all Free tests >
Free
UGC NET Paper 1: Held on 21st August 2024 Shift 1
10.8 K Users
50 Questions 100 Marks 60 Mins
Start Now

Detailed Solution

Download Solution PDF

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

Edge set for the given graph = {2, 3, 4, 5, 6, 7, 8}

For 5 vertices, we need 4 edges in MST,

So, edge set for MST = {2, 3, 4, 6}

Minimum spanning tree

F2 R.S 18.5.20 Pallavi D1

Minimum cost 2 + 3 + 4 + 6 = 15

Download Solution PDF
Latest UGC NET Updates

Last updated on Jun 12, 2025

-> The UGC NET June 2025 exam will be conducted from 25th to 29th June 2025.

-> The UGC-NET exam takes place for 85 subjects, to determine the eligibility for 'Junior Research Fellowship’ and ‘Assistant Professor’ posts, as well as for PhD. admissions.

-> The exam is conducted bi-annually - in June and December cycles.

-> The exam comprises two papers - Paper I and Paper II. Paper I consists of 50 questions and Paper II consists of 100 questions. 

-> The candidates who are preparing for the exam can check the UGC NET Previous Year Papers and UGC NET Test Series to boost their preparations.

More Spanning Tree Questions

Q1.Given the graph below which one of the following edges cannot be added in that order to find a minimum spanning tree algorithm. A. a - b B. d - f C. b - f D. d - c E. d - e Choose the correct answer from the options given below: 
Q2.Consider the Graph below: How many spanning trees can be found?
Q3.Consider the given tree below. Calculate the value at the root of the tree using alpha‐beta pruning algorithm.
Q4.Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE ?
Q5.Let G (V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A. \(\rm A [i][j] = \left\{ \begin{matrix} 1, & \rm 1 \le j \le i \le 5\\\ 0, & \ \rm otherwise \end{matrix} \right.\) A[𝑖][𝑗] = 1 indicates a directed edge from node i to node j. A directed spanning tree of G, rooted at r ∈ V, is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V. The number of such directed spanning trees rooted at vertex 5 is ______
Q6.What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
Q7.What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
Q8.The length of the path from ν5 to ν6 in the MST of previous question with n = 10 is
Q9.What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
Q10.Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?

More Graphs/Spanning Tree and Shortest Paths Questions

Q1.Statement 1: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to find the lower bound on the weight of the minimum-weight vertex cover. Statement 2: The lower bound can be found by maximizing the following \(\rm\sum_{v \in V}^n {w}(v) {x}(v)\) subject to x(u) + x(v) ≥ 1 for each (u, v) ∈ V x(v) ≤ 1 for each v ∈ V x(v) ≥ 0 for each v ∈ V In the light of the above statements, choose the most appropriate answer from the options given below:
Q2.Given the graph below which one of the following edges cannot be added in that order to find a minimum spanning tree algorithm. A. a - b B. d - f C. b - f D. d - c E. d - e Choose the correct answer from the options given below: 
Q3.Consider the Graph below: How many spanning trees can be found?
Q4.A top down approach to programming calls for: Statement I: Working from the general to the specific. Statement II: Postpone the minor decisions. Statement III: A systematic approach. Statement IV: Intermediate coding of the problem Which of the following is true?
Q5.Consider the following graph: For the graph; the following sequences of depth first search (DFS) are given (A) abcghf (B) abfchg (C) abfhgc (D) afghbc Which of the following is correct?
Q6.Consider the given tree below. Calculate the value at the root of the tree using alpha‐beta pruning algorithm.
Q7.Given below are two statements Statement I : Breadth‐First Search is optimal when all the step costs are equal whereas uniform‐cost search is optimal with any step‐cost. Statement II : When all the step costs are same uniform‐cost search expends more nodes at depth d than the Breadth‐First Search. In light of the above statements, choose the correct answer from the options given below
Q8.Consider the following graph. Among the following sequences I. a b e g h f II. a b f e h g III. a b f h g e IV. a f g h b e Which are depth first traversals of the above graph?
Q9.Which of the following concepts can be used to identify loops? A. Depth first ordering B. Dominators C. Reducible graphs Choose the correct answer from the options given below :
Q10.Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE ?

More Algorithms Questions

Q1.The Highest Lower Bound on the number of Comparisons in the worst case for comparison-based sorting order of : 
Q2.In what manner is a state-space tree for a backtracking algorithm constructed ? 
Q3.Which open addressing technique is free from Clustering problems ?
Q4.Assume that P and NP are different i.e. P! = NP then for the expression NP-Complete ∩ P = ? Which among the following is correct ? 
Q5.The recurrence relation for binary search algorithm is : 
Q6.The time complexity of solving the Longest Common Subsequence problem using Dynamic Programming is : (m and n are lengths of subsequences) 
Q7.Given the following characteristics : (i) Optimal substructure (ii) Overlapping subproblems (iii) Memorization (iv) Decrease and conquer Dynamic programming has the following characteristics :
Q8.Which of the following is not a stable sorting algorithm ?
Q9.Match the LIST-I with LIST-II LIST - I LIST - II A. Breadth First Search I. LISP B. Depth First Search II. Syntax tree C. Prefix III. Stack D. Infix IV. Queue Choose the correct answer from the options given below:
Q10.Which one of the following is not related to the feed forward networks on the Backpropagation Algorithm
Super Coaching
UGC NET Test Series
UGC NET Previous Year Papers
UGC NET Syllabus
UGC NET Books
Testbook Edu Solutions Pvt. Ltd.
1st & 2nd Floor, Zion Building,
Plot No. 273, Sector 10, Kharghar,
Navi Mumbai - 410210
[email protected]
Toll Free:1800 833 0800
Office Hours: 10 AM to 7 PM (all 7 days)
Company
About usCareers We are hiringTeach Online on TestbookPartnersMediaSitemap
Products
Test SeriesTestbook PassOnline CoursesOnline VideosPracticeBlogRefer & EarnBooks
Our Apps
Follow us on
Copyright © 2014-2022 Testbook Edu Solutions Pvt. Ltd.: All rights reserved
User PolicyTermsPrivacy
Get Free Access Now
Hot Links： lucky teen patti teen patti royal teen patti 50 bonus